An introduction to the cardinal numbers

There are lots of different kinds of numbers. In school, you learn about some of them: integers, rational numbers, irrational numbers, real numbers, imaginary numbers, complex numbers. So educated non-mathematicians are familiar with these kinds of numbers. But there are other kinds of numbers which pretty much nobody who doesn’t have an interest in maths has heard of, and that’s a pity, because some of them are really cool. Two of the most interesting examples are the cardinal numbers and the ordinal numbers. Both of these number systems are ways of extending the ordinary system of positive integers to allow for numbers representing infinite quantities. I’ll talk about the cardinal numbers in this post, and I’ll possibly talk about the ordinal numbers in another one.

In order to understand what cardinal numbers are, you need to understand what sets are, in the mathematical sense. In its ordinary sense, the word ‘set’ can refer to a collection of objects, and that’s basically what it refers to in the mathematical sense, as well. However, the first examples of sets, in the ordinary sense, that come to mind are probably all collections of objects which are physically bundled together in some way, e.g. the set of socks in your wardrobe, or the set of coins in a bag. But we can also use the word ‘set’ to refer to collections of objects which are not physically close, but are distinguished by sharing some other common property, e.g. the set of all the people you’re related to. In mathematics, the sets we talk about tend to be more like this: after all, they usually contain abstract things, like numbers, which do not have any physical location. If we wanted to, we could talk about rather silly sets, like the set consisting of John F. Kennedy, the North Pole, and the philosophical school of Stoicism. The property that distinguishes the objects in this set is the property of being either John F. Kennedy, the North Pole or Stoicism. It’s not the kind of property you’d usually want to talk about, but, still, it’s a property.

The number of objects a set {S} contains is called its cardinality and denoted {|S|}. For example, the cardinality of the set consisting of John F. Kennedy, the North Pole and Stoicism is 3. However, there is nothing in the definition of the word ‘set’ that implies sets can only contain a finite number of objects. For example, the set of integers contains infinitely many objects. Sure, if we restrict our attention to sets which contain actual, physical objects, sets may all be finite in size (depending on what you mean by ‘actual, physical objects’, and also depending on physics). But, certainly, if we want to talk about sets containing abstract mathematical objects like numbers, we’re going to have to accept that some of them are infinite in size. Sets like this are called infinite sets, as opposed to finite sets. The question which motivates the development of the concept of cardinal numbers is this: what is the cardinality of an infinite set? Clearly, it is not any integer. Of course we can introduce a new number called infinity and say that the cardinality of every infinite set is infinity, but this doesn’t really give any more information than just saying that the cardinality is not any non-negative integer. For a long time, mathematicians assumed that this was the only way to assign cardinalities to infinite sets, and, therefore, they did not consider this question very interesting. It was only in 1874 that things changed. Georg Cantor published a paper explaining how there was a quite sensible way of assigning cardinalities to infinite sets which did not assign them all the same cardinality. In particular, it assigned the set of the real numbers a larger cardinality than the set of the integers. He called the new numbers introduced in this way (together with the non-negative integers, which are the cardinalities of finite sets) the cardinal numbers.

It was the proof that there were different infinite cardinalities that was Cantor’s innovation; his definition of cardinality was not particularly original. In fact, it is probably the most natural way to define cardinality in precise terms. The idea is, basically, that you find a set’s cardinality by counting the objects in it. To see what I mean, think about what the process of counting involves. You start off knowing that the set contains at least 0 objects. So you start a counter at 0. Then you pick an object out of the set. It may not be possible to do so, in which case you know the set contains exactly 0 objects (i.e. it is empty). But if it is possible to do so, then you know that the set contains at least 1 object, so you add one to the counter, making it 1. And the process repeats like that: at each step, you see whether you can pick out another object from the set; if you can, you add one to your counter, otherwise, you stop and take the current value of the counter as the cardinality. The object picked out must always be a new object, not one of the ones you already picked out. Does this work for infinite sets, though? No, because the process will never stop: after a finite number of steps, there will always be another object to pick out.

The problem, then, is that, as we are conceptualising it, counting is a process; it has to be carried out in a finite number of steps. But there is a different way to conceptualise counting. If you count a set which contains exactly {n} objects, the sequence of values the counter takes is 0, 1, 2, …, {n}. Each of these values, except for 0, can be associated with the object which caused the counter to reach that value when it was picked out, and in this way a one-to-one correspondance is set up between the objects in the set and the integers 0, 1, 2, … and {n}: each of the objects corresponds to exactly one of the integers and each of the integers corresponds to exactly one of the objects. So one way of describing what you do when you count a finite set {S} is that you find a non-negative integer {n} such that you can set up a one-to-one correspondance between the objects in {S} and the integers 0, 1, 2, … and {n}. In general, two sets {S} and {T} have the same cardinality if and only if there is a one-to-one correspondance between the objects in {S} and the objects in {T}. The crucial point here is that you can set up one-to-one correspondances between the objects in infinite sets, too. So, even though there are infinitely many non-negative integers, we can define a new number, {\omega}, by saying that the cardinality of a set {S} is {\omega} if you can set up a one-to-one correspondance between the objects in {S} and the non-negative integers. This new number is our first example of a cardinal number which is not a non-negative integer.

In his book, Two New Sciences, Galileo Galilei was already talking about this way back in 1638. But Galileo noticed that this definition gives some rather odd results. For example, it seems obvious that there are more non-negative integers than square integers. After all, there are infinitely many non-negative integers which are not square integers, and, furthermore, as you go further into the sequence of non-negative integers, the gaps between successive square integers get wider and wider: so it seems like the number of square integers, if it makes sense to speak of this number, should be just a fraction of the number of non-negative integers. But every non-negative integer has exactly one square, and every square integer has exactly one non-negative square root. So there is a one-to-one correspondance between the square integers and the non-negative integers, and, therefore, if we use this definition of cardinality, we have to say that the cardinality of the set of square integers is {\omega}, which is exactly the same as the cardinality of the set of the non-negative integers.

Galileo considered this result absurd enough that the only sensible conclusion to reach was that it was meaningless to talk of infinite quantities being greater than, less than or equal to other infinite quantities. Indeed, it seems likely, if we can set up one-to-one correspondances between two sets which seem very different in size, like these two, then we will be able to set up one-to-one correspondances between any two infinite sets. But, as Cantor showed, this is not the case. Let’s see how he showed it.

Cantor gave his original proof by showing that the cardinality of the set of the real numbers was not {\omega}, but this proof was rather complicated, so I won’t go into it here. Instead, I’ll give a different example of a set whose cardinality is not {\omega}; in fact, I’ll show how an infinite sequence of new cardinal numbers which are all different from one another can be constructed. First, I need to tell you some more things about sets. For every set {S}, sets which only contain objects in {S} are called subsets of {S}. For example, the set of the positive integers is a subset of the set of the integers. The set of all the subsets of {S} is called the power set of {S} and denoted {\mathcal P(S)}. For example, the power set of {\{1, 2, 3\}} consists of {\emptyset}, {\{1\}}, {\{2\}}, {\{3\}}, {\{1, 2\}}, {\{1, 3\}}, {\{2, 3\}} and {\{1, 2, 3\}}. (I’ve used some notation here you may not be familiar with. {\emptyset} is the empty set, the one which doesn’t contain any objects. A list of objects surrounded by curly brackets denotes the finite set consisting of those objects.) What we can prove is that for every set {S}, the cardinality of {\mathcal P(S)} is not the same as that of {S}. If you’ve heard of Russell’s paradox, this proof will remind you of it. Suppose there is a one-to-one correspondance from the members of {S} to the subsets of {S}. For every object {x} in {S}, let {f(x)} be the subset of {S} corresponding to {x}. Consider the set {T} of the members {x} of {S} such that {f(x)} does not contain {x}. This is a subset of {S}. If it is equal to {f(x)} for some member {x} of {S}, then there are two possibilities: either {T} contains {x}, or {T} does not contain {x}. But if {T} contains {x}, then {f(x)} does not contain {x}, by the definition of {T}, but this is absurd, because {f(x)} is {T}! And, if {T} does not contain {x}, then {f(x)} does not contain {x}, because {T} is {f(x)}, but this is, again, absurd, because then {f(x)} is, by the definition of {T}, in {T}. So, if there is a one-to-one correspondance from the members of {S} to the subsets of {S}, this inevitably leads to an absurdity, and hence no such correspondance can exist. (This isn’t just a counter-intuitive absurdity, like the absurdity of there being as many squares as non-negative integers; we have shown that if such a correspondance exists, there is a statement which is both true and false at the same time. That’s a much more serious kind of absurdity.)

The notion of a subset also allows us to define what it means for one infinite cardinality to be greater than another infinite cardinality. A set {S} has greater cardinality than another set {T} if and only if {S} has the same cardinality as a subset of {T}. It is easy to see that the cardinality of {\mathcal P(S)} is, in fact, greater than the cardinality of {S}, because the set of all sets of the form {\{x\}}, where {x} is a member of {S}, is a subset of {\mathcal P(S)}, and there is an obvious one-to-one correspondance between these sets and the members of {S}. This suggests that we can define an infinite sequence of cardinal numbers which increase in size,

\displaystyle \beth_0, \beth_1, \beth_2, \dotsc,

where {\beth_0} is {\omega} and for every non-negative integer {n}, {\beth_{n + 1}} is the cardinality of the power sets of sets of cardinality {\beth_n}. In other words, {\beth_0} is the cardinality of {\mathbb N} (the set of the non-negative integers), {\beth_1} is the cardinality of {\mathcal P(\mathbb N)}, {\beth_2} is the cardinality of {\mathcal P(\mathbb N)}, and so on. (In order to make sure that these cardinal numbers actually do increase in size, we have to check that our way of ordering the cardinal numbers has the property that if {S}, {T} and {U} are sets and {|S| < |T|}, and {|T| < |U|}, then {|S| < |U|} as well. However, the proof that this is the case is quite complicated, so I will omit it here.) Note that not every cardinal number is a member of this sequence. The cardinality of the set of the real numbers is in this sequence, however: it’s {\beth_1}. You could try and prove this yourself: all you need to show is that there is a one-to-one correspondance between the real numbers and the subsets of {\mathbb N}. Here’s a hint: a subset of {\mathbb N} can be thought of as a function associating each natural number with 0 (if this natural number is not in the subset) or 1 (if this natural number is in the subset), i.e. a sequence of 0s and 1s. Is there also a way to think of real numbers as sequences of 0s and 1s?

There is a lot more that I could say about cardinal numbers to help you get comfortable with thinking of them as numbers. There is no strict definition of what a ‘number’ is in mathematics: the decision of whether to call things numbers is a subjective one, influenced by the amount of properties those things have which are similar to properties of archetypal number systems like {\mathbb N}. To use Vi Hart’s phrase, numbers are things you do can do numbery things with. We have shown that there are infinitely many cardinal numbers and they can be arranged into an increasing sequence, and that’s pretty numbery, but there are lots of other numbery things you can do with cardinal numbers: for example, you can add and multiply them, and you can take the power of one cardinal number to another (although, that said, the operations on the cardinal numbers behave rather weirdly— I won’t go into it fully here, but, for example, for every pair of infinite cardinal numbers {\kappa} and {\mu}, {\kappa + \mu} and {\kappa \mu} are both the same and just equal to the larger of {\kappa} and {\mu}). So, now you know that it’s not quite true to say that infinity isn’t a number. OK, it isn’t one number, but every infinite quantity can be described by a cardinal number, and these cardinal numbers aren’t too different from ordinary numbers.

If you were wondering whether the theory of cardinal numbers has any practical application, well, the answer is ‘no’. The same can be said about a lot of mathematics, but applications of the cardinal numbers are actually quite scarce even within mathematics. Outside of set theory, mathematicians hardly ever need to concern themselves with sets whose cardinalities are greater than {\beth_1}, the cardinality of the set of the real numbers. So the only distinction between infinite cardinal numbers which is often relevant is that between {\beth_0} and {\beth_1}. Infinite sets of cardinality {\beth_1}, as well as finite sets, are called countable sets, while infinite sets of cardinality {\beth_1}, and all other infinite sets of greater cardinality than {\beth_0}, are called uncountable sets. There’s a famous analogy, which David Hilbert came up with, which sheds some light on why this is the case.

Any hotel in our universe only has finitely many rooms. So if the hotel is full, and another person comes along, they have to be turned down. Because, if the new person goes into Room 1, the person already in Room 1 has to move into Room 2, and then the person already in Room 2 has to move into Room 3, and so on, and since there are only finitely many rooms, eventually some positive integer {n} is reached such that there is no Room {n + 1}, and hence nowhere for the person in Room {n} to move to. So the hotel either has to refuse the new person, or kick someone out. In mathematical terms, what we’re saying here is that if you take a set of a finite cardinality {n} and add another member to it, the new set has greater cardinality.

But let’s suppose the hotel has {\beth_0} rooms. In that case the new person can be let in, even though the hotel is full, because there is no positive integer {n} at which there stops being a Room {n + 1}! The person in Room 1 can move to Room 2, the person in Room 2 can move to Room 3, and so on, leaving Room 1 free for the new person. In mathematical terms, if you add another member to a set of cardinality {\beth_0} (or any other infinite cardinality), the new set still has the same cardinality. And, by repeating this process, any finite number of new people can be let in. That’s why, if you add a finite cardinal number to an infinite cardinal number, the result is the original infinite cardinal number; it is not changed by the addition.

OK, what if there’s a countably infinite number of new people? Still not a problem, we just have to take a slightly different approach: move the person in Room 1 to Room 2, move the person in Room 2 to Room 4, move the person in Room 3 to Room 6, and so on, so that all the odd-numbered rooms are left free. Again, there’s nothing stopping us from doing this: for every positive integer {n}, there is a Room {2 n}. Then, we just move the first new person into Room 1, the second new person into Room 3, the third new person into Room 5, and so on; for every positive integer {n}, there is a Room {2 n + 1} free for the {n}th new person to move into. In mathematical terms, this reflects the fact that {\beth_0} times 2 is still just {\beth_0}. And, of course, we can repeat this any finite number of times, showing that {\beth_0} times every positive integer is still {\beth_0}, or, if you take any finite number of countably infinite sets and put all their members together into one set (this set is called the union of the original sets), this set is still countably infinite.

Well, how about if there are countably infinitely many lines of new people waiting outside the hotel, each of them containing a countably infinite number of people? This isn’t a problem, although some slightly more advanced mathematics is needed. We can use the fact that every positive integer is uniquely represented as a product of prime numbers, which means that in particular, for every pair of prime numbers {p} and {q}, no two powers of {p} and {q} are equal (for otherwise the common value of the two powers would be a number which can be represented as a product of prime numbers in two different ways). So for every positive integer {n}, we can move the person in Room {n} to Room {p_n} where {p_n} is the {n}th prime number. Then, for every positive integer {n}, we move the {n}th person in the first line into Room {p_n^2}, we move the {n}th person in the second line into Room {p_n^3}, and so on. This allows all the people to get a room, and, in fact, it even leaves all the rooms whose numbers are not powers of prime numbers (e.g. Room 6) free. This indicates that even unions of countably infinitely many countably infinite sets are still countably infinite. For example, the set of the rational numbers, i.e. fractions {a / b} where {a} and {b} are integers, is countably infinite, because there are countably infinitely many possible values of {b}, and hence the set can be split into countably infinitely many subsets, with the members of each subset sharing a common denominator. And each subset is countably infinite, because the only way two of its members can be different is if they have different numerators, and there are only countably infinitely many possible values of {a}.

The point of all this is that it’s a lot harder to make a set whose cardinality is infinite into a bigger set than it is if the cardinality is finite. So, in most areas of mathematics, you end up only needing to work with countably infinite sets, such as {\mathbb N}. It’s rare that you come across a set so large that it is uncountable, and even if you do, it is probably only of cardinality {\beth_1}. It’s not surprising, then, that mathematicians didn’t feel the need to develop a theory of cardinal numbers for a long time. But the cardinal numbers are really neat, which in mathematics is a completely acceptable reason to study something (indeed, in Hardy’s view, it is the principal reason why anyone studies mathematics); they are also interesting from a philosophical point of view as they shed some light on the meaning of infinity, or at least one particular conception of the meaning of infinity. And note that I have only given a very cursory introduction to them in this post; there are very interesting things about cardinal numbers which I have not even mentioned. For example, there is the question of whether there are any cardinal numbers between {\beth_0} and {\beth_1}, which turns out to be, in a certain sense, unanswerable.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s