A glimpse into cardinality, countability and infinity. Zhaorui Xu

The idea of sheltering homeless pigeons has somehow been haunting me recently… Perhaps it’s because I’ve encountered these little critters every day since coming to Oxford and feel that I’m not caring for them enough? Or maybe it has something to do with the reported pigeon infestation at Hilbert’s overbooked Hotel? In fact, I wonder whether we could combine the two problems and in the process provide homes not only for the pigeons of Oxford, but for all pigeons across the world… 

The first step in sheltering pigeons would be to gather together all the pigeons we can find. Before handling a set of pigeons, we first need to be clear about the general concept of a set from a mathematical standpoint. A set can be viewed as a group of distinct objects. But, sets do not have to be made up of only mathematical objects like numbers, ordinary objects such as oranges and in our case pigeons, can also form sets. 

Next up is cardinality – the cardinality of a set is the number of the elements in the set. So in our examples above, each set has cardinality 3. A set is said to be finite if its cardinality is a natural number or 0^[1], otherwise it is infinite. The set of natural numbers {1, 2, 3, 4…}, or concisely denoted by ℕ,  is an example of an infinite set. However, if we keep writing 1, 2, 3, 4, 5…. we know that every natural number will eventually turn up somewhere in the list, although this list goes on forever, which means that in this case we can say the natural numbers are countably infinite. If an infinite set is not countable, or simply speaking its elements are not listable like the natural numbers, then we say it is uncountably infinite. Finally, we introduce a cardinal number ℵ₀ to denote the cardinality of ℕ, and in fact since ℕ is the smallest infinite set, any infinite set will have a cardinality that is at least ℵ₀.

Two sets are defined to be equinumerous – which means they have the same size or the same cardinality – if and only if the elements in one of the set can be put in a one-to-one correspondence with those in the other set. In fact, this concept of equinumerosity in maths is even more fundamental than the definition of numbers: we are able to grasp this idea without even knowing what cardinal numbers are. Just think of how you make sure that knives are equinumerous with forks on a long dinner table. You arrange a fork by the side of each knife, not necessarily counting their numbers!

Now we have enough knowledge to match up pigeons and nests – the basic idea being simply to have the same number of pigeons as we have nests. If we suppose that we have a set of distinct pigeons and a set of distinct nests, then we would know that these two sets have the same size if there is a way to place one – and only one – pigeon into each nest. 

We could also imagine a tree with countably infinitely many branches, with one nest on each branch and each nest belonging to exactly one pigeon, as illustrated below:

In this case the sizes of both the set of nests and the set of pigeons are the same as ℕ: they both have cardinality ℵ₀. The two sets are equinumerous, which means that there are no unoccupied nests or perhaps most importantly, no homeless pigeons. 

Now that we have created pigeon utopia, there is little doubt that the word will spread and pigeons will flock to our tree of countably infinite branches. Let’s start with the simplest case, and suppose that one new fellow turns up wondering if they can join the community. Is this possible? Well, what we need to do is to invite all the pigeons to move one branch up. Since the natural numbers are not bounded above – that is, there is no greatest natural number – for the pigeon living on any branch n, they can move up to the branch n+1 and there will never be a dead end. The newcomer can now happily move into the nest on the first branch and everyone has a house.

We can see from this idea that infinity plus one is no bigger than our original infinity. In fact, the community of pigeons would always be of size ℵ₀ when a finite number m of pigeons joins, no matter how big m is. All we need to do is just shift all the pigeons m branches upwards, so that m vacant nests are created out of a fully occupied tree, using some mathematical magic. Conversely, the infinite size of the community of pigeons would be preserved even if as many as 10¹⁰⁰ members leave – infinity doesn’t care!

But what if an infinite population of pigeons wants to join the old community? What if the original population is doubled?

Before trying to figure this out, let’s first think about the following question: what is the size of the set of all even natural numbers {2, 4, 6,…}? Intuitively, we may want to say that its cardinality is half of that of ℕ (and the odd natural numbers contribute the other half). However, consider a match up like the folllowing:

We have a one-to-one correspondence between the even natural numbers and the natural numbers! Therefore by our earlier definition of equinumerosity there are the same number of even natural numbers as there are natural numbers. 

This means that to accommodate double the amount of pigeons, just ask the old members to all move onto branches labelled with even numbers and the newcomers can move into branches labelled with odd numbers. The tree will not be overcrowded and everyone can live in harmony! 

A more generalised (and mathematical) result is that 2ℕ, 3ℕ, …9999ℕ… are all equinumerous with ℕ. They are all of the same size, all have a cardinality of ℵ₀, and all are countably infinite. So in fact is ℕ x ℕ（and this can also be generalised to any power of ℕ). An instance of a set with the same size as ℕ x ℕ would be the set of all positive rational numbers (or all rational numbers, as these two sets are of the same cardinality). There is a clever method to list all positive rational numbers which was first introduced by German mathematician Georg Cantor in the late 19^th century:

The natural numbers on the horizontal and the vertical axes serve as the denominator and numerator for the rational number at the corresponding entry in the table. All instances of positive rational numbers appear somewhere on this diagram if I expand out this endless scroll forever. Following the arrows while crossing out rational numbers that have already appeared on the way (such as 1/2 and 2/4), we finally have all distinct positive rational numbers in an ordered list. Since rational numbers are listable, they are at most countable (by our earlier discussion). Moreover, they are countably infinite. So again, the cardinality of the set of rational numbers is ℵ₀. There are the same number of rational numbers as there are natural numbers, although intuitively there seems to be many times more rational numbers than there are natural numbers!

Returning to our infinite tree, let’s consider the following setup. We start with countably infinite blue pigeons. If each of these blue pigeons invites countably infinite orange pigeons and each of the orange pigeons invites countably infinite green pigeons (and the green pigeons have no guests), the eventual population would be equinumerous with ℕ³, and this is huge! But, all of the pigeons will still have a home as we can arrange the pigeons in a three-dimensional space and assign each of them a coordinate. The pigeon with coordinates (p, q, r) is given the nest with number 2^p3^q5^r. Thanks to the fundamental theorem of arithmetic^[2], no two pigeons with distinct coordinates end up in the same nest and everyone is once again happily at home.

This discussion about various scenarios of pigeons and nests is in fact an illustration of Hilbert’s paradox of the Grand Hotel. The paradox was originally introduced by David Hilbert in 1924 and replaced pigeons and nests with guests at a hotel with infinite rooms. 

So far we’ve yet to see anything bigger than ℕ, despite trying a lot of different approaches! However, there definitely are things larger than ℕ – for example the real numbers and the irrational numbers. They are both so dense on the number axis that they cannot all be picked out and listed as we did with the naturals and the rationals. In fact, there are many many more irrational numbers lying between 0 and 1 than there are rational numbers on the whole number axis. To see this, let’s suppose we are given a potentially infinite list of ordered irrational numbers between 0 and 1. We can specify a new irrational number that is distinct from all on the list as follows: let the new number be distinct from the first number on the list at the first decimal place, distinct from the second number on the list at the second decimal place, and so on. Continuing in this way we will construct an irrational number that does not belong to our list and thus there is no way to form a complete list of the irrational numbers. If there are uncountably many irrational numbers, then there are certainly uncountably many real numbers (since the real numbers are the union of all rational and irrational numbers).

It was proven by Cantor that the set of real numbers is equinumerous with the power set^[3]of ℕ, with the cardinality 2^ℵ₀ but I will leave this particular proof as an exercise for the (very interested and mathematically minded) reader. From our previous discussions we at least know that that 2^ℵ₀ > ℵ₀.

As mentioned earlier, the cardinality of ℕ, that is ℵ₀, is the smallest infinity (although it already racks one’s brain to comprehend, and already exhausts one’s life to count, and is even larger than the seemingly infinite number of pigeons living on this planet). Just as our magnificent sun is merely a negligibly tiny celestial body floating in the immense universe, there are many more sophisticated, gigantic members in the family of transfinite cardinal numbers. Perhaps it’s better only to mention that the next smallest cardinality, the smallest cardinality strictly greater than ℵ₀, is called ℵ₁. This is already uncountably infinite. 

It is still a mystery whether ℵ₁ is greater than 2^ℵ₀ or not. Cantor’s Continuum Hypothesis (CH) assumes that these two cardinalities are equal, however, this hypothesis is left unproven. It is not that mathematicians haven’t yet found a proof, but that the hypothesis is theoretically unprovable. Kurt Gödel proved that one cannot disprove the CH from the axioms on which today’s mathematics is built, and Paul Cohen proved that the CH similarly cannot be disproved. This is definitely not a situation that mathematicians are willing to accept… in fact, this is horrendous!

Anyway, to return to my original intention, why even bother considering infinitely many pigeons? The number of currently living pigeons, plus that of all of the generations of pigeons that lived before them, is still far less than infinity. ℵ₀ does not necessarily exist in nature! However, thanks to maths, at least I can have the most idealistic and harmonious pigeon utopia constructed in my mind (and now too in this article).

---

^[1]Here we adopt the more traditional convention of excluding 0 from natural numbers (Gottlob Frege would probably oppose).

^[2]Also called the unique factorisation theorem. It says that every integer greater than 1 can be uniquely written as the product of prime numbers. A prime number is a positive integer greater than 1 that can only be divided by 1 and itself. Note that 2, 3, 5 are all prime numbers. 

^[3]The power set of a set A, denoted by P(A) , is the set of all subsets of A. For example, the power set of {0,1} would be {∅, {0}, {1}, {0,1}}. If the cardinality of A is n, then the cardinality of P (A) would be 2ⁿ. To see this, think of each element in the power set as the set of presence or absence of every element of A. In each subset of A, there are two possible situations for each element in A: either present or absent. Hence there are 2ⁿ possible combinations in total. That is, 2ⁿ distinct subsets of A.