Exercise 1.17
Prove the following: if $MN$ is strongly normalising, then both $M$ and $N$ are strongly normalising.
Strongly normalising means a term has no infinite β-reduction paths starting from it.
The term $MN$ has three possibilities for redexes:
- the full term $MN$
- the first sub-term $M$
- the second sub-term $N$
If there were an infinite reduction path, it would have to start from one of these three possibilities.
Since there is no infinite reduction path, none of the three possibilities has an infinite reduction path. Specifically, terms $M$ and $N$ have no infinite reduction path from them.
Therefore $M$ and $N$ are strongly normalising.
