Somebody said infinity?

1. Wait. “Size”?
2. Ok, got it. But where’s the infinity?
3. Wow, that’s interesting (right?)! Are there even larger infinities?

Perhaps there aren’t so many mysterious and yet fluent concepts such as infinity. Most of us have some sense of it, even as children. And yet, trying to pinpoint it can quickly become philosophical or metaphysical. As children, we might say “I love you infinitely” to a parent or a sibling to express endless love, or perhaps express the desire for “an infinite number of cookies”. One might try to express the infinity of the universe, the spirit or the human creativity, or even the infinite number of music pieces that may be composed.

It isn’t much to see that those examples actually deal with very different concepts, and yet have some kind of resemblance. Each of them somehow treats some kind of amount, whether tangible or not. And that is the subject of this little article: infinity. Though here it’ll be in a mathematically precise fashion, that most haven’t seen, I believe.

From high school to undergrad, outside mathematics, one learns about the symbol $∞$ that appears as some kind of “real number,” perhaps accompanied by some algebra rules for summation and multiplication, in order to express a “really large number, or amount”. This way of talking about it is actually very well-defined (mathematically speaking), but not what I’d like to consider in this piece. Here I’ll talk about the way one can count. Yes! 1, 2, 3… Like in “1 dog, 2 cats, 4096 rabbits, $6.0221415\times10^{23}$ mice.”

There is a clear infinity there: the infinite number of numbers. We learn it in math as the set of the naturals, $N = \{1,2,3,\ldots, n\}$. The nice thing about it is that, even though you never stop, one can put an order to it and, you know, count its elements. And from that we have some kind of definition of one concept of infinity. It even has a name: countable. We say that any other set is countably infinite, or simply countable, if it has the same size as the $N$.

Wait. “Size”?

But what is “size”? Well, that’s the hard question. Even though size is a tough concept, a mathematician usually knows how to compare sizes, using functions. Yes, the same thing we learn in high school and is a nightmare for many. The one that reminds us of quadratic formula and graphs smiling or frowning. But stay calm. Pretend there is a hitchhiker’s guide to the galaxy and DON’T PANIC!

The following are formal definitions. But don’t digress so much about it, it’s just so we can agree on things. Read the following in a sullen, and kind of annoying, voice of an old scholastic man, way behind his time.

“A set $A$ is a collection of elements, which are well-defined. Another set $B$ is a subset of $A$, if every element of $B$ also belongs to $A$, denoted as $B \subset A$”

“A function $f:A \to B$ is a relation between two sets, $A$ and $B$, such that for each element of $x \in A$ is related to only one $y \in B$, so called the image of $x$ by $f$, denoted $y = f(x)$.”

“A given function $f:A \to B$ is called an injective function, or simply injection, if given $x_1 \ne x_2$ in $A$ then $f(x_1) \ne f(x_2)$ in $B$.”

Maybe visualizing stuff is better than defining them. A set is just a collection of anything: numbers, letters, functions, sequences or even other sets. We can think of functions as a collection of arrows relating two sets with the following rules: every element of the origin set has to have exactly one arrow coming out of it; if the function is injective, no element of the target set has more than one arrow pointing to it.

So, how do functions help? Well, the set $A = \{1,3,5\}$, which has 3 elements is smaller than the set of 5 numbers $B = \{1,2,3,4,5\}$, which has 5. The number of elements is called cardinality, that we denote with the symbol $\#$, like in $\#A=3$ and $\#B=5$, and is the central concept that we’ll use.

We see it’s possible to build an injection from $A$ to $B$, but not from $B$ to $A$, exactly because $B$ is in fact “bigger”, or as one says in the math lingo $B$ has larger cardinality.

Now here’s the kick. Given two sets $C$ to $D$, if there is at least one injection $f:C \to D$, among possibly many, then automatically $\#C \leq \#D$! And if that is also true that $\#D \leq \#C$, i.e. there is another injection $g:D \to C$, then we write $\#C = \#D$. That is, $C$ and $D$ have the same cardinality.

Finally, there is a very “natural” quality in such a way to compare sizes, namely given that $A \subset B$, that is, $A$ is a subset of $B$, then $\#A \leq \#B$, as in the example above.

Ok, got it. But where’s the infinity?

Naively, one may think that a set’s cardinality is just a number, but that’s not really the case. We can talk about the cardinality of $N$, which can’t be written as a number, because, well, there is an infinite number of numbers, and since we can’t give a number we just write it as $\#N$. It is in fact the first and smallest infinity out there, called countable.

Are there other sets that are countable? Yes, plenty! The set of even numbers has cardinality $\#N$ even though there is only “half” of the number there (yeah, that’s right.). Or perhaps the collection of all prime numbers, which is a subset of $N$, and yet has also cardinality $\#N$ (confused yet?), because there are infinite prime numbers. When a set has non-finite cardinality, it’s actually quite normal to find a subset with the same cardinality.

Maybe the reader already concluded that any set which can be put as an ordered sequence of elements that never ends is in fact countable (being those elements numbers, functions or even other sets). An example is the rational numbers $Q$, those that can be written as fractions. Well, $\#N \leq \#Q$, because $N \subset Q$, but there is also an ordering for the rational numbers, and it shows that in it’s also true that $\#N \geq \#Q$, and thus $\#N = \#Q$.

Now is there a set with cardinality larger them $\#N$? Yeah! Plenty, actually. But they can become very confusing, very fast. One of them is the real line $R$, and $\#R$ is referred to as the continuum cardinality. The idea here is that one cannot put its elements in an infinite sequence. There is this cool argument that shows that’s true, called Cantor’s diagonal argument, that proves that in fact $\#N < \#R$. It’s a bit long and beyond the scope of this piece, so I’ll let the curious take a look at it.

Just like the case $\#N=\#Q$, there are many subsets of ℝ with cardinality $\#R$. One of them is $[0,1]$, the set of real numbers between and including 0 and 1, which are decimal numbers that start with a zero, such as 0.78598163397… The way to relate is sketched below, but it might be difficult for the uninitiated.

It turns out that the set of all sequences of natural numbers, denoted $N^{N}$, have exactly the same cardinality of $[0,1]$, because a decimal number starting with a $0$ is written as an infinite sequence of natural numbers. So, even though $N$ is countable, the set of all possible sequences of numbers is not.

The last example of a set of continuum cardinality is the Cantor set $C$. Among mathematicians, it is considered a kind of wildcard, because it defies our intuition. To explain that it is, we begin with $[0,1]$ and take out of it the second third of it. Then for each remaining section, you take out the second third again. Rinse and repeat ad infinitum (look at the drawing above) and one ends up with $C$. One may think one ends up with nothing, but there are many, many numbers remaining.

In fact, $\#C = \#R$, even though it can be seen as a collection of dots with gaps between them, with no “volume”, that is, if one represent them as points on the line, no two points are connected with a segment. And there are so many, that one just can’t count them! You can’t order them and put them in a sequence.

To sum up, we have the following relation of infinity sizes:

Wow, that’s interesting (right?)! Are there even larger infinities?

Yes! The set of all functions from the reals into itself, denoted here as $R^{R}$, has cardinality even larger than continuum. It is so large that not even an infinite and countable collection of lines would be enough to “count” them. I find this really weird.

The notation is not coincidental. For any set $A$, one can denote $A^{A}$ as the set of functions of $A$ into itself. And it is always true that $\#A < \#A^{A}$. So, for $A = R^{R}$ we have $\#R^{R} < \#A^{A}$. We repeat the argument ad infinitum, and voilà! There is in fact a countable collection of infinities, one larger than the next. Let it sink a little. Math can be a bit overwhelming.

And with this final conclusion, I shall end this piece.

I know that some readers might be lost right now. Threat not, it isn’t a simple topic. Quite the opposite, in fact. If that’s the case, I invite the reader to revisit this piece after a period of digestion. One truthful fact about learning math is that sleeping on it really helps.

For those inflamed by all of this, I recommend the unassuming Naive set theory by Paul R. Halmos and The Joy of Sets by Keith Devlin. But be warned! It’s not for the faint-hearted, and certainly requires perseverance to conquer.