Proof of Intervals of Natural Numbers: Initial Segments, Adding One Element, Splitting and Shifting

Each result cited below is universally quantified over the data in its own statement, and is applied to the data named where it is cited.

Throughout, $k$ ranges over $\mathbb{N}_{0}$. We use the following facts about $\mathbb{N}_{0}$. Its order $\le$ is a total order by The Order on Omega Is a Well-Order with Membership as Its Strict Order, and Nothing Lies between n and Its Successor §well-order, and $k<n$ means $k\le n$ and $k\neq n$ by The Order on Omega Is a Well-Order with Membership as Its Strict Order, and Nothing Lies between n and Its Successor §strict. Since $n+1$ is the successor of $n$ by Natural Numbers Are the Successors in Omega: One Is Least and Not a Successor of a Natural Number, the Successor Is Injective, and N Is Closed under Addition and Multiplication §plus-one, The Order on Omega Is a Well-Order with Membership as Its Strict Order, and Nothing Lies between n and Its Successor §successor gives $k<n+1$ if and only if $k\le n$, in particular $n<n+1$, so that $n+1\le n$ fails; and The Order on Omega Is a Well-Order with Membership as Its Strict Order, and Nothing Lies between n and Its Successor §successor-below gives $n<k$ if and only if $n+1\le k$.

Segment. An element $k$ of $\mathbb{N}_{0}$ lies in $\mathbb{N}$ if and only if $1\le k$: if $k\in\mathbb{N}$, then $1\le k$ by Arithmetic and Order of the Natural Numbers §least; if $k\notin\mathbb{N}$, then $k=0$ because $\mathbb{N}_{0}=\mathbb{N}\cup\{0\}$ by The Natural Numbers and the Natural Numbers with Zero: Arithmetic, Order, Induction and Recursion §sets, and $1\le0$ fails because $1$ is the successor of $0$ by The Set of Natural Numbers and the Number One §one, that is, $1=0+1$, and $0+1\le0$ fails. Hence $[n]=\{k\in\mathbb{N}_{0}:1\le k\le n\}=\{k\in\mathbb{N}:k\le n\}$. If $k\in\mathbb{N}$ and $k\le0$, then $1\le k\le0$, which is impossible; so $[0]=\emptyset$. If $k\in\mathbb{N}$ and $k\le1$, then $1\le k$ gives $k=1$ by antisymmetry; and $1\in\mathbb{N}$ with $1\le1$; so $[1]=\{1\}$.

Successor. For $k\in\mathbb{N}$, $k\le n+1$ holds if and only if $k<n+1$ or $k=n+1$, that is, if and only if $k\le n$ or $k=n+1$. Since $n+1\in\mathbb{N}$ by Natural Numbers Are the Successors in Omega: One Is Least and Not a Successor of a Natural Number, the Successor Is Injective, and N Is Closed under Addition and Multiplication §successors, the description of segments above gives $[n+1]=[n]\cup\{n+1\}$. As $n+1\le n$ fails, $n+1\notin[n]$.

Split. Let $m\le n+1$. The intervals $\{m,\dots,n\}$ and $\{n+1,\dots,n+p\}$ are disjoint, since $k\le n$ and $n+1\le k$ would give $n+1\le n$. Both lie in $\{m,\dots,n+p\}$: we have $n\le n+p$ by Arithmetic of Addition on Omega: Recursion Rules, Associativity, Commutativity, Cancellation and Compatibility with the Order §difference, so $m\le k\le n$ implies $m\le k\le n+p$; and $n+1\le k\le n+p$ implies $m\le n+1\le k\le n+p$. Conversely, let $m\le k\le n+p$. By totality, $k\le n$ or $n<k$; in the first case $k\in\{m,\dots,n\}$, and in the second $n+1\le k$, so $k\in\{n+1,\dots,n+p\}$.

Shift. By Arithmetic of Addition on Omega: Recursion Rules, Associativity, Commutativity, Cancellation and Compatibility with the Order §order and Arithmetic of Addition on Omega: Recursion Rules, Associativity, Commutativity, Cancellation and Compatibility with the Order §commutative, $m\le k\le n$ holds if and only if $m+p\le k+p\le n+p$. Hence $\varphi:k\mapsto k+p$ is a map from $\{m,\dots,n\}$ to $\{m+p,\dots,n+p\}$. It is injective, since $k+p=k'+p$ implies $k=k'$ by Arithmetic of Addition on Omega: Recursion Rules, Associativity, Commutativity, Cancellation and Compatibility with the Order §cancellation and commutativity. It is surjective: let $m+p\le j\le n+p$. Since $p\le p+m=m+p$ by Arithmetic of Addition on Omega: Recursion Rules, Associativity, Commutativity, Cancellation and Compatibility with the Order §difference, we get $p\le j$, so by the same clause $j=p+k=k+p$ for some $k\in\mathbb{N}_{0}$; then $m+p\le k+p\le n+p$ gives $m\le k\le n$, and $j=\varphi(k)$. So $\varphi$ is a bijection.

Inclusion. If $m\le n$ and $k\in[m]$, then $k\le m\le n$, so $k\in[n]$. Conversely, let $[m]\subseteq[n]$. If $m=0$, then $m\le n$ by The Order on Omega Is a Well-Order with Membership as Its Strict Order, and Nothing Lies between n and Its Successor §zero-least. Otherwise $m\in\mathbb{N}$ by The Natural Numbers and the Natural Numbers with Zero: Arithmetic, Order, Induction and Recursion §sets, and $m\le m$ gives $m\in[m]\subseteq[n]$, so $m\le n$.