Naive Set Theory: The Natural Numbers

Natural Numbers and Induction


The German mathematician Leopold Kronecker said, "God made the integers, all else is the work of man." The implication is that, if we take the properties of the integers as our starting point, we can derive nearly all the other mathematical concepts of interest. However, the integers can indeed be constructed as the work of man (and woman!). In fact, the even more primitive natural numbers can also be constructed. In this section, we construct the natural numbers via sets call von Neumann ordinals, named after the 20th century polymath John von Neumann.

Successors

First we start by defining the concept of a successor. The successor of a set $S$ is the set $S^+$ and is defined as $S^+= S \cup \{S\}$. For example, if the set $A = \{1, 2, 3\}$, then the successor to $A$ is $A^+ = A \cup \{A\} = \{ 1, 2, 3, \{1, 2, 3\} \}$.

Inductive Sets and von Neumann Ordinals

An inductive set is a set $\omega$ with the following two properties:

  • $\varnothing \in \omega$

  • For all $a \in \omega$, $a^+ \in \omega$

From this definition, we can go about constructing an inductive set, call it $I$. In order to be an inductive set, it must be the case that $\varnothing \in I$. Because $\varnothing \in I$, it follows that $\varnothing^+$ must also be in $I$. By the definition of successor, $\varnothing^+ = \{\varnothing\}$. This in turn implies that $\{\varnothing\}^+ \in I$, and so on. We can plainly see that this pattern goes on indefinitely, and in fact in axiomatic set theory this phenomenon is taken as an axiom. The elements of this set $I$, namely $\varnothing, \varnothing^+, \varnothing^{++}$, and so on, are called the von Neumann ordinals.

However, this set $I$ is not the only possible inductive set. It's left as an exercise to come up with other inductive sets.

The Natural Numbers

natural number is a number that is a member of every inductive set, and the set of all natural numbers is denoted $\mathbb{N}$. The set $\mathbb{N}$ is in fact identical to the set $I$ constructed above. However, for ease of use, the von Neumann ordinals are replaced with more familiar symbols. Namely, $0 = \varnothing, 1 = \varnothing^+, 2 = \varnothing^{++}, 3 = \varnothing^{+++}$, and so on.

It is very important to note that we have only defined the elements of the set of natural numbers, namely the numbers $0, 1, 2, 3, \ldots$ themselves. We have not defined any operations on them, such as addition and multiplication.

Proof by Induction

The Principle of Mathematical Induction, proved below, is a very powerful tool for proving whole oceans of interesting mathematical results. Proofs that take advantage of the Principle of Mathematical Induction are called proofs by induction, and they follow a standard format:

  1. First, proofs by induction often start by stating that the proof will be done by induction. Most folks simply write "Proof by induction."

  2. Next, the proof constructs a subset of the natural numbers, call it $S$, and defines membership in the set as being conditional on the property the proof is seeking to prove. For example, in the exercise below to prove that $0 + n = n$ for all $n \in \mathbb{N}$, we construct a set $S = \{ n \in \mathbb{N} : 0 + n = n \}$. If this subset of $\mathbb{N}$ can be shown to be an inductive set, then the Principle of Mathematical Induction shows that it is in fact equal to $\mathbb{N}$.

  3. In order to show that the set $S$ is inductive, the proof must first demonstrate the truth of a base case. The base case establishes the fact that the $0$ element is in the subset of $\mathbb{N}$ the proof has defined.

  4. In order to finish showing that $S$ is inductive, the proof must prove the inductive step. The inductive step is equivalent to showing that $n \in S$ implies that $n^+ \in S$.

  5. Once the preceding three steps have been carried out, the constructed set $S$ has been shown to be an inductive subset of $\mathbb{N}$ and therefore, by the Principle of Mathematical Induction, equal to $\mathbb{N}$. This means that the statement that conditioned membership in $S$ on the truth of some proposition is true for all natural numbers. Continuing the example from step 2, it would show that $0 + n = n$ is true for all $n \in \mathbb{N}$. This completes the proof.

Note on Induction

  • The format given here is particular to the set-theoretic construction of the natural numbers. Many approaches to induction do not start this close to the foundations of mathematics and are instead formulated entirely in terms of arithmetic operations on the natural numbers or integers. For example, a more common proof by induction will show that some fixed starting case is true, then show that if some case $n$ is true then case $n+1$ must be true, then conclude that the desired result is has been demonstrated "by induction." This format is far easier to work with than the sets-and-successors format defined here. In fact, one of the problem below shows that $a^+ = a + 1$, thus providing a syntactic escape hatch from the successor notation.

  • Learning how to prove the inductive step for a proof by induction is often tricky, as it takes the logical form of proving $A \implies B$. One common mistake is to think that proving $A \implies B$ requires proving $A$ itself first. In fact, one only need show that if $A$ is true, that is, if we assume it to be true, then $B$ must necessarily be true as a result. In the inductive step portion of a proof by induction, $A$ is $n \in S$, and $B$ is $n^+ \in S$. Therefore, it is not only "okay" but in fact logically correct to assume the truth of $n \in S$. And in case you're wondering how $A$ itself gets proven, that's what the base case takes care of. Combining the two shows that $0$ is in fact in $S$, which by the inductive step means that $0^+=1 \in S$, which by the inductive step again means $1^+=2 \in S$, and bada bing bada boom $S = \mathbb{N}$.


Problems

  1. Write out the von Neumann ordinals for the numbers $0$ through $4$ in terms of their sets by recursively applying the successor operator.

    $0 = \varnothing$

    $1 = \{\varnothing\}$

    $2 = \{\varnothing, \{\varnothing\}\}$

    $3 = \{\varnothing, \{\varnothing\}, \{\varnothing, \{\varnothing\} \} \}$

    $4 = \{ \varnothing, \{\varnothing\}, \{ \varnothing, \{\varnothing\} \}, \{ \varnothing, \{\varnothing\}, \{ \varnothing, \{\varnothing\}\} \} \}$

    Show Answer
  2. Write out the set representations of the natural numbers $0$ through $4$ in terms of natural numbers, rather than empty sets, as applicable.

    $0 = \varnothing$

    $1 = 0^+ = 0 \cup \{0\} = \varnothing \cup \{0\} = \{0\}$

    $2 = 1^+ = 1 \cup \{1\} = \{0\} \cup \{1\} = \{0, 1\}$

    $3 = 2^+ = 2 \cup \{2\} = \{0, 1\} \cup \{2\} = \{0, 1, 2\}$

    $4 = 3^+ = 3 \cup \{3\} = \{0, 1, 2\} \cup \{3\} = \{0, 1, 2, 3\}$

    Show Answer
  3. Construct an inductive set that is not equal to $\mathbb{N}$.

    We construct the "alphanumerals", denoted $A$, as an inductive set. Let $0 = \varnothing \in A$ and let $a \in A$, and further stipulate that if there is some $x \in A$, then $x^+ \in A$. Then by definition we see both that $\varnothing \in A$ and that every element in $A$ has a successor, which means that $A$ is an inductive set. However, the elements $a, a^+, a^{++}, \ldots$ are clearly not elements of $\mathbb{N}$. Therefore $A \neq \mathbb{N}$.

    Show Answer
  4. Principle of Mathematical Induction: Prove that every inductive subset of $\mathbb{N}$ is itself $\mathbb{N}$.

    Let $A \subseteq \mathbb{N}$ such that $A$ is inductive. By the first property of inductive sets, $\varnothing \in A$. Then by the second property of inductive sets, $\varnothing^+ \in A$, which in turn implies $\varnothing^{++} \in A$. Thus $A = \{0, 1, 2, \ldots\} = \mathbb{N}$.

    Note: If you've heard of induction before, this statement of the theorem and its proof may seem unfamiliar. The induction principle is usually stated in terms like "If $\{0,\ldots,n\} \subseteq A \implies n+1 \in A$, then $A = \mathbb{N}$." Once we define some arithmetic operations like addition for $\mathbb{N}$, we'll see that these two statements and proofs are equivalent.

    Show Answer