Exercise $4.$ This is a classic exercise but very important. We will demonstrate how to

encode certain notions in Simply Typed Lambda Calculus. Fix a type a and let $T$ be nat

$=(aa)aa.$ The idea here is to encode each natural number $n$ into a term

whose type is nat. For example, the natural number $0$ is represented by $f^{a-a}{x}^a.x$; $$

the natural number $1$ by $hat(f{)}^{a-a}{x}^a.fx$;$1$ and the natural number $2$ by $f^{a-a}{x}^{a}f(fx).$

$($i$)$ For each $f,$xinV, consider the following recursive definition:

$f^{n}x=\{\begin{array}{ccc}x,& se& n=0\\ f(f^{n-1}x),& se& n>0\end{array}$

for each ninN. To start, show that $f^m(f^{n}x)=f^{m+n}x$ for each $m,$ninN.

$($ii$)$ For each ninN, we will write $\frac{?}{n7}$ to denote the previously typed term $f^{a-}{x}^a*f^{n}x.$

Show that $n$ is legal for each ninN.

$($iii$)$ Consider the following previously typed term suc $=a^{\text{n}\text{a}\text{t}}{f}^{a-a}{x}^a.f(afx).$

Show that sum is legal and that suc$[n]=[n+1]$ for each ninN.

$($iv$)$ Consider the following previously typed term:

sum $=a^{\text{n}\text{a}\text{t}}{b}^{\text{n}\text{a}\text{t}}{f}^{a-a}{x}^a*af(bfx).$

Show that sum is legal and that ${?}^{{\displaystyle \underset{?}{\overset{?}{}}}[m][n]}=[m+n]$ for each $m,$ninN.