Exercise 1.19
We define $U := λzx. x(zzx)$ and $Z := U U$. Prove that $Z$ is a fixed point combinator, i.e. $ZM$ is a fixed point for every λ-term $M$, so $M(ZM) =_β ZM$. Show that even holds: $ZM \to_β M(ZM)$.
Let's start with $ZM$.
$$\begin{align} ZM & = (UU)M \\ \\ & = (λzx.x(zzx))(λba.a(bba))M \\ \\ & \to λx.x((λba.a(bba))(λba.a(bba))x)M \\ \\ & \to M((λba.a(bba))(λba.a(bba))M) \\ \\ & \to M(ZM) \end{align}$$
We have shown
$$ZM \to_β M(ZM)$$
Which means,
$$M(ZM )=_β ZM$$
That is, Z is a fixed point combinator for any M, because $M(ZM) =_β ZM$.
