Simple mathematical concepts such as counting appear to be firmly anchored in the natural process of thinking. Studies have shown that even very young children and animals possess such skills to a certain extent. This is hardly surprising because counting is extremely useful in terms of evolution. For example, it is required for even very simple forms of trading. And counting helps in estimating the size of a hostile group and, accordingly, whether it is better to attack or retreat.
Over the past millennia, humans have developed a remarkable notion of counting. Originally applied to a handful of objects, it was easily extended to vastly different orders of magnitude. Soon a mathematical framework emerged that could be used to describe huge quantities, such as the distance between galaxies or the number of elementary particles in the universe, as well as barely conceivable distances in the microcosm, between atoms or quarks.
We can even work with numbers that go beyond anything currently known to be relevant in describing the universe. For example, the number 1010100 (one followed by 10100 zeros, with 10100 representing one followed by 100 zeros) can be written down and used in all kinds of calculations. Writing this number in ordinary decimal notation, however, would require more elementary particles than are probably contained in the universe, even employing just one particle per digit. Physicists estimate that our cosmos contains fewer than 10100 particles.
Yet even such unimaginably large numbers are vanishingly small, compared with infinite sets, which have played an important role in mathematics for more than 100 years. Simply counting objects gives rise to the set of natural numbers, ℕ = {0, 1, 2, 3, …}, which many of us encounter in school. Yet even this seemingly simple concept poses a challenge: there is no largest natural number. If you keep counting, you will always be able to find a larger number.
Can there actually be such a thing as an infinite set? In the 19th century, this question was very controversial. In philosophy, this may still be the case. But in modern mathematics, the existence of infinite sets is simply assumed to be true—postulated as an axiom that does not require proof.
Set theory is about more than describing sets. Just as, in arithmetic, you learn to apply arithmetical operations to numbers—for example, addition or multiplication—you can also define set-theoretical operations that generate new sets from given ones. You can take unions—{1, 2} and {2, 3, 4} becomes {1, 2, 3, 4}—or intersections—{1, 2} and {2, 3, 4} becomes {2}. More excitingly, you can form power sets—the family of all subsets of a set.
Comparing Set Sizes
The power set P(X) of a set X can be easily calculated for small X. For instance, {1, 2} gives you P({1,2}) = {{}, {1}, {2}, {1, 2}}. But P(X) grows rapidly for larger X. For example, every 10-element set has 210 = 1,024 subsets. If you really want to challenge your imagination, try forming the power set of an infinite set. For example, the power set of the natural numbers, P(ℕ), contains the empty set, ℕ itself, the set of all even numbers, the prime numbers, the set of all numbers with the sum of digits totaling 2021, {12, 17}, and much, much more. As it turns out, the number of elements of this power set exceeds the number of elements in the set of natural numbers.
To understand what that means, you first have to understand how the size of sets is defined. For the finite case, you can count the respective elements. For instance, {1, 2, 3} and {Cantor, Gödel, Cohen} are of the same size. If you wish to compare sets with numerous (but finitely many) elements, there are two well-established methods. One possibility is to count the objects contained in each set and compare the numbers. Sometimes, however, it is easier to match the elements of one set to another. Then two sets are of the same size if and only if each element of one set can be uniquely paired with an element of the other set (in our example: 1 → Cantor, 2 →Gödel, 3 →Cohen).
This pairing method also works for infinite sets. Here, instead of first counting and then deriving concepts such as “greater than” or “equal to,” you follow a reverse strategy. You start with defining what it means that two sets, A and B, are of the same size—namely, there is a mapping that pairs each element of A with exactly one element of B (so that no element of B is left over). Such a mapping is called bijection.
Similarly, A is defined to be less than or equal to B if there is a mapping from A to B that uses each element of B once at most.
After we have these notions, the size of sets is denoted by cardinal numbers, or cardinals. For finite sets, these are the usual natural numbers. But for infinite sets, they are abstract quantities that just capture the notion of “size.” For example, “countable” is the cardinal number of the natural numbers (and therefore of every set that has the same size as the natural numbers). It turns out that there are different cardinals. That is, there are infinite sets A and B with no bijection between them.
At first sight, this definition of size seems to lead to contradictions, which were elaborated by the Bohemian mathematician Bernard Bolzano in Paradoxes of the Infinite, published posthumously in 1851. For example, Euclid’s “The whole is greater than the part” appears self-evident. That means if a set A is a proper subset of B (that is, every element of A is in B, but B contains additional elements), then A must be smaller than B. This assertion is not true for infinite sets, however! This curious property is one reason some scholars rejected the concept of infinite sets more than 100 years ago.
For example, the set of even numbers E = {0, 2, 4, 6, …} is a proper subset of the natural numbers ℕ = {0, 1, 2, …}. Intuitively, you might think that the set E is half the size of ℕ. But in fact, based on our definition, the sets have the same size because each number n in E can be assigned to exactly one number in ℕ (0 →0, 2 →1, 4 →2, …, n →n/2, …).
Consequently, the concept of “size” for sets could be dismissed as nonsensical. Alternatively, it could be termed something else: cardinality, for example. For the sake of simplicity, we will stick to the conventional terminology, even though it has unexpected consequences at infinity.
In the late 1800s, German logician Georg Cantor, founder of modern set theory, discovered that not all infinite sets are equal.
