Proof of Arithmetic and Order of the Natural Numbers

Let $0$ be as in The Class Omega of Natural Numbers with Zero §zero, and let $S(x)$ denote the successor of a set $x$.

Preliminaries. By The Set of Natural Numbers and the Number One §naturals, The Boolean Operations on Classes, Disjointness, and the Universal Class §operations and The Empty Set, the Unordered Pair and the Singleton §singleton, a set $x$ lies in $\mathbb{N}$ if and only if $x\in\omega$ and $x\neq0$. In particular $\mathbb{N}\subseteq\omega$, so the results on $\omega$ cited below apply to $a$, $b$ and $c$, and $a\neq0$, $b\neq0$, $c\neq0$. 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 Well-Orders on a Set §well-order, $\le$ is a total order on the set $\omega$ (a set by Omega Is the Least Inductive Class: It Is a Set, Induction from Zero, the Peano Properties, and Transitivity §set), so by Partial and Total Orders on a Set and the Associated Strict Relation §total it is a partial order on $\omega$, and by The Order on Omega Is a Well-Order with Membership as Its Strict Order, and Nothing Lies between n and Its Successor §strict the class $<$ is its associated strict relation. Hence Uniqueness of Least and Greatest Elements, Properties of the Strict Order, and Trichotomy for Total Orders applies to $\le$ and $<$ on $\omega$. 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 §closed, the sums and products of elements of $\mathbb{N}$ formed below lie in $\mathbb{N}\subseteq\omega$.

Clause commutative. By Arithmetic of Addition on Omega: Recursion Rules, Associativity, Commutativity, Cancellation and Compatibility with the Order §commutative and Arithmetic of Multiplication on Omega: Recursion Rules, Distributivity, Associativity, Commutativity, No Zero Divisors, Cancellation and Compatibility with the Order §commutative.

Clause associative. By Arithmetic of Addition on Omega: Recursion Rules, Associativity, Commutativity, Cancellation and Compatibility with the Order §associative and Arithmetic of Multiplication on Omega: Recursion Rules, Distributivity, Associativity, Commutativity, No Zero Divisors, Cancellation and Compatibility with the Order §associative.

Clause distributive. By Arithmetic of Multiplication on Omega: Recursion Rules, Distributivity, Associativity, Commutativity, No Zero Divisors, Cancellation and Compatibility with the Order §distributive.

Clause one. 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, $a\cdot1=a$. Since $1=S(0)$ by The Set of Natural Numbers and the Number One §one, Arithmetic of Multiplication on Omega: Recursion Rules, Distributivity, Associativity, Commutativity, No Zero Divisors, Cancellation and Compatibility with the Order §one gives $1\cdot a=S(0)\cdot a=a$.

Clause cancellation. If $a+c=b+c$, then $c+a=c+b$ by the clause commutative above, so $a=b$ by Arithmetic of Addition on Omega: Recursion Rules, Associativity, Commutativity, Cancellation and Compatibility with the Order §cancellation. If $a\cdot c=b\cdot c$, then $c\cdot a=c\cdot b$ by the clause commutative above, and since $c\neq0$, Arithmetic of Multiplication on Omega: Recursion Rules, Distributivity, Associativity, Commutativity, No Zero Divisors, Cancellation and Compatibility with the Order §cancellation gives $a=b$.

Clause partial-order. Since $\le$ is a partial order on $\omega$ and $a,b,c\in\omega$, $a\le a$ by Reflexive, Symmetric, Antisymmetric and Transitive Relations on a Set §reflexive; $a\le b$ and $b\le a$ imply $a=b$ by Reflexive, Symmetric, Antisymmetric and Transitive Relations on a Set §antisymmetric; and $a\le b$ and $b\le c$ imply $a\le c$ by Reflexive, Symmetric, Antisymmetric and Transitive Relations on a Set §transitive. Further, $a\le b$ if and only if $a<b$ or $a=b$ by Uniqueness of Least and Greatest Elements, Properties of the Strict Order, and Trichotomy for Total Orders §weak-strict, and $a<b$ and $b<c$ imply $a<c$ by Uniqueness of Least and Greatest Elements, Properties of the Strict Order, and Trichotomy for Total Orders §strict-transitive.

Clause trichotomy. Since $\le$ is total on $\omega$, this is Uniqueness of Least and Greatest Elements, Properties of the Strict Order, and Trichotomy for Total Orders §trichotomy.

Clause difference. Suppose $a<b$. By The Order on Omega Is a Well-Order with Membership as Its Strict Order, and Nothing Lies between n and Its Successor §strict, $a\le b$ and $a\neq b$, so by Arithmetic of Addition on Omega: Recursion Rules, Associativity, Commutativity, Cancellation and Compatibility with the Order §difference there is $d\in\omega$ with $a+d=b$. If $d=0$, then $b=a+0=a$ by Arithmetic of Addition on Omega: Recursion Rules, Associativity, Commutativity, Cancellation and Compatibility with the Order §zero, contradicting $a\neq b$; so $d\neq0$, that is, $d\in\mathbb{N}$ by the preliminaries. Conversely, let $d\in\mathbb{N}$ with $b=a+d$. Since $d\in\omega$, Arithmetic of Addition on Omega: Recursion Rules, Associativity, Commutativity, Cancellation and Compatibility with the Order §difference gives $a\le b$. If $a=b$, then $a+d=a=a+0$ by Arithmetic of Addition on Omega: Recursion Rules, Associativity, Commutativity, Cancellation and Compatibility with the Order §zero, so $d=0$ by Arithmetic of Addition on Omega: Recursion Rules, Associativity, Commutativity, Cancellation and Compatibility with the Order §cancellation, contradicting $d\in\mathbb{N}$; so $a\neq b$, and $a<b$ by The Order on Omega Is a Well-Order with Membership as Its Strict Order, and Nothing Lies between n and Its Successor §strict.

Clause order. By Arithmetic of Addition on Omega: Recursion Rules, Associativity, Commutativity, Cancellation and Compatibility with the Order §order with $k=c$, $a<b$ if and only if $c+a<c+b$, and $a\le b$ if and only if $c+a\le c+b$; by the clause commutative above, $c+a=a+c$ and $c+b=b+c$, which gives both forms for addition. Since $c\neq0$, Arithmetic of Multiplication on Omega: Recursion Rules, Distributivity, Associativity, Commutativity, No Zero Divisors, Cancellation and Compatibility with the Order §order with $k=c$ gives $a<b$ if and only if $c\cdot a<c\cdot b$, that is, by the clause commutative above, if and only if $a\cdot c<b\cdot c$. For the weak form, $a=b$ implies $a\cdot c=b\cdot c$, and $a\cdot c=b\cdot c$ implies $a=b$ by the clause cancellation above; so $a=b$ if and only if $a\cdot c=b\cdot c$. Hence, using Uniqueness of Least and Greatest Elements, Properties of the Strict Order, and Trichotomy for Total Orders §weak-strict twice (for $a,b\in\omega$ and for $a\cdot c,b\cdot c\in\omega$), $a\le b$ holds if and only if $a<b$ or $a=b$, if and only if $a\cdot c<b\cdot c$ or $a\cdot c=b\cdot c$, if and only if $a\cdot c\le b\cdot c$.

Clause least. 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 §one.

Clause successor. Since $a\in\omega$, $a+1=S(a)$ 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. Then $a<S(a)=a+1$ by The Order on Omega Is a Well-Order with Membership as Its Strict Order, and Nothing Lies between n and Its Successor §successor. Since $a\in\mathbb{N}$, $a+1=S(a)\neq1$ 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 §peano. If $d\in\mathbb{N}$ satisfied $a<d$ and $d<a+1=S(a)$, then $d\in\omega$ would contradict The Order on Omega Is a Well-Order with Membership as Its Strict Order, and Nothing Lies between n and Its Successor §successor-adjacent.

Clause predecessor. If $a\neq1$, 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 §predecessor gives $d\in\mathbb{N}$ with $a=S(d)$, and $S(d)=d+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 §plus-one, since $d\in\omega$.

Clause induction. Let $A$ be as in the clause. For $n\in A$ we have $n\in\mathbb{N}\subseteq\omega$, so $S(n)=n+1\in A$ 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 and the hypothesis on $A$. Together with $1\in A$ and $A\subseteq\mathbb{N}$, The Principle of Induction for the Natural Numbers Starting at One §induction gives $A=\mathbb{N}$.

Clause digits. By Digits and Decimal Numerals §digits, $2=S(1)$, $3=S(2)$, $4=S(3)$, $5=S(4)$, $6=S(5)$, $7=S(6)$, $8=S(7)$ and $9=S(8)$, and each of $1,\dots,9$ denotes an element of $\omega$. So each of $2,\dots,9$ is $S(k)$ for some $k\in\omega$ and lies 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, and since $S(k)=k+1$ for $k\in\omega$ 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, $2=1+1$, $3=2+1$, $4=3+1$, $5=4+1$, $6=5+1$, $7=6+1$, $8=7+1$ and $9=8+1$. By Digits and Decimal Numerals §numerals, the numeral $10$ (with $k=1$, $d_{1}=1$, $d_{0}=0$) abbreviates $(1\cdot S(9))+0$. Since $S(9)\in\omega$ by Omega Is the Least Inductive Class: It Is a Set, Induction from Zero, the Peano Properties, and Transitivity §inductive and $1=S(0)$ by The Set of Natural Numbers and the Number One §one, $1\cdot S(9)=S(9)$ by Arithmetic of Multiplication on Omega: Recursion Rules, Distributivity, Associativity, Commutativity, No Zero Divisors, Cancellation and Compatibility with the Order §one, and $S(9)+0=S(9)$ by Arithmetic of Addition on Omega: Recursion Rules, Associativity, Commutativity, Cancellation and Compatibility with the Order §zero; so $10=S(9)$. Hence $10\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, and $10=S(9)=9+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 §plus-one.

Clause well-order. Let $s$ be a subset of $\mathbb{N}$ with at least one element. Since $\mathbb{N}\subseteq\omega$, $s$ is a subset of $\omega$ by Subclasses and Subsets §subclass. 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 Well-Orders on a Set §well-order, $s$ has a least element $m$ with respect to $\le$, that is, by Bounds, Least and Greatest Elements, Suprema and Infima for a Partial Order §least, $m\in s$ and $m\le v$ for every $v\in s$.