Exercise 1.16
Let $M$ be a λ-term with the following properties:
(1) $M$ has a β-normal form.
(2) There exists a reduction path $M ≡ M_0 →_β M_1 →_β M_2 →_β \ldots $ of infinite length.
(a) Prove that every $M_i$ has a β-normal form.
(b) Give an example of a λ-term with the mentioned two properties and show that it satisfies these properties.
(a) By property (2) every $M_i$ can be β-converted to $M_{i-1}$. This process can be repeated until $M_0 ≡ M$. By property (1) $M$ has a β-normal form. Therefore there is a path from every $M_i$ to this β-normal form. So every $M_i$ has a β-normal-form.
(b) The example given in 1.9.3 works. Let's define it
$$T := (λu. v)Ω = (λu. v)( (λx. xx)(λx. xx) )$$
There are two redexes, the full term $T$ and the sub-term Ω.
The redex $T$ β-reduces to $v$ which is in β-normal-form. So the λ-term has a β-normal-form, property (1).
The second redex Ω has only one option for β-reduction, $Ω \to Ω$. This means there is a reduction path from $T := (λu. v)Ω$ of infinity length, $T \to T \to T \to \ldots$. This is property (2).
