Proof of Basic Properties of Initial Segments of the Natural Numbers

Throughout we use the numbered claims of Arithmetic of Addition on the Natural Numbers and of Properties of the Order on the Natural Numbers, and the description $[n]=\{k\in\mathbb{N}: k\le n\}$ from the definition of initial segments.

Claim 1. By claim 4 of Properties of the Order on the Natural Numbers we have $1\le n$, so $1\in[n]$, and by claim 1 of that lemma $n\le n$, so $n\in[n]$. In particular $[n]\ne\emptyset$.

Claim 2. By Claim 1, $1\in[1]$. Conversely let $k\in[1]$, so $k\le 1$. If $k\ne 1$ then $k<1$, so $1=k+a$ for some $a\in\mathbb{N}$ by the definition of the order, contradicting claim 7 of Arithmetic of Addition on the Natural Numbers. Hence $k=1$ and $[1]=\{1\}$.

Claim 3. By claim 5 of Properties of the Order on the Natural Numbers we have $n<S(n)$, so by the trichotomy in claim 3 of that lemma neither $S(n)<n$ nor $S(n)=n$ holds; hence $S(n)\le n$ is false and $S(n)\notin[n]$.

For the displayed equality, first let $k\in[n]\cup\{S(n)\}$. If $k\in[n]$ then $k\le n$, and $n<S(n)$ gives $n\le S(n)$, so $k\le S(n)$ by transitivity of $\le$ (claim 1 of Properties of the Order on the Natural Numbers); hence $k\in[S(n)]$. Also $S(n)\le S(n)$, so $S(n)\in[S(n)]$. Conversely let $k\in[S(n)]$, so $k\le S(n)$. If $k=S(n)$ then $k\in\{S(n)\}$; otherwise claim 5 of Properties of the Order on the Natural Numbers gives $k\le n$, i.e. $k\in[n]$.

Claim 4. Let $m\le n$ and $k\in[m]$, so $k\le m$. Transitivity of $\le$ (claim 1 of Properties of the Order on the Natural Numbers) gives $k\le n$, i.e. $k\in[n]$.

Claim 5. Define $\varphi(j)=m+j$ for $j\in[t]$.

$\varphi$ maps $[t]$ into $[m+t]\setminus[m]$. Let $j\in[t]$, so $j\le t$. By claim 6 of Properties of the Order on the Natural Numbers we get $m+j\le m+t$, hence $m+j\in[m+t]$. The same claim gives $m<m+j$, so by trichotomy (claim 3 of that lemma) neither $m+j<m$ nor $m+j=m$ holds; thus $m+j\le m$ is false and $m+j\notin[m]$.

$\varphi$ is injective. If $m+j=m+j'$, then by claim 4 of Arithmetic of Addition on the Natural Numbers we get $j+m=j'+m$, and claim 5 of that lemma gives $j=j'$.

$\varphi$ is surjective onto $[m+t]\setminus[m]$. Let $y\in[m+t]\setminus[m]$, so $y\le m+t$ while $y\le m$ fails. By trichotomy, $m<y$, so claim 7 of Properties of the Order on the Natural Numbers provides a unique $j\in\mathbb{N}$ with $y=m+j$. It remains to check $j\le t$. If $y=m+t$, then $m+j=m+t$ gives $j=t$ as in the injectivity argument. Otherwise $m+j=y<m+t$, so $m+t=(m+j)+c$ for some $c\in\mathbb{N}$; by claim 3 of Arithmetic of Addition on the Natural Numbers this reads $m+t=m+(j+c)$, and cancelling $m$ as above gives $t=j+c$, i.e. $j<t$. In both cases $j\in[t]$ and $\varphi(j)=y$.

Together, every $y\in[m+t]\setminus[m]$ has exactly one preimage in $[t]$, so $\varphi$ is a bijection from $[t]$ onto $[m+t]\setminus[m]$.

Finally, claim 6 of Properties of the Order on the Natural Numbers gives $m<m+t$, hence $m\le m+t$, and Claim 4 above gives $[m]\subseteq[m+t]$. Consequently $[m+t]$ is the union of $[m]$ and $[m+t]\setminus[m]$, and these two sets are disjoint by construction.