At a certain level, no one is any good at proving stuff unless they practice over and over and over again! Even the brilliant mathematics student reaches a point (often in mid-UG studies) where the weird innate talent that helped them sail through school runs dry, and they have to learn to think carefully and practice proof techniques they pick up from textbooks and teachers.

The post below about diagonalization has, tucked just beneath the surface, examples of things that aren't too hard to prove, and are useful for getting some practice at proofs by induction. For example,

Because of the presence of $\underline{0}$ and $S$ in $\mathcal{L}$, there is a canonical way of denoting numbers, using canonical numerals. Roughly, the number $n$ is denoted by the term $S\dots S\underline{0}$, with $S$ repeated $n$ times. More exactly, one defines a functionSo, how do we prove this by induction?

$\underline{ }:\mathbb{N} \rightarrow Tm(\mathcal{L})$,by primitive recursion as follows:

$\underline{0}:= \underline{0}$So, for example, the number 7 is denoted by $\underline{7}$, which is the term $SSSSSSS\underline{0}$. By induction, it is easy to prove that $(\underline{n})^{\mathbb{N}}=n$.

$\underline{n+1}:=S\underline{n}$

Induction is used to prove claims of the form,

for all $n$, $n$ has property P,by two preliminary steps:

(i) Base step: show that $0$ has P.It's always useful to identify the property in question. In this case,

(ii) Induction step: show that if $k$ has P, then $k+1$ has P too (where $k$ is arbitrary).

$n$ has the property P iff $(\underline{n})^{\mathbb{N}}=n$So, the two steps required are:

(i)The Base step is completely obvious, because $(\underline{0})^{\mathbb{N}}$ is defined to be the number $0$.Base step: show that $(\underline{0})^{\mathbb{N}}=0$.

(ii)Induction step: show that if $(\underline{k})^{\mathbb{N}}=k$, then $(\underline{k+1})^{\mathbb{N}}=k+1$.

The induction step is fairly straightforward. We want to show that,

if $(\underline{k})^{\mathbb{N}}=k$, then $(\underline{k+1})^{\mathbb{N}}=k+1$.So, first assume the

**Induction Hypothesis**:

$(\underline{k})^{\mathbb{N}}=k$The sub-aim is to prove,

$(\underline{k+1})^{\mathbb{N}}=k+1$from the Induction Hypothesis. And this proof should involve the definition of the function $\underline{ }$ that takes numbers to their numerals, and perhaps further "background facts". So, one can do it like this,

$(\underline{k+1})^{\mathbb{N}} = (S\underline{k})^{\mathbb{N}}$In the first line, we replace "$\underline{k+1}$" by its definition, namely "$S\underline{k}$". In the second line, we use the usual clause for evaluating the denotation of a compound term $ft$ relative to an interpretation $\mathcal{A}$, namely,

$= S^{\mathbb{N}}((\underline{k})^{\mathbb{N}})$

$= S^{\mathbb{N}}(k)$

$= k+1$, as required.

$(ft)^{\mathcal{A}} = f^{\mathcal{A}}((t)^{\mathcal{A}})$.In the third line, we use the Induction Hypothesis; and in the final line, we use the fact that $S^{\mathbb{N}}$ is the successor function.