Exercise 1.18
Let $L$, $M$ and $N$ be λ-terms such that $L=_β M$ and $L \to_β N$.
Moreover, let $N$ be in β-normal form. Prove that also $M \to_β N$.
$L =_β M$ means one of the following is true
- case 1: $L \to_β M$
- case 2: $M \to_β L$
Let's consider each case in turn.
Case 1: $L \to_β M$ and $L \to_β N$, where $N$ is in β-normal-form, means $M \to_β N$ by the Church-Rosser Theorem.
Case 2: $M \to_β L$ and $L \to_β N$, means $M \to_β N$ by the transitivity of β-reduction.
Both cases lead to the conclusion $M \to_β N$
