Regardless, of whether we are supposed to show all these facts as consequences of $A_{E}$ or not, my solution of Exercise 2 shows that there is one-to-one correspondence between “finite” numbers in $\mbox{Cn}A_{E}$ and natural numbers $\mathbb{N}$ , in the sense that $A_{E}\vdash\mathbb{S}^{m}0<\mathbb{S}^{n}0$ iff $m<n$ ($A_{E}$ proves the negation otherwise), and $A_{E}\vdash\mathbb{S}^{m}0=\mathbb{S}^{n}0$ iff $m=n$ ($A_{E}$ proves the negation otherwise). Therefore, we will proceed informally, as is done for the most part of the section in the text, keeping in mind that the solution can be translated into the formal language to be proved from $A_{E}$ .

(a) $0+1=1<2=p_{0}$ . By induction, $a+1<p_{a}$ implies $(a+1)+1=a+2\le p_{a}<p_{a+1}$ .

(b) Note, that, formally, $(b)_{k}$ is defined for all natural numbers as the least $n\in\mathbb{N}$ such that either $b=0$ or $<p_{k}^{n+2},b>\notin\mathcal{D}$ where $\mathcal{D}$ is the divisibility relation. By definition,$(0)_{k}=0$ for all $k\in\mathbb{N}$ . For $b\ge1$ , either $(b)_{k}=0<b$ , or $(b)_{k}-1\ge0$ , and $p_{k}^{[(b)_{k}-1]+2}=p_{k}^{(b)_{k}+1}$ divides $b$ , i.e. $b\ge p_{k}^{(b)_{k}+1}>p_{k}^{(b)_{k}}$ . We just need to argue that for $p\ge2$ and $a\in\mathbb{N}$ , $p^{a}\ge a$ . In fact, we will show $p^{a}\ge a+1$ . For $a=0$ , we have $1\ge0+1$ , and, by induction, if $p^{a}\ge a+1$ , then $p^{a+1}\ge2p^{a}\ge2a+2\ge(a+1)+1$ .

(c) Again, formally, $\mbox{lh}a$ is defined for all natural numbers as the least $n\in\mathbb{N}$ such that either $a=0$ or $<p_{n},a>\notin\mathcal{D}$ . By definition, $\mbox{ln}0=0$ . For $a\ge1$ , either $\mbox{ln}a=0<a$ , or $\mbox{ln}a-1\ge0$ , and $p_{\mbox{ln}a-1}$ divides $a$ . By (a), $\mbox{ln}a=\mbox{ln}a-1+1<p_{\mbox{ln}a-1}\le a$ .

(d) Again, formally, $a\upharpoonright i$ is defined for all natural numbers as the least $n\in\mathbb{N}$ such that either $a=0$ or both $n\neq0$ and for every $j<i$ , $k<a$ , $<p_{j}^{k},a>\in\mathcal{D}$ implies $<p_{j}^{k},n>\in\mathcal{D}$ . Suppose, $a\upharpoonright i-1\ge a$ . Then, $a\upharpoonright i\ge1$ , implying $a\ge1$ , implying $a\upharpoonright i\ge2$ , implying for every $1\le b\le a\upharpoonright i-1$ , there are $j<i$ and $k<a$ such that $<p_{j}^{k},a>\in\mathcal{D}$ but $<p_{j}^{k},b>\notin\mathcal{D}$ , in particular, for $b=a\le a\upharpoonright i-1$ , there are $j<i$ and $k<a$ such that $<p_{j}^{k},a>\in\mathcal{D}$ but $<p_{j}^{k},a>\notin\mathcal{D}$ , contradiction. Hence, $a\upharpoonright i-1<a$ , and $a\upharpoonright i\le a$ .

(e) $\mbox{lh}(a\upharpoonright i)$ is the least $n\in\mathbb{N}$ such that either $a\upharpoonright i=0$ or $<p_{n},a\upharpoonright i>\notin\mathcal{D}$ , where $a\upharpoonright i$ is the least $m\in\mathbb{N}$ such that either $a=0$ or both $m\neq0$ and for every $j<i$ , $k<a$ , $<p_{j}^{k},a>\in\mathcal{D}$ implies $<p_{j}^{k},m>\in\mathcal{D}$ . Further, $\mbox{lh}a$ the least $l\in\mathbb{N}$ such that either $a=0$ or $<p_{l},a>\notin\mathcal{D}$ . If $a=0$ , then $\mbox{lh}a=0$ , $a\upharpoonright i=0$ , and $\mbox{lh}(a\upharpoonright i)=0=\mbox{lh}a\le i$ . If $a\ge1$ and $i=0$ , then $a\upharpoonright i=1$ and $\mbox{lh}(a\upharpoonright i)=0=i\le\mbox{lh}a$ . Now, suppose $a>0$ and $i>0$ . Then, $a\upharpoonright i>0$ . If $0<i<\mbox{lh}a$ , then, by definition of $\mbox{lh}a$ , for all $l<i$ , $<p_{l},a>\in\mathcal{D}$ , and, by definition of $a\upharpoonright i$ , $<p_{l},a\upharpoonright i>\in\mathcal{D}$ , but for $l\ge i$ , $<p_{l},a\upharpoonright i>\notin\mathcal{D}$ (otherwise, we can divide $a\upharpoonright i$ by $p_{l}$ to obtain a smaller $m$ satisfying the definition). Then, by definition of $\mbox{lh}(a\upharpoonright i)$ , $\mbox{lh}(a\upharpoonright i)=i<\mbox{lh}a$ . Finally, if $i\ge\mbox{lh}a$ , then, by definition of $\mbox{lh}a$ , for all $l<\mbox{lh}a$ , $<p_{l},a>\in\mathcal{D}$ , but $<p_{\mbox{lh}a},a>\notin\mathcal{D}$ . Then, by definition of $a\upharpoonright i$ , for all $l<\mbox{lh}a\le i$ , $<p_{l},a\upharpoonright i>\in\mathcal{D}$ , but $<p_{\mbox{lh}a},a\upharpoonright i>\notin\mathcal{D}$ (otherwise, we can divide $a\upharpoonright i$ by $p_{\mbox{lh}a}$ to obtain a smaller $m$ satisfying the definition). Hence, by definition of $\mbox{lh}(a\upharpoonright i)$ , $\mbox{lh}(a\upharpoonright i)=\mbox{lh}a\le i$ .

Note. This last point holds for every number $a$ , even if it is not a sequence number, and even if it is odd ($\mbox{lh}a=0$ ).

$a$	$\mbox{lh}a$	$i$	$a\upharpoonright i$	$\mbox{lh}(a\upharpoonright i)$
$10=2\cdot5$	$1$	$1$	$2$	$1$
$10=2\cdot5$	$1$	$2$	$2$	$1$
$10=2\cdot5$	$1$	$3$	$10=2\cdot5$	$1$
$15=3\cdot5$	$0$	$1$	$1$	$0$
$15=3\cdot5$	$0$	$2$	$3$	$0$
$15=3\cdot5$	$0$	$3$	$15=3\cdot5$	$0$
$42=2\cdot3\cdot7$	$2$	$1$	$2$	$1$
$42=2\cdot3\cdot7$	$2$	$2$	$6=2\cdot3$	$2$
$42=2\cdot3\cdot7$	$2$	$3$	$6=2\cdot3$	$2$