Set theoretic construction of the natural numbers

Proper definition of the natural numbers.

Here's one taken (from memory) from Halmos's Naive Set Theory.

Definition. Given a set $x$, we define $x^+$, the successor of $x$, to be the set $x\cup\{x\}$.

If $x$ is a set, $x^+$ is a set: $\{x\}$ is an element of the power set of $X$, so $x^+$ is a subset of $x\cup\mathcal{P}(x)$, hence a set (by the Axiom of Powers, Axiom of Unions, and Axiom of Separation).

Definition. A set $S$ is said to be inductive if and only if $\emptyset\in S$ and for every $x$, if $x\in S$ then $x^+\in S$.

Axiom of Infinity. There exists at least one inductive set.

Now, let $S$ be any inductive set. Let $$\mathbb{N}_S = \bigcap\{A\subseteq S\mid A\text{ is inductive}\}.$$ This is a set, since the family is a subsets of $\mathcal{P}(S)$, and so its intersection is a set.

Lemma. The intersection of any nonempty collection of inductive sets is inductive.

Proof. Suppose $\{S_i\}$ is a nonempty family of inductive sets, and let $S=\cap S_i$ Then $\emptyset\in S_i$ for each $i$, hence $\emptyset\in S$; and if $x\in S$, then $x\in S_i$, for each $i$; hence (since each $S_i$ is inductive), $x^+\in S_i$ for each $i$, and thus $x^+\in S$. Thus, $S$ is inductive. $\Box$

Corollary. If $S$ is inductive, then $\mathbb{N}_S$ is inductive. Moreover, if $B$ is any inductive subset of $S$, then $\mathbb{N}_S\subseteq B$.

Theorem. If $S$ and $T$ are two inductive sets, then $\mathbb{N}_S = \mathbb{N}_T$.

Proof. Consider $\mathbb{N}_T\cap S$; this is an inductive subset of $S$, hence $\mathbb{N}_S\subseteq \mathbb{N}_T\cap S\subseteq \mathbb{N}_T$. Symmetrically, since $\mathbb{N}_S\cap T$ is inductive, then $\mathbb{N}_T\subseteq \mathbb{N}_S\cap T\subseteq\mathbb{N}_S$. Thus, $\mathbb{N}_S=\mathbb{N}_T$. $\Box$

Definition. $\mathbb{N}$ is the set $\mathbb{N}_S$, where $S$ is any inductive set.

This set is well defined, since by the theorem above it does not matter what inductive set we start with, we always get the same set $\mathbb{N}$; and there is at least one inductive set by the Axiom of Infinity.

Theorem. If $S$ is any inductive set, then $\mathbb{N}\subseteq S$; that is, $\mathbb{N}$ is the "smallest" inductive set, in the sense of set inclusion.

Proof. If $S$ is any inductive set, then $\mathbb{N}=\mathbb{N}_S\subseteq S$. $\Box$

Now let $0=\emptyset$, and let $s(x) = x^+$ for every $x$.

Theorem. (The Peano Axioms) $\mathbb{N}$ satisfies the following:

1. $0\in \mathbb{N}$.
2. If $n\in \mathbb{N}$, then $s(n)\in\mathbb{N}$.
3. For all $n\in\mathbb{N}$, $s(n)\neq 0$.
4. If $s(n)=s(m)$, then $n=m$.
5. If $S\subseteq \mathbb{N}$ is such that $0\in S$ and if $n\in S$ then $s(n)\in S$, then $S=\mathbb{N}$.

Proof. Since $\mathbb{N}$ is inductive, 1 and 2 are satisfied. 3 is satisfied because by definition, $n\in s(n)$, hence $s(n)\neq\emptyset=0$. 5 is satisfied because the given conditions imply that $S$ is inductive, and therefore $\mathbb{N}\subseteq S$. Since we already have $S\subseteq \mathbb{N}$, then $S=\mathbb{N}$ holds.

The only difficulty is property 4. This requires some auxiliary results:

Lemma 1. If $n\in\mathbb{N}$, and $m\in n$, then $m\subseteq n$.

Proof. Let $S=\{n\in\mathbb{N}\mid \text{for all }m\in n, m\subseteq n\}$. Then $0\in S$, since $0=\emptyset$ satisfies the property by vacuity. Assume that $k\in S$, and let $m\in s(k) = k\cup\{k\}$. If $m\in k$, then since $k\in S$ we have $m\subseteq k\subseteq s(k)$. If $m\notin k$, then $m\in\{k\}$, hence $m=k$, and $m=k\subseteq k\cup\{k\}=s(k)$. Thus, $s(k)\in S$.

We conclude that $S$ is an inductive subset of $\mathbb{N}$, and therefore that $S=\mathbb{N}$. $\Box$

Lemma 2. If $n\in\mathbb{N}$ and $m\in n$, then $n\not\subseteq m$.

Proof. Let $S=\{n\in\mathbb{N}\mid\text{for all }m\in n, n\not\subseteq m\}$. Then $0\in S$, since it satisfies the condition by vacuity.

Assume that $k\in S$. If $m\in s(k)=k\cup\{k\}$, then either $m\in k$, in which case $k\not\subseteq m$, hence $s(k)\not\subseteq m$ (since $k\subseteq s(k)$); or else $m=k$. But since $k\in S$, then $k\notin k$ (for $k\subseteq k$, so $k\in k$ would contradict that $k\in S$). Since $k\in s(k)$, then $s(k)\not\subseteq k=m$. Thus, if $k\in S$ then $s(k)\in S$. Hence $S$ is an inductive subset of $\mathbb{N}$, so $S=\mathbb{N}$. $\Box$

We are now ready to prove property 4. Assume that $s(n)=s(m)$. Since $m\in s(m)=s(n) = n\cup \{n\}$, then either $m=n$, or $m\in n$. If $m=n$, we are done. So assume that $m\in n$. Since $n\in s(n)=s(m)$, then $n\in m\cup \{m\}$; since $n\neq m$, then $n\in m$. Thus, $n\in m$, hence $n\subseteq m$; but $m\in n$, contradicting Lemma 2. This contradiction arises from assuming that $m\in n$. Therefore, $m\notin n$, so $m=n$, hence $\mathbb{N}$ satisfies the fourth Peano axiom. $\Box$

Proof that $\lt$ is a total order on $\mathbb{N}$.

(I'm more used to the definition $n\lt m\Longleftrightarrow n\in m$, but I'll use your definition with proper inclusion)

We want to prove that if $n,m\in\mathbb{N}$, then either $n=m$, $n\subset m$, or $m\subset n$.

Lemma. Let $n\in \mathbb{N}$. Then either $n=0$, or there exists $k\in\mathbb{N}$ such that $n=s(k)$.

Proof. Let $S=\{n\in\mathbb{N}\mid n=0\text{ or }n=s(k)\text{ for some }k\in\mathbb{N}\}$.

Then $0\in S$; if $k\in S$, $s(k)\in S$ (since $s(k)$ is a successor). Thus, $S$ is inductive, hence $S=\mathbb{N}$. $\Box$

Lemma. Let $k,n\in\mathbb{N}$. If $k\subset n$, then $s(k)\subseteq n$.

Proof. Let $S=\{n\in\mathbb{N}\mid \text{if }k\subset n\text{ then }s(k)\subseteq n\}$.

Then $0\in S$ by vacuity. If $n\in S$, let $k\subset s(n)=n\cup\{n\}$.

If $k\subset n$, then $s(k)\subseteq n\subset s(n)$. If $k=n$, then $s(k)=s(n)$. The only other possibility is that $n\in k$. But since $k$ is a natural number, then $n\in k$ implies $n\subseteq k$. But $n\subseteq k\subset n\cup\{n\}$ is impossible. Hence, $k\subset s(n)$ simplies $s(k)\subseteq s(n)$. This proves $S$ is inductive, hence $S=\mathbb{N}$.

Finally, fix $m$, and let $S=\{n\in\mathbb{N}\mid m\subseteq n\text{ or }n\subset m\}$.

Then $0\in S$: if $m=\emptyset$, then $m\subseteq 0$; if $m\neq\emptyset$, then $\emptyset\subset m$.

Assume that $k\in S$. If $m\subseteq k$, then $m\subseteq s(k)$. If $k\subset m$, then by the Lemma $s(k)\subseteq m$. If $s(k)=m$, then $s(k)\in S$. If $s(k)\subset m$, then $s(k)\in S$. Either way, $S$ is inductive, hence $S=\mathbb{N}$. Therefore, $\lt$ is a trichotomic relation on $S$.

Proof of the Well Ordering Principle

Lemma. If $n\in\mathbb{N}$, then there does not exist $k\in\mathbb{N}$ such that $n\lt k\lt s(n)$.

Proof. It is impossible to have $n\subset k\subset n\cup\{n\}$. $\Box$

Well Ordering Principle. If $A\subseteq\mathbb{N}$ and $A\neq\emptyset$, then $A$ has a smallest element.

Proof. Let $A\neq\emptyset$, $A\subseteq \mathbb{N}$. Let $S=\mathbb{N}-A$.

Let $S'= \{n\in\mathbb{N}\mid n\in S\text{ and for all }k,\text{ if }k\lt n\text{ then }k\in S\}$. Since $S'\subseteq S\neq\mathbb{N}$, then $S'$ is not inductive. Therefore, either $0\notin S'$, or else there exists $k\in S'$ such that $s(k)\notin S'$.

If $0\notin S'$, then since for all $k\lt 0$, $k\in S$, it follows that $0\notin S$. Therefore, $0\in A$. Since $0$ is the smallest element of $\mathbb{N}$, it is also the smallest element of $A$ and we are done.

Assume then that there exist $k\in \mathbb{N}$ such that $k\in S'$ but $s(k)\notin S'$. Then $k\in S$ and for all $n\in\mathbb{N}$, if $n\lt k$ then $n\in S$. That means that for all $n\in\mathbb{N}$, if $n\lt s(k)$, then $n\in S$ (for $n\lt s(k)$ implies $n\leq k$ by the Lemma, and so either $n=k\in S$ or $n\lt k$ hence $n\in S$ since $k\in S'$). That means that because $s(k)\notin S'$, it must be because $s(k)\notin S$. Thus, $s(k)\in A$. However, as we have already seen, if $n\lt s(k)$, then $n\in S$, hence $n\lt s(k)\Rightarrow n\notin A$. Thus, $n\in A\Rightarrow s(k)\leq n$, which proves that $s(k)$ is the smallest element of $A$. $\Box$

If you have two sets such that each of them satisfies the condition $\emptyset\in N$ and $x\in N\Rightarrow x\cup\{x\}\in N$, then the intersection of the two sets satisfies the same property. In fact this holds not just for the intersection between two sets, but for the intersection between any number of sets. So $\mathbb N$ can be defined as the intersection of all sets that staisfy the condition. That there is at least one set that satisfies it is usually an explicit axiom of set theory -- the Axiom of Infinity.

This definition of $\mathbb N$ directly implies that mathematical induction works. Namely, assume that $A$ is a subset of $\mathbb N$ such that $0\in A$ and $\forall n\in A: n+1\in A$. That means exactly that $A$ is one of the sets we intersected to make $\mathbb N$ in the first place. So $A$ is both a subset of $\mathbb N$ and a superset of $\mathbb N$, thus it must be $\mathbb N$ itself.

Then prove that long induction works -- essentially because $a<b+1$ if and only if $a=b$ or $a<b$.

Finally, we can prove well-ordering by long induction on $n$: if some set $B$ of natural numbers contains $n$, then it contains a least element.