Mathematical Proof and the Principles of Mathematics/Sets/Natural numbers

Infinity

None of the Zermelo-Fraenkel axioms stated so far assert the existence of an infinite set. The next axiom of ZF set theory does just this.

First we need the concept of an inductive set.

Definition A set $S$ is said to be inductive if $\emptyset \in S$ and $n\cup \{n\}\in S$ for all $n\in S$. For a given set $n$ we call $n\cup \{n\}$ the successor of $n$ and denote it $n^{+}$.

Axiom (Axiom of Infinity)

There exists an inductive set.

Whilst there are many inductive sets, we can prove the following.

Theorem There exists a unique inductive set which is a subset of all inductive sets.

Proof Let $S$ be any inductive set. Such a set exists by the Axiom of Infinity.

Now let us define $W=\{x\in S\;|\;x\in A\;{\mbox{for all inductive sets}}\;A\}$. Note that $W$ is a set by the Axiom Schema of Comprehension.

If $x\in W$ then $x$ is in every inductive set. Thus $W$ is a subset of every inductive set.

Since $\emptyset$ is in every inductive set, $\emptyset \in W$. Moreover, if $x\in W$ then $x$ is in every inductive set and so $x\cup \{x\}$ is in every inductive set. Thus $x\cup \{x\}\in W$. Thus $W$ is inductive.

To show that $W$ is unique, suppose that $W_{1}$ and $W_{2}$ are both inductive sets which are subsets of all inductive sets. In particular we have that $W_{1}\subseteq W_{2}$ and $W_{2}\subseteq W_{1}$. But then by the Axiom of Extensionality, $W_{1}=W_{2}$. $\square$

Definition We denote $\emptyset$ by $0$ and $0^{+}$ by $1$ and $1^{+}$ by $2$, etc. The unique inductive set that is a subset of all inductive sets is denoted $\omega$.

Note that $0=\{\}$, $1=\{0\}$, $2=\{0,1\}$, $3=\{0,1,2\}$.

In general $n=\{0,1,2,\ldots ,n-1\}$ and so $n^{+}=n\cup \{n\}=\{0,1,2,\ldots ,n\}$.

Natural numbers

We have seen that $\omega$ contains $0,1,2,\ldots$. We call these the natural numbers. Note that in other fields of mathematics, the natural numbers do not include $0$, but in set theory it is convenient to include it.

Definition For natural numbers $n$, we shall write $n+1$ instead of $n^{+}=n\cup \{n\}$.

One of the most useful theorems involving natural numbers is the following.

Theorem (Induction) Suppose $P(x)$ is a property of natural numbers for which $P(0)$ holds, and such that for all natural numbers $n$ for which $P(n)$ holds, we have that $P(n+1)$ also holds. Then $P(n)$ holds for every natural number $n$.

Here is a straightforward result that can be proved using induction.

Theorem If $m,n,k\in \omega$ and $m\in n$ and $n\in k$ then $m\in k$.

Proof We prove this by induction on $k$. In other words, we let $P(k)$ be the property that $m\in n$ and $n\in k$ then $m\in k$.

$P(0)$ holds since in this case $k$ is empty and there is nothing to prove.

Now suppose that $P(k)$ holds for some $k\in \omega$. In other words, for that value of $k$ we have that if $m\in n$ and $n\in k$ then $m\in k$.

We wish to show that $P(k+1)$ holds. So assume that $m\in n$ and $n\in k^{+}$. There are two cases.

As $k^{+}=k\cup \{k\}$ there are two cases. The first case is $n\in k$. Bu then by the inductive hypothesis, $m\in k\subset k^{+}=k\cup \{k\}$. Thus $m\in k$.

The other case is $n\in \{k\}$. In this case $n=k$. Thus since $m\in n$ we have $m\in k$. Thus we have shown that in either case $P(k+1)$ holds.

Thus by induction $P(k)$ holds for all natural numbers $k$. $\square$

Here is another simple result that follows by induction.

Theorem Every element of $\omega$ is either $0$ or it is the successor of an element of $\omega$.

Proof We prove this by induction on $k$ where $P(k)$ is the property that $k$ is either $0$ or the successor of some $m\in \omega$.

Clearly $P(0)$ holds. Now suppose that $P(k)$ holds for some $k\in \omega$. Thus either $k=0$ or $k=m^{+}$ for some $m\in \omega$. In both cases $k^{+}$ is the successor of $k$ and thus $P(k+1)$ holds. Thus by induction $P(k)$ holds for all $k\in \omega$. $\square$

A useful variant of induction is the following.

Theorem (Strong induction) Let $P(n)$ be a property of the natural numbers such that if $P(m)$ holds for all $m\in n$ then $P(n)$ holds. Then such a property $P(n)$ holds for all natural numbers $n$.

Proof We prove this result by ordinary induction. Let $Q(n)$ be the property that $P(m)$ holds for every $m\in n$. Clearly $Q(0)$ holds, since there are no elements of $0$ to prove it for.

Now suppose that $Q(n)$ holds for some $n\in \omega$. In other words, $P(m)$ holds for all $m\in n$.

But by assumption this implies that $P(n)$ holds. Thus $P(m)$ holds for all $m\in n\cup \{n\}$. In other words, $Q(n+1)$ holds.

Thus by ordinary induction, $Q(n)$ holds for all natural numbers $n$.

But if $n\in \omega$ then $n^{+}\in \omega$ and so for all natural numbers $n$ we have that $Q(n^{+})$ holds. But $n\in n^{+}$ and so in particular we have that $P(n)$ holds. In other words, we have shown that $P(n)$ holds for all natural numbers $n$. $\square$