# Set theoretic construction of the natural numbers

I'm trying to tie some loose ends here. My lecturer didn't bother to go into details, so I have to work it out myself. I usually hate to be pedantic, but these questions have been bugging me for a while.

First, what's the proper definition of the natural numbers? The one given to me is: "the smallest set such that $\emptyset\in N$ and $x\in N\implies x\cup\lbrace x\rbrace\in N$". This definition does not seem rigorous to me. What does "smallest" mean here? Does it mean that no proper subset have the same property? And how to prove the existence of such set (under ZFC)? Lastly, how to prove this set satisfies Peano's axioms, especially the last axiom (about induction)?

Next, how to prove that the relation $<$ is a total order? The definition is $x<y\Leftrightarrow x\subset y$. I was thinking of changing the definition into "the transitive closure of $\lbrace(n,n')|n\in N\rbrace$" (to avoid the set theory stuffs), but it's still difficult to prove that it's a total order.

Lastly, how to prove the well ordering principle? I suspect this would be easy after proving the previous statement though.

Edit: Why didn't the curly bracket appear? I'll use the square bracket instead.

-
You prove the well ordering principle with the principle of mathematical induction (and vice versa). – The Chaz 2.0 Sep 30 '11 at 3:22
\left \{ abc \right \} (in dollar signs) gives { abc } – The Chaz 2.0 Sep 30 '11 at 3:25
I got out of bed to write an answer, and by the time I get to the computer two good answers have appeared. Instead I fixed the braces (which did not work due to the quotation marks, I suspect.) – Asaf Karagila Sep 30 '11 at 3:37
I also can't figure out why you are trying "to avoid the set theory stuff" in a set theoretic construction. – Asaf Karagila Sep 30 '11 at 3:43
@TheChaz: If only things were that simple... :-) – Asaf Karagila Sep 30 '11 at 4:38

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$

-
There's a more in-depth discussion of this,with some nice historical notes,in Herbert Enderton's classic ELEMENTS OF SET THEORY. – Mathemagician1234 Sep 30 '11 at 3:37
@Jason: Let $C=\{x\mid\varphi(x)\}$ be some class. Define the intersection of the class as $\bigcap C=\{z\mid\forall x(\varphi(x)\rightarrow z\in x)\}$. Of course this might be another class, but due to the axiom of infinity this has to be restricted by a set. – Asaf Karagila Sep 30 '11 at 3:40
@Jason, the Axiom of Replacement (or even Comprehension) guarantees that every subclass of a set is itself a set, so any wild intersection is a set as soon as one of the intersectees is. – Henning Makholm Sep 30 '11 at 3:46
@Jason: As Henning said. This is exactly the axiom of replacement. A subclass of a set is a set. My point is that the intersection over a class can be defined syntactically, since classes are syntactic objects (i.e. formulae, and not elements of the universe) – Asaf Karagila Sep 30 '11 at 3:55
Thanks, Arturo! Okay, this has cleared my doubts about the construction. :) Also, thanks for the reference, Mathemagician1234! – dkdsj93 Sep 30 '11 at 4:00

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.

-
When you say any number of sets it is important to add that this any includes proper classes. – Asaf Karagila Sep 30 '11 at 3:34
@Asaf, yes -- or just take the intersection with the-set-that-the-Axiom-of-Infinity-gives-us separately for each candidate before taking the big intersection. Then the big intersection is taken over a subset of the power set of the-set-that-the-Axiom-of-Infinity-gives-us. (Which is useful if we're working in a theory without proper classes, such as ZFC). – Henning Makholm Sep 30 '11 at 3:44
Of course, I just think it is important to note (even if in the comments) that there is a very large collection whose intersection is still this set. – Asaf Karagila Sep 30 '11 at 3:57
Thanks. The problem is, I'm not really sure yet about the relation <. We need to prove that it's a total order before proving that it's a well order, correct? – dkdsj93 Sep 30 '11 at 4:01