The Natural Numbers and Integers
Two of the sets of numbers that we’re introduced to in computability and number theory courses are the natural numbers, $\mathbb{N}$, and the integers, $\mathbb{Z}$.
The natural numbers are all the positive whole numbers, and zero:
$\mathbb{N} = \{0, 1, 2, 3, \ldots\}$.
The integers are all the positive and negative whole numbers, and zero:
$\mathbb{Z} = \{\ldots, -3, -2, -1, 0, 1, 2, 3, \ldots\}$.
Both of these sets are infinite in size. But, are they the same size of infinite?
In this blog post, we’ll explore a technique for showing that two infinite-sized sets are the same size: creating a bijection between them. We’ll use this technique to show that, counter to all intuition, there are exactly as many natural numbers as there are integers.
Set Cardinality
The cardinality of a set $S$, written $|S|$, is the size of the set (the number of things in it). A few examples are:
$|\{4, 5, 6\}| = 3$, and
$|\{$dog, cat, pig, cow$\}|$ = 4.
When a set is finite in size, the cardinality of the set is a count of its elements. We know that $\{$a, b, c$\}$ is the same size as $\{$d, e, f$\}$, because the cardinality of both is 3.
Cardinality of Infinite Sets
But, what about the cardinality of infinite sets? It’s a common question in number theory courses to ask if two infinite sets are the same size. These could be questions along the lines of:
Let $S$ be the infinite-sized set of all things where…, and let $T$ be the infinite-sized set of all things where…. Is $|S| = |T|$?
Of course, this question implies that there are different sizes of infinity. It’s not quite as simple as the playground taunts of, “I’m stronger than you by infinity”, followed by, “Well, I’m stronger than you by infinity plus one”. But, the taunt is surprisingly sound: some infinities are larger than others.
Our Flawed Intuition
The fact that there are different sizes of infinity is incredible. That sort of bizarre fact is part of why I love computer science so much.
But, in the case of $\mathbb{N}$ and $\mathbb{Z}$, shouldn’t $\mathbb{Z}$ be roughly twice the size of $\mathbb{N}$?
Let’s put aside the pesky number 0 for the moment, and talk about our intuitive observation:
$\mathbb{N}$ contains 1, but $\mathbb{Z}$ contains both -1 and 1. $\mathbb{N}$ contains 2, but $\mathbb{Z}$ contains both -2 and 2. And so forth onto, well, infinity.
Yet, as it turns out, our intuition leads us astray here. In fact, $|\mathbb{N}| = |\mathbb{Z}|$, and we’ll prove it by creating a bijection between the two sets.
Bijections
A bijection (also called a “bijective function”) is a function from a set S to a set T that’s both:
- Injective. That is, it causes each element in S to get mapped to a different element in T; and,
- Surjective. That is, it allows every element in T to get output, or “hit”, by some element in S.
Recall the sets $S = \{$a, b, c$\}$ and $T = \{$d, e, f$\}$. Let’s define a function $g : S \rightarrow T$ (meaning that $g$ takes an input from the set $S$ and outputs a result in the set $T$) as follows,
$g(x) = \begin{cases}
d & \text{if}~x = a \\
e & \text{if}~x = b \\
f & \text{if}~x = c
\end{cases}$
The function g is injective, because each input (be it “a”, “b”, or “c”) produces a distinct output. No two different inputs produce the same output.
The function g is also surjective because, for every possible element in T (be it “d”, “e”, or “f”), we can find some input that produces (or “hits”) that element of T.
The existence of this bijection between the two sets proves that the two sets are the same size, because we’ve discovered some way to create a perfect correspondence between the elements of the two sets.
To be clear, this method of proving $|S| = |T|$ is far more complicated than necessary (we could just count that there are 3 elements in each set). But, it is a proof that $|S| = |T|$.
A Bijection Between the Naturals and the Integers
What this means is that, if we can create a bijection between $\mathbb{N}$ and $\mathbb{Z}$, we’ll have proved that they’re the same size of infinity, all intuition to the contrary.
To accomplish this task, we’ll start by creating a function (seemingly out of thin air), and then we’ll go on to prove that the function is a bijection.
The general approach to showing that two infinite-sized sets have the same cardinality is to start by considering what a bijective function between the two sets might look like, then creating a function, and finally proving that the function is both injective and surjective (that is, bijective).
Let’s create a function $f : \mathbb{N} \rightarrow \mathbb{Z}$, as follows. That is, $f$ takes a natural number as input, and returns an integer.
$f(x) = \begin{cases}
x/2 & \text{if}~x~\text{is even} \\
-(x+1)/2 & \text{if}~x~\text{is odd}
\end{cases}$
Is our function f a bijection? Let’s prove that it’s both injective and surjective. For simplicity, let’s break this problem down into two separate proofs.
Proof the Function is Injective
To prove that f is injective, we need to show that no two different inputs to f will ever produce the same output.
To start our proof, let’s observe something important about our function that we’ll return to later in our proof. Our function can take one of two forms:
In the first form, where $f(x) = x/2$, we know $f(x)$ is positive or zero (that is, non-negative), because $x \ge 0$ for any natural number $x$.
In the second form, where $f(x) = -(x+1)/2$, we know $f(x)$ is negative. That’s because $x \ge 0$ for any natural number $x$, so $x + 1 > 0$, meaning $-(x+1) < 0$.
Let’s call that previous set of observations about the function’s two forms “Lemma 1”. This common technique of starting a proof with an inline mini-proof, showing a fact we’ll return to later, is called writing a lemma.
With Lemma 1 in place, let’s begin our overall proof that the function f is injective.
We’ll approach this as a proof by contradiction. Let’s assume we have two different inputs, $x \neq y$, but somehow $f(x) = f(y)$.
If $f(x) = f(y)$ then either both of $f(x)$ and $f(y)$ are non-negative, or both of $f(x)$ and $f(y)$ are negative. It can’t be the case that $f(x) = f(y)$ if only one of them is negative.
Let’s start by considering the case where $f(x)$ and $f(y)$ are both non-negative. By Lemma 1, the only time that can happen is when both $f(x)$ and $f(y)$ take the form $f(x) = x/2$ and $f(y) = y/2$. But, if $f(x) = f(y)$, then $x/2 = y/2$, so $x = y$. That contradicts our assumption that $x \neq y$.
Next, let’s next consider the case where $f(x)$ and $f(y)$ are both negative. Again, by Lemma 1, that can only happen when $f(x)$ and $f(y)$ take the form $f(x) = -(x+1)/2$ and $f(y) = -(y+1)/2$. Similar to our approach to the first case, if $f(x) = f(y)$, then:
$\begin{aligned}
& \quad -(x+1)/2 = -(y+1)/2 \\ \Rightarrow & \quad -(x+1) = -(y+1) \\ \Rightarrow & \quad x = y
\end{aligned}$.
Again, this contradicts our assumption that $x \neq y$.
Having shown a contradiction in both possible cases, we know it can never happen that $f(x) = f(y)$ when $x \neq y$. That is, our function $f$ is injective.
Proof the Function is Surjective
To prove that f is surjective, we need to show that it’s possible to produce every possible integer as an output, using some natural number as input.
Again, we’ll break down the proof into cases. We’d like to show that, using f, we can output, or “hit”: (a) every non-negative integer; and, (b) every negative integer.
For the first case, let’s consider some non-negative integer $y \ge 0$ that we want $f$ to output. Because $y \ge 0$, we know that $2y \ge 0$. Let’s name that value as $x = 2y$. Because $x \ge 0$, the integer $x$ is also a natural number.
Additionally, $x = 2y$ is even, because 2 times any integer is an even integer. Since $x$ is an even natural number, we have that: $f(x) = x/2 = 2y/2 = y$. In other words, we’ve found a natural number, $x$, that when input into $f$, will cause $y$ to be output.
In the second case, let’s consider some negative integer $y < 0$ that we want $f$ to output. Because $y < 0$, or in other words $y \le -1$, we know that $2y \le -2$. So, $2y+1 \le -1$.
Because $2y+1$ is negative, $-(2y+1)$ is positive. Let’s name that value $x = -(2y+1)$. Because $x$ is a positive integer, it’s a natural number.
Similar to in our first case, we know that $2y$ is even, hence $2y+1$ is odd, as is $x = -(2y+1)$. Given that $x$ is an odd natural number, we have that:
$\begin{aligned}
f(x) &= -(x+1)/2 \\ &= -(-(2y+1)+1)/2 \\ &= ((2y+1)-1)/2 \\ &= 2y/2 \\ &= y
\end{aligned}$
Taking these two cases together, it means that for any integer y (be it non-negative or negative), there is some natural number input x to the function f that produces the output y. Thus, f is surjective.
Proof of Equal Cardinality
The fact that there exists a bijection $f : \mathbb{N} \rightarrow \mathbb{Z}$ proves that $|\mathbb{N}| = |\mathbb{Z}|$.
That is, the cardinality of the naturals is the same as the cardinality of the integers. We even have a name for this size of infinity: $\aleph_0$ (aleph-nought).
As an important note, we could create a function that maps naturals to integers that isn’t a bijection. Consider $h : \mathbb{N} \rightarrow \mathbb{Z}$, where $h(x) = 1$. It’s not the case that every function between the two sets is a bijection. Rather, it’s the fact that some bijection exists that proves the two sets have the same cardinality.
Other Sizes of Infinity
We couldn’t wind up today’s blog post without asking: are all infinite sets as large as each other? No, there are different sizes of infinity.
The real numbers, $\mathbb{R}$ (all the decimals, including irrational numbers like $\sqrt{2}$ and $\pi$) represent a larger set than $\mathbb{N}$ or $\mathbb{Z}$. That cardinality, $|\mathbb{R}| = 2^{\aleph_0} > \aleph_0$.
The proof that $|\mathbb{R}| > |\mathbb{Z}| = |\mathbb{N}|$ is fascinating, but is a whole blog post unto itself.
Exercise
Some courses and textbooks define the natural numbers as being only the positive whole numbers:
$\mathbb{N}^+ = \{1, 2, 3, \ldots\}$.
It would be a great exercise for students to design a bijection between $\mathbb{N}$ and $\mathbb{N}^+$ to show that these two sets are the same size, despite $\mathbb{N}$ having one additional element (the number zero) that $\mathbb{N}^+$ does not.
Summary
The notion of different sizes of infinity is, in my opinion, one of the most interesting concepts in introductory number theory. That said, if we can create a bijection between two infinite sets — even two sets that seem like they shouldn’t be the same size, like the natural numbers and the integers — we’ve proved they’re the same size.
That is, there are just as many natural numbers as there are integers, even though our intuition tells us that there should be roughly twice as many integers as there are naturals.
I find the best way to approach proofs where you have to show that two infinite sets have the same cardinality is to take a three-section approach. In the first section, think about what a function representing a perfect correspondence between the two sets might look like, and create such a function. After creating such a function, break the problem of proving it’s a bijection into two halves. In one section, prove that the function is injective. In a separate section, prove that the function is surjective.
Keeping our work separated into these three clear sections will help keep these complicated proofs organized and readable.
For more tips, and to arrange for personalized tutoring for yourself or your study group, check out Vancouver Computer Science Tutoring.