The Smallest Infinity
I have one tattoo on my body. Naturally, it’s very meaningful to me. It reminds me daily of the wonder of the world, how surreal and special our existence is. The tattoo is the symbol ℵ₀ (pronounced aleph null, or aleph naught) and it represents the smallest infinity.
When I tell people what ℵ₀ means, they typically express some form of this excellent question,
How can there be bigger infinities? Isn’t infinity already infinite?
The answer is part of the reason I find the concept of the so-called cardinal numbers so beautiful, and the most common proof of bigger infinities involves the diagonalization argument. In fact, there exists an infinite ladder of infinities, starting with ℵ₀ and continuing on, ℵ₁, ℵ₂, and so on, forever, just like “regular” numbers do.
However, this post is about a different excellent question, posed to me recently for the very first time, by my uncle (thanks, Uncle Darwin!) He asked,
Why isn’t there a smaller infinity?
I was stumped! I couldn’t articulate the reason. Luckily, thanks to the magic of the internet, I’ve discovered the answer, and I’m so excited to share it that I wrote this, my first Medium post.
Intro to Counting
Before we dive in, it will be useful to start with something that may seem quite simple. How can we determine the size of a set, also called its cardinality?
To find a set’s cardinality, all we have to do is count the elements.
Easy enough for finite sets. What about infinite sets?
Well, it actually turns out that counting works the same way for some infinite sets. You just have to keep counting forever! Sets that work like this are called countably infinite and their size is denoted by ℵ₀.
One example of a countably infinite set is the set of all positive integers, denoted ℤ+. We can count the elements like this:
Fun with Countably Infinite Sets
There are lots of useful countably infinite sets other than ℤ+, and all of them have the same cardinality, ℵ₀. We’ll consider this idea to be an axiom, a basic fact that we’ll build upon later.
Axiom 1: If two sets are both countable, they have the same cardinality: ℵ₀.¹ We will informally say that all sets with the same cardinality are the same “size.”
This axiom leads to some conclusions that may surprise you. Let’s take a look at a few of its consequences.
Is the set of natural numbers, ℕ = {0, 1, 2, 3, 4, … } larger than ℤ+? The only difference between them is that we’ve added an extra number, 0. So ℕ must be larger than ℤ+ right? Well in fact, we can count them both, so they are the same size according to our axiom.
What about the set of odd integers {1, 3, 5, … }? It seems like this set only has half the elements that ℤ+ has, so it must be smaller. As it turns out, we can still count the elements, so this infinite set also has the same cadinality.
Even the set of all integers ℤ = {…, -2, -1, 0, 1, 2, … } is countable. This set includes all of the integers from ℤ+ , and the number 0, and the entire infinite set of negative integers. It seems larger, evenly infinitely larger. But, with just a little rearranging, it turns out we can count this set, too.
At this point you may be wondering again about bigger infinities. If all these sets are the same size, is there any infinite set that’s larger? The best example of a larger infinite set is the set of the real numbers ℝ, which includes fractions like 2/3 and 0.7 (also called rational numbers), as well as irrational numbers like π and the square root of 2. No matter how you try to rearrange them, you can’t find a way to count the numbers in this set. ℝ is an example of a set that is uncountably infinite. Its cardinality is larger than ℵ₀.²
Smaller Infinities?
Now that we understand what makes two infinite sets the same size, we’re ready to tackle the original question. Is ℵ₀ the smallest infinity? Put in other words, is there an infinite set with a cardinality less than ℵ₀?
The answer is definitively no, there is not, and to prove it, we’re first going to prove two intermediate theorems, or lemmas.
Lemma 1
For any countable set 𝕏 (i.e. a set with cardinality less than or equal to ℵ₀), there is some subset of ℤ+ with the same cardinality as 𝕏.³
Proof of Lemma 1
Let’s say we’ve found some set 𝕏 that is smaller than ℤ+. Since 𝕏 is smaller, this means there must be at least one element in ℤ+ for every element in 𝕏.
Imagine we draw an arrow from every element 𝕏 to one unique element of ℤ+, like in the image above. There may be some integers in ℤ+ left over, uncircled, but there will be exactly one arrow from each element of 𝕏, and exactly one green integer at the end of each arrow. This one-to-one mapping of elements from 𝕏 to ℤ+ is called an injection.
Since there is one green integer for each element of 𝕏, we can collect up all the green integers to get a subset of ℤ+ with the same cardinality as 𝕏.
Lemma 2
All subsets of ℤ+ are either finite or countably infinite.⁴
Proof of Lemma 2
Now we have a subset of ℤ+, let’s call it 𝕐. The elements of 𝕐 are unique positive integers, which means that we can write them in order from least to greatest. We know that the least possible element of 𝕐 is 1, because this is the least element of ℤ+. What about the greatest element? If 𝕐 has a greatest element, thats great for us. That means that 𝕐 is finite, and the lemma holds. If 𝕐 doesn’t have a maximum element, it’s infinite, but since we can write out the elements in order, starting with the least element, that means we can count them, so 𝕐 must be countably infinite.
Putting it All Together
So what are we talking about, again?
We want to prove that ℵ₀ is the smallest infinity (specifically, the smallest infinite cardinal number.) To do this, we’re going to take a set, ℤ+, with cardinality ℵ₀, and show that there is no smaller set that is still infinite.
Let’s say you give me some infinite set 𝕏, and you think it may be smaller than ℤ+. First I can use Lemma 1 to create a one-to-one mapping from 𝕏 to ℤ+ to define a set 𝕐 that is a subset of ℤ+ and has the same cardinality as 𝕏. By Lemma 2, I know that 𝕐 is either finite or has the same cardinality as ℤ+. We started with the assumption that 𝕏 is not finite, though, so the only option is that 𝕐 must have the same cardinality as ℤ+. So 𝕏 and 𝕐 are the same size and 𝕐 and ℤ+ are the same size, which means that 𝕏 and ℤ+ are the same size! All three sets have the cardinality ℵ₀, and so there is no smaller, infinite set! ℵ₀ is the smallest infinity. QED
Infinity is a fascinating concept, and even richer than you may have guessed. If you want to learn more on this topic, I’d recommend starting on Georg Cantor’s Wikipedia page. I hope you found this post informative and entertaining, and that you’ve gained a little insight into the infinite!
[1] To figure out if two uncountable infinite sets are the same size, you need to provide something called a bijection. This is a generalized version of what I’m doing in this post with countable sets.
[2] Is the cardinality equal to ℵ₁? That’s hard to say.
[3] Of course, a more general statement is true: if the cardinality of some set A is not larger than the cardinality of some set B, then we can find an injection from A to B.
[4] As with the first lemma, a more general statement is true: a subset of any countably infinite set is either finite or countably infinite.
