Skip to main content

Section 1.13 Natural numbers

In mathematics, pretty much every object is a set. In particular, we will define the natural numbers

\begin{equation*} 0, 1, 2, 3, 4, 5, 6, 7, 8, \ldots \end{equation*}

as a sequence of very special of sets called the finite ordinals, and we will count the elements of any other set \(S\) by matching the elements of \(S\) up with the elements of one of these finite ordinals.

These special sets will look pretty strange at first, but really the only point is to build sets with certain key properties. Here are the two things we want to capture:

  • There is a first, or rather zeroeth, natural number called \(0\text{,}\) which has no elements at all.

  • For any natural number \(n \text{,}\) there is a next or successor natural number, which we might write as \(S(n)\) or \(n+1\text{,}\) which has exactly one more element than \(n \) does.

So how do we make this happen? Well, we know where to start: we've already met a set that has no elements – the empty set.

Definition 1.13.1. Zero.

The natural number \(0\) is defined to be the empty set \(\varnothing\text{.}\)

So far so good. But how should we make sense of the successor operation? If we're given a natural number \(n\text{,}\) then how shall we construct a new set with exactly one more element? The idea here is that we are going to take the elements of \(n\text{,}\) whatever they are, and add one more element, which will be the set \(\{n\}\text{.}\) This will give us a set that has exactly one more element than \(n\) had, just as we hoped.

Definition 1.13.2. Successor.

Let \(A\) be a set. The successor of \(A\) is the set \(S(A) = A \cup \{A\}\text{.}\)

So to understand how this works, let's begin with \(0\text{,}\) AKA the empty set. The elements of the set \(S(0)\text{,}\) according to our definition, includes all the elements of \(0\) (but there aren't any of those, so that's not saying much), as well as the set \(\{0\}\) itself. That is,

\begin{equation*} S(0) = \{ 0 \} = \{ \varnothing \}\text{.} \end{equation*}

Note that \(0\) has no elements, but \(S(0)\) has exactly one element. We write \(1 = S(0)\text{.}\)

Let's keep going. We constructed the natural number \(1\text{.}\) Let's construct \(2=S(1)=S(S(0))\text{.}\) The elements of \(2 \) are thus the elements of \(1\) along with \(\{1\}\text{.}\) That is,

\begin{equation*} 2 = S(1) = \{\varnothing, \{\varnothing\}\} = \{0,1\}\text{.} \end{equation*}

No point in stopping now! We have

\begin{equation*} 3 = S(2) = \{\varnothing, \{\varnothing\}, \{\varnothing, \{\varnothing\}\}\} = \{0,1,2\}\text{.} \end{equation*}

By now, you've probably understood the picture here: the natural number \(0\) is the empty set, and if \(n\) is a natural number, then the next natural number \(n+1\) is the set of natural numbers up to \(n\text{:}\)

\begin{equation*} n+1 = \{0,1,\dots,n\} \end{equation*}

You may well be thinking, “This is an answer to a question no one asked. I already knew what the number \(4\) was, and it wasn't the goofy set

\begin{equation*} \{\varnothing, \{\varnothing\}, \{\varnothing, \{\varnothing\}\},\{\varnothing, \{\varnothing\}, \{\varnothing, \{\varnothing\}\}\}\}\text{.} \end{equation*}
Is this whole course going to be like this?”

And in a way, you're right: we'll almost never use this way of formalizing the natural numbers. (And not to worry: the course won't all be like this!) There's a bit of a mismatch here between how we formalize certain pieces of mathematics and how we think about those pieces of mathematics. However: formalization in mathematics has four positive effects:

  • It holds us to an extremely high standard of verification. When we reduce all concepts to a small number of primitive ones with a small number of rules for their interaction, then we can be very confident that the things we derive in this way are actually true.

  • Being able to encode things in ways similar to this makes it possible to encode these ideas on a computer, and use the computer to verify our proofs. This is a growing part of pure mathematics.

  • While this approach to the natural numbers may not be how we start off thinking about them, very often the act of formalization reveals a different and new set of intuitions we can have toward even familiar mathematical objects. In this case, our strategy for defining the natural numbers in this iterative fashion provides us with a blueprint for proving certain kinds of statements – induction.

  • Lastly, formalization gives us the opportunity to generalize notions in surprising directions. In this case, the way we've defined the natural numbers generalizes to what are called the von Neumann ordinals, which permit us to talk about various infinite structures, and even to do an infinite kind of induction, called transfinite induction.

In set theory the Axiom of Infinity ensures that there is a set of all natural numbers:

\begin{equation*} \NN_0 = \{ 0, 1, 2, \dots \} \end{equation*}

Let's characterize this set precisely. First, let's say that a set \(M\) is successive if and only if \(0\in M\text{,}\) and for any \(A \in M\text{,}\) one has \(S(A)\in M\text{.}\) Now \(\NN_0\) is defined to be the smallest successive set; that is, \(\NN_0\) is a successive set such that no proper subset \(T \subset \NN_0\) is successive. Thus \(\NN_0\) contains \(0\text{,}\) and it also contains all the successors of successors of … of \(0\) — and nothing else!

One neat consequence of this way of constructing the set of natural numbers is that we can now define inequalities:

for every \(m,n\in\NN_0\text{,}\) we have \(m\leq n\) if and only if \(m \subseteq n\text{.}\)

The set \(\NN_0\) is our very first example of an infinite set. Now is a good time to reflect on what that word means. We perhaps have the intuition that this set is infinite because it “does not end.” How can we make this intuition precise? We shall return to this point soon.