Set Theory

The Natural Numbers

Table of contents

The Axiom of Infinity

The natural numbers are the mathematical object that most connects the world of mathematics to the real world. No matter how we define an axiom system, if \(2\) does not come immediately after \(1\), then our system is wrong in some sense. There are several things that we simply expect to be true about numbers, just by observing the way reality works. The role of this part is to formalize all those assumptions that we usually make without devoting thought to them. We will begin all this by defining what it means to be “the next number.”

Definition:

Let \(n\) be a set. Then the set \(n\cup\{n\}\) is called the successor of \(n\), and is denoted \(S(n)\) or \(n^{+}\).

Definition:

Let \(A\) be a set. Then \(A\) is called inductive if \(\emptyset\in A\), and for every \(x\in A\), \(S(x)\in A\).

Definition:

Let \(A,B\) be sets. Then \(B\) is called an inductive subset of \(A\) if it is a subset of \(A\) and is also an inductive set.

Claim:

For every inductive set \(I\), write \(N_{I}:=\{n\in I:\text{for every }J\subseteq I\text{ s.t. }J\text{ is inductive, }n\in J\}\). Let \(I_{0},I_{1}\) be inductive sets. Then \(N_{I_{0}}=N_{I_{1}}\).

Proof:

Write \(I:= I_{0}\cap I_{1}\). Since \(\emptyset\in I_{0}\) and \(\emptyset\in I_{1}\), we get \(\emptyset\in I\). Let \(x\in I\). Then \(x\in I_{0}\), hence \(S(x)\in I_{0}\), and \(x\in I_{1}\), hence \(S(x)\in I_{1}\). Therefore \(S(x)\in I\), so \(I\) is an inductive set. Hence \(I\) is an inductive subset of \(I_{0}\).

Let \(n\in N_{I_{0}}\). Since \(I\) is an inductive subset of \(I_{0}\), we get \(n\in I\), and therefore \(N_{I_{0}}\subseteq I\subseteq I_{1}\). Hence \(N_{I_{0}}\) is a subset of \(I_{1}\).

For every inductive \(J_{0}\subseteq I_{0}\), \(\emptyset\in J_{0}\), and therefore \(\emptyset\in N_{I_{0}}\). Let \(n\in N_{I_{0}}\). Then \(n\in I_{0}\), hence \(S(n)\in I_{0}\). For every inductive subset \(J_{0}\subseteq I_{0}\), \(n\in J_{0}\), hence \(S(n)\in J_{0}\). Thus \(S(n)\in N_{I_{0}}\). Therefore \(N_{I_{0}}\) is an inductive subset of \(I_{1}\), and hence \(N_{I_{1}}\subseteq N_{I_{0}}\). By symmetry, \(N_{I_{0}}=N_{I_{1}}\).

Definition:

The set whose existence was proved above is denoted \(\mathbb{N}\), and is called the set of natural numbers, or the naturals for short.

Definition:

Let \(n\in\mathbb{N}\). Then \(n\) is called a natural number, or a natural for short.

Definitions:

1. \(0:=\emptyset\).
2. \(1:= S(0)\).
3. \(2:= S(1)\).
4. \(3:= S(2)\).

Claim (Principle of Induction):

Let \(\varphi\) be a property such that \(\varphi(0)\), and such that for every natural \(n_{0}\in\mathbb{N}\), if \(\varphi(n_{0})\), then \(\varphi(n_{0}^{+})\). Then for every \(n\in\mathbb{N}\), \(\varphi(n)\).

Proof:

Write \(A:=\{n\in\mathbb{N}:\varphi(n)\}\). By definition, \(0\in A\), and for every \(n_{0}\in A\), \(S(n_{0})\in A\). Therefore \(\mathbb{N}\subseteq A\). Since \(A\subseteq\mathbb{N}\), we get \(A=\mathbb{N}\), as desired.

Definition:

Let \(A\) be a set. Then \(A\) is called transitive if for every \(a\in A\), \(a\subset A\).

Claim:

Let \(n\in\mathbb{N}\) be natural. Then \(n\) is transitive.

Proof:

If \(n=0\), the claim holds vacuously. Let \(n_{0}\in\mathbb{N}\) be transitive, and let \(m\in S(n_{0})=n_{0}\cup\{n_{0}\}\). Then \(m\in n_{0}\) or \(m=n_{0}\). If \(m\in n_{0}\), then \(m\subset n_{0}\), and in particular \(m\subset n_{0}\cup\{n_{0}\}=S(n_{0})\). If \(m=n_{0}\), then \(m=n_{0}\subset n_{0}\cup\{n_{0}\}\). Hence \(S(n_{0})\) is transitive, and by the principle of induction all natural numbers are transitive.

Claim:

\(\mathbb{N}\) is transitive.

Proof:

Write \(N:=\{n\in\mathbb{N}:n\subset\mathbb{N}\}\). By definition \(0\in\mathbb{N}\), and of course \(\emptyset\subset\mathbb{N}\), so \(0\in N\). Let \(n\in N\). Then \(n\subset\mathbb{N}\), and also \(\{n\}\subset N\subseteq\mathbb{N}\), so \(n\cup\{n\}\subset\mathbb{N}\). Thus \(S(n)\subset\mathbb{N}\), and hence \(S(n)\in N\). By the principle of induction, \(N=\mathbb{N}\).

Order on the Naturals

In order to continue dealing with numbers and the relations between them, we first have to understand what a relation is. For that we need a way to express an “ordered pair,” like a set with two elements, one of which is defined to be “the first.”

Definition:

Let \(a,b\) be sets. Then the set \(\{\{a\},\{a,b\}\}\) is called an ordered pair, and is denoted \((a,b)\). In addition, for every property \(\varphi\), we write briefly \(\{(a,b):\varphi(a,b)\}:=\{x:\text{ exists }a\text{ and exists }b\text{ s.t. }x=(a,b)\text{ and }\varphi(a,b)\}\).

Definition:

Let \(A,B\) be sets. Then the class \(\{(a,b):a\in A\text{ and }b\in B\}\) is called the Cartesian product of \(A\) and \(B\), and is denoted \(A\times B\).

Claim:

Let \(A,B\) be sets. Then \(A\times B\) is a set.

Proof:

By the axiom of union, \(A\cup B\) is a set, and by the axiom of power set, \(P(P(A\cup B))\) is a set. Therefore, by the axiom of separation, \(\{x\in P(P(A\cup B)):\text{ exists }a\in A\text{ and exists }b\in B\text{ s.t. }x=(a,b)\}\) is a set.

Corollaries:

Let \(A,{\cal B}\) be sets. Then:

1. \(A\times\bigcup{\cal B}=\bigcup\limits _{B\in{\cal B}}\left(A\times B\right)\)
2. \(\bigcup{\cal B}\times A=\bigcup\limits _{B\in{\cal B}}\left(B\times A\right)\)

Corollaries:

Let \(A,B,C\) be sets. Then:

1. \(A\times(B\cup C)=(A\times B)\cup(A\times C)\)
2. \((A\cup B)\times C=(A\times C)\cup(B\times C)\)

Definition:

Let \(A,B\) be sets. Then \(R\subseteq A\times B\) is called a binary relation between \(A\) and \(B\). If \((a,b)\in R\), we also write \(aRb\) briefly.

Definitions:

Let \(A\) be a set, and let \(R\subseteq A\times A\) be a binary relation. Then:

1. \(R\) is called reflexive if for every \(a\in A\), \(aRa\).
2. \(R\) is called symmetric if whenever \(aRb\), also \(bRa\).
3. \(R\) is called antisymmetric if for every \(a\in A\) and every \(b\in A\), if \(aRb\) and \(bRa\), then \(a=b\).
4. \(R\) is called transitive if for every \(a\in A\), \(b\in A\), and \(c\in A\), if \(aRb\) and \(bRc\), then also \(aRc\).

Definition:

Let \(A\) be a set, and let \(\preccurlyeq\subseteq A\times A\) be a reflexive, antisymmetric, and transitive binary relation. Then it is called an order relation, and \(A\) is called an ordered set with respect to \(\preccurlyeq\).

Corollary:

Let \(A\) be a set. Then \(A\) is ordered with respect to \(\{(a,b)\in A\times A:a\subseteq b\}\).

Definitions:

1. \(\le:=\{(n,m)\in\mathbb{N}\times\mathbb{N}:n\in m\text{ or }n=m\}\).
2. \(<:=\{(n,m)\in\mathbb{N}\times\mathbb{N}:n\in m\}\).

Corollary:

Let \(\{m,n\}\subset\mathbb{N}\). Then \(m\in S(n)\) if and only if \(m\le n\).

Claim:

\(\mathbb{N}\) is an ordered set with respect to \(\le\).

Proof:

Reflexivity is clear, and antisymmetry follows directly from the axiom of foundation. We prove transitivity. Let \(k\le m\) be natural numbers. If \(m\le0\), it follows that \(m=0\), so also \(k=0\), and in particular \(k\le0\).

Let \(n_{0}\in\mathbb{N}\) be such that if \(m\le n_{0}\), then \(k\le n_{0}\). Assume \(m\le S(n_{0})\). Then \(m=S(n_{0})\) or \(m\le n_{0}\). If \(m=S(n_{0})\), then \(k\le m=S(n_{0})\). Otherwise \(m\le n_{0}\), so \(k\le n_{0}\), hence \(k\in S(n_{0})\), and in particular \(k\le S(n_{0})\). Therefore, by the principle of induction, for every \(n\in\mathbb{N}\), if \(m\le n\), then \(k\le n\).

Claim:

For every \(n\in\mathbb{N}\), \(0\le n\).

Proof:

For \(n=0\), the claim holds trivially. Let \(n\in\mathbb{N}\) be such that \(0\in n\) or \(n=0\). If \(n=0\), then \(0\in\{0\}=S(0)=S(n)\). Otherwise \(0\in n\), and in particular \(0\in n\cup\{n\}=S(n)\). Thus the claim follows by the principle of induction.

Claim:

Let \(n\in\mathbb{N}\) be natural. Then for every \(m\in n\), \(S(m)\le n\).

Proof:

For \(n=0\), the claim holds vacuously. Let \(n_{0}\in\mathbb{N}\) be such that for every \(m\in n_{0}\), \(S(m)\le n_{0}\). Assume \(m\in S(n_{0})\). Then \(m\le n_{0}\). If \(m=n_{0}\), then \(S(m)=S(n_{0})\), and in particular \(S(m)\le S(n_{0})\). Otherwise \(m\in n_{0}\), and by the choice of \(n_{0}\), \(S(m)\le n_{0}\), hence in particular \(S(m)\le S(n_{0})\). By the principle of induction, the claim is true for every \(n\in\mathbb{N}\).

Definition:

Let \(A\) be a set ordered by \(\preccurlyeq\). If for every \(\{a,b\}\subseteq A\), \(a\preccurlyeq b\) or \(b\preccurlyeq a\), then \(\preccurlyeq\) is called a total order on \(A\), and \(A\) is called linearly ordered with respect to \(\preccurlyeq\).

Claim:

\(\mathbb{N}\) is linearly ordered with respect to \(\le\).

Proof:

Let \(m\in\mathbb{N}\) be natural. \(0\) satisfies \(0\le m\). Let \(n_{0}\in\mathbb{N}\) be such that \(n_{0}\le m\) or \(m\le n_{0}\). If \(m=n_{0}\), then \(m\in S(m)=S(n_{0})\). If \(m\in n_{0}\), then in particular \(m\in n_{0}\cup\{n_{0}\}=S(n_{0})\). If \(n_{0}\in m\), then by the previous claim \(S(n_{0})=m\) or \(S(n_{0})\in m\). Therefore the claim follows by the principle of induction.

Definitions:

Let \(A\) be a set ordered with respect to \(\preccurlyeq\), let \(A_{0}\subseteq A\), and let \(a\in A_{0}\). Then:

1. If for every \(b\in A_{0}\), \(a\preccurlyeq b\), we say that \(a\) is a minimal element of \(A_{0}\) with respect to \(\preccurlyeq\), and denote it by \(\min A_{0}\).
2. If for every \(b\in A_{0}\), \(b\preccurlyeq a\), we say that \(a\) is a maximal element of \(A_{0}\) with respect to \(\preccurlyeq\), and denote it by \(\max A_{0}\).

Claim:

Let \(A\) be linearly ordered with respect to \(\preccurlyeq\), and let \(A_{0}\subseteq A\). Then \(A_{0}\) has at most one minimal element.

Proof:

Assume that minimal elements of \(A_{0}\) exist, and denote two of them by \(a\) and \(b\). From the minimality of \(a\), \(a\preccurlyeq b\). From the minimality of \(b\), \(b\preccurlyeq a\). Therefore by antisymmetry, \(a=b\).

Corollary:

\(\min\mathbb{N}=0\).

Definition:

Let \(A\) be a linearly ordered set with respect to \(\preccurlyeq\). If every nonempty subset \(A_{0}\subseteq A\) has a minimal element with respect to \(\preccurlyeq\), then \(\preccurlyeq\) is called a well-order on \(A\), and \(A\) is called well-ordered with respect to \(\preccurlyeq\).

Claim:

\(\mathbb{N}\) is well-ordered with respect to \(\le\).

Proof:

Let \(N\subseteq\mathbb{N}\) be a subset of the naturals such that for every \(n\in N\), there exists \(m\in N\) with \(m<n\). If \(0\in N\), then there exists \(m\in N\setminus\{0\}\) such that \(m\in0=\emptyset\), a contradiction. Hence \(0\in\mathbb{N}\setminus N\).

Let \(n\in\mathbb{N}\setminus N\) be such that for every \(m<n\), \(m\in\mathbb{N}\setminus N\). If \(S(n)\in N\), then there exists \(m\in N\setminus\{S(n)\}\) such that \(m<S(n)\), meaning \(m\le n\), contradicting the choice of \(n\). Therefore \(S(n)\in\mathbb{N}\setminus N\), and for every \(m<S(n)\), \(m\in\mathbb{N}\setminus N\). By the principle of induction, \(\mathbb{N}\setminus N=\mathbb{N}\), and hence \(N=\emptyset\).

Claim:

Let \(n,m\) be natural numbers such that \(n\subset m\). Then \(n\in m\).

Proof:

Write \(N:= m\setminus n\). This is a nonempty subset of the naturals, so there exists \(n_{0}\in N\) such that for every \(m\in N\), \(n_{0}\le m\). We show that \(n_{0}=n\). If there were \(k\in n_{0}\setminus n\), then in particular \(k\in m\setminus n\), and also \(k\in n_{0}\), contradicting the choice of \(n_{0}\). Hence \(n_{0}\subseteq n\).

On the other hand, if there were \(k\in n\setminus n_{0}\), then by linearity \(n_{0}=k\) or \(n_{0}\in k\). But then by transitivity we would get \(n_{0}\subseteq k\subset n\setminus n_{0}\), a contradiction. Therefore \(n=n_{0}\), and in particular \(n\in m\).