Proof of Parity: Every Natural Number with Zero Is Either Even or Odd, and Parity of Natural Numbers

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, expressions are read in $\mathbb{N}_{0}$ as in The Natural Numbers and the Natural Numbers with Zero: Arithmetic, Order, Induction and Recursion §overloading, and $1=S(0)$ by The Set of Natural Numbers and the Number One §one, where $S$ is the successor; $2\in\mathbb{N}\subseteq\mathbb{N}_{0}$ and $2=1+1$ by Arithmetic and Order of the Natural Numbers §digits. Since $1\in\mathbb{N}=\mathbb{N}_{0}\setminus\{0\}$ by The Natural Numbers and the Natural Numbers with Zero: Arithmetic, Order, Induction and Recursion §sets, $1\neq0$.

Two identities. (I) By Arithmetic of Multiplication on Omega: Recursion Rules, Distributivity, Associativity, Commutativity, No Zero Divisors, Cancellation and Compatibility with the Order §zero, applied to $m=2$, $2\cdot0=0$. (II) Let $k\in\mathbb{N}_{0}$. By Arithmetic of Multiplication on Omega: Recursion Rules, Distributivity, Associativity, Commutativity, No Zero Divisors, Cancellation and Compatibility with the Order §distributive, applied to $2$, $k$ and $1$ in place of $k$, $m$ and $n$, $2(k+1)=2k+2\cdot1$; 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, applied to $n=2$, $2\cdot1=2$; and $2=1+1$, so by Arithmetic of Addition on Omega: Recursion Rules, Associativity, Commutativity, Cancellation and Compatibility with the Order §associative, applied to $2k$, $1$ and $1$ in place of $k$, $m$ and $n$,

$$2(k+1)=2k+(1+1)=(2k+1)+1 .$$

Clause exactly-one: every element is even or odd. Let $E=\{n\in\mathbb{N}_{0}:n\text{ is even or odd}\}$, a set by Sets and Maps: Ordinary Notation §set-builder: by Even and Odd Natural Numbers with Zero §even and Even and Odd Natural Numbers with Zero §odd the property says that $n=2k$ or $n=2k+1$ for some $k\in\mathbb{N}_{0}$, which quantifies over sets only. We show $\mathbb{N}_{0}\subseteq E$ by induction from $0$, that is, by Omega Is the Least Inductive Class: It Is a Set, Induction from Zero, the Peano Properties, and Transitivity §induction applied to the class $E$, the successor of $n\in\mathbb{N}_{0}$ being $S(n)=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 §plus-one. By (I), $0=2\cdot0$ with $0\in\mathbb{N}_{0}$, so $0$ is even by Even and Odd Natural Numbers with Zero §even and $0\in E$. Let $n\in E$. If $n$ is even, $n=2k$ with $k\in\mathbb{N}_{0}$, then $n+1=2k+1$ is odd by Even and Odd Natural Numbers with Zero §odd, with the same $k$. If $n$ is odd, $n=2k+1$ with $k\in\mathbb{N}_{0}$, then $n+1=(2k+1)+1=2(k+1)$ by (II), and $k+1\in\mathbb{N}_{0}$, so $n+1$ is even. In both cases $n+1\in E$. Hence every $n\in\mathbb{N}_{0}$ is even or odd.

Clause exactly-one: not both. Suppose $n\in\mathbb{N}_{0}$ is both even and odd: $n=2k$ and $n=2l+1$ with $k,l\in\mathbb{N}_{0}$. The order of $\mathbb{N}_{0}$ is a well-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, hence a total order by Well-Orders on a Set §well-order, so $k\le l$ or $l\le k$ by Partial and Total Orders on a Set and the Associated Strict Relation §total.

Case $k\le l$. By Arithmetic of Addition on Omega: Recursion Rules, Associativity, Commutativity, Cancellation and Compatibility with the Order §difference, applied to $m=k$ and $n=l$, there is $j\in\mathbb{N}_{0}$ with $k+j=l$. Then, by Arithmetic of Multiplication on Omega: Recursion Rules, Distributivity, Associativity, Commutativity, No Zero Divisors, Cancellation and Compatibility with the Order §distributive (applied to $2$, $k$, $j$) and Arithmetic of Addition on Omega: Recursion Rules, Associativity, Commutativity, Cancellation and Compatibility with the Order §associative (applied to $2k$, $2j$, $1$), $2l+1=(2k+2j)+1=2k+(2j+1)$, while $2k=2k+0$ by Arithmetic of Addition on Omega: Recursion Rules, Associativity, Commutativity, Cancellation and Compatibility with the Order §zero. So $2k+0=2k+(2j+1)$, and Arithmetic of Addition on Omega: Recursion Rules, Associativity, Commutativity, Cancellation and Compatibility with the Order §cancellation, applied to $2k$, $0$ and $2j+1$ in place of $k$, $m$ and $n$, gives $0=2j+1$. By Arithmetic of Addition on Omega: Recursion Rules, Associativity, Commutativity, Cancellation and Compatibility with the Order §zero-sum, applied to $m=2j$ and $n=1$, $1=0$, a contradiction.

Case $l\le k$. By Arithmetic of Addition on Omega: Recursion Rules, Associativity, Commutativity, Cancellation and Compatibility with the Order §difference, applied to $m=l$ and $n=k$, there is $j\in\mathbb{N}_{0}$ with $l+j=k$. Then $2l+2j=2k=2l+1$ by Arithmetic of Multiplication on Omega: Recursion Rules, Distributivity, Associativity, Commutativity, No Zero Divisors, Cancellation and Compatibility with the Order §distributive (applied to $2$, $l$, $j$), and Arithmetic of Addition on Omega: Recursion Rules, Associativity, Commutativity, Cancellation and Compatibility with the Order §cancellation, applied to $2l$, $2j$ and $1$ in place of $k$, $m$ and $n$, gives $2j=1$. If $j=0$, then $2j=2\cdot0=0$ by (I), so $1=0$, a contradiction. Hence $j\neq0$, so $j\in\mathbb{N}_{0}\setminus\{0\}=\mathbb{N}$. Moreover, by Arithmetic of Multiplication on Omega: Recursion Rules, Distributivity, Associativity, Commutativity, No Zero Divisors, Cancellation and Compatibility with the Order §distributive (its second identity, applied to $1$, $1$ and $j$ in place of $m$, $n$ and $k$) and Arithmetic of Multiplication on Omega: Recursion Rules, Distributivity, Associativity, Commutativity, No Zero Divisors, Cancellation and Compatibility with the Order §one (applied to $m=j$, with $S(0)=1$), $2j=(1+1)j=1\cdot j+1\cdot j=j+j$. So $j+j=1$ with $j\in\mathbb{N}$, contradicting A Sum of Natural Numbers Exceeds Each Summand and Is Not One §not-one applied to $a=j$ and $b=j$.

Hence no $n\in\mathbb{N}_{0}$ is both even and odd, which with the paragraph proving that every element is even or odd proves the clause exactly-one.

Clause naturals. Let $n\in\mathbb{N}$; then $n\in\mathbb{N}_{0}$ and $n\neq0$, as $\mathbb{N}=\mathbb{N}_{0}\setminus\{0\}$.

Even. If $n=2q$ with $q\in\mathbb{N}$, then $q\in\mathbb{N}_{0}$, so $n$ is even by Even and Odd Natural Numbers with Zero §even. Conversely, if $n$ is even, $n=2k$ with $k\in\mathbb{N}_{0}$, then $k\neq0$, since $k=0$ would give $n=2\cdot0=0$ by (I); so $q=k\in\mathbb{N}$ and $n=2q$.

Odd. If $n$ is odd, $n=2k+1$ with $k\in\mathbb{N}_{0}$, then $n+1=(2k+1)+1=2(k+1)$ by (II). Here $k+1\neq0$, since $k+1=0$ would give $1=0$ by Arithmetic of Addition on Omega: Recursion Rules, Associativity, Commutativity, Cancellation and Compatibility with the Order §zero-sum applied to $m=k$ and $n=1$; so $q=k+1\in\mathbb{N}_{0}\setminus\{0\}=\mathbb{N}$ and $n+1=2q$. Conversely, let $n+1=2q$ with $q\in\mathbb{N}$. By the clause exactly-one, proved above, $n$ is even or odd. If $n$ were even, $n=2k$ with $k\in\mathbb{N}_{0}$, then $n+1=2k+1$ would be odd by Even and Odd Natural Numbers with Zero §odd, and also even by Even and Odd Natural Numbers with Zero §even, since $n+1=2q$ with $q\in\mathbb{N}\subseteq\mathbb{N}_{0}$; this contradicts the clause exactly-one, proved above, for the element $n+1$ of $\mathbb{N}_{0}$. Hence $n$ is odd.