Proof of Induction for Predicative Formulas, and the Order of ℕ below 1 and below n+1

Proof of (i). Let $\psi$ be a predicative formula expressing $\varphi$, as in Conditions Expressed by a Predicative Formula, and Guards (ii): its free variables are among $x$ and the parameters of $\varphi$, and, the parameters having their fixed values, for every set $a$ the formula $\psi$ holds with $a$ assigned to $x$ if and only if $\varphi(a)$. Taking $\mathbb{N}$ as an additional parameter, let $S=\{x\in\mathbb{N}:\psi\}$ be the class of Class Abstraction: the Class of All Sets Satisfying a Predicative Formula (ii), that is, $\{x:x\in\mathbb{N}\wedge\psi\}$; by Class Abstraction: the Class of All Sets Satisfying a Predicative Formula (i), for every set $a$, $a\in S$ if and only if $a\in\mathbb{N}$ and $\psi$ holds with $a$ assigned to $x$, that is, if and only if $a\in\mathbb{N}$ and $\varphi(a)$; here $\varphi(a)$, the condition $\varphi$ with $x$ given the value of a parameter whose fixed value is the set $a$, is again expressed by a predicative formula by Substituting Variables and Set Parameters into Predicative Formulas, Extending Assignments, and Finiteness (i), with $n=1$ and $m=0$. In particular every element of $S$ lies in $\mathbb{N}$, so $S\subseteq\mathbb{N}$ by Subclasses and Subsets (i).

We have $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 (ii) and $\varphi(1)$ by hypothesis, so $1\in S$. Let $n\in S$. Then $n\in\mathbb{N}$ and $\varphi(n)$, so $\varphi(n+1)$ by hypothesis; and $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 (vi), as $1\in\mathbb{N}$. Hence $n+1\in S$. By Arithmetic and Order of the Natural Numbers (xiii), $S=\mathbb{N}$. So every $n\in\mathbb{N}$ lies in $S$, and $\varphi(n)$ holds.

Proof of (ii). Let $k\in\mathbb{N}$. By Arithmetic and Order of the Natural Numbers (x), $1\le k$, so $1<k$ or $1=k$ by Arithmetic and Order of the Natural Numbers (vi). By Arithmetic and Order of the Natural Numbers (vii), applied to $k$ and $1$, exactly one of $k<1$, $k=1$ and $1<k$ holds; as one of the last two holds, $k<1$ fails.

Proof of (iii). Let $k,n\in\mathbb{N}$; then $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 (vi).

First assertion. As $\mathbb{N}\subseteq\mathbb{N}_{0}$ by The Natural Numbers and the Natural Numbers with Zero: Arithmetic, Order, Induction and Recursion (ii) (indeed $\mathbb{N}=\omega\setminus\{0\}\subseteq\omega$ by The Set of Natural Numbers and the Number One (i)), $k$ and $n$ lie in $\omega=\mathbb{N}_{0}$, and the successor $S(n)$ of $n$ equals $n+1$ 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 (v). By The Order on Omega Is a Well-Order with Membership as Its Strict Order, and Nothing Lies between n and Its Successor (iv), $k<S(n)$ if and only if $k\le n$; so $k<n+1$ if and only if $k\le n$. By Arithmetic and Order of the Natural Numbers (vi), applied to $k$ and $n$, $k\le n$ if and only if $k<n$ or $k=n$. Hence $k<n+1$ if and only if $k<n$ or $k=n$.

Second assertion. By Arithmetic and Order of the Natural Numbers (vi), applied to $k$ and $n+1$, $k\le n+1$ holds if and only if $k<n+1$ or $k=n+1$; by the first assertion, this holds if and only if $k<n$, $k=n$ or $k=n+1$. By Arithmetic and Order of the Natural Numbers (vi), applied to $k$ and $n$, $k<n$ or $k=n$ holds if and only if $k\le n$. So $k\le n+1$ if and only if $k\le n$ or $k=n+1$.