Posted in June 2019

What is cardinality?

This is the second in a short series of blog posts intended to explain the terms in red in the following sentence, that succinctly describes the Continuum Hypothesis.
There is no set whose cardinality is strictly between that of the integers and the real numbers.
These are, in the words of John Lloyd, the bits that he does not understand.

In the first post and its addendum we dealt with the difficulty that any definition of the notion `set’ must, to some extent, be circuitous: one cannot avoid the use of a synonym, such as `collection’, `aggregate’, …

The next term in red in the sentence above is `cardinality’. Here the difficulty is worse.
To see why this is we turn to Georg Cantor again in his Beiträge zur Begründung der transfiniten Mengenlehre he gave the following definition.

,Mächtigkeit` oder ,Cardinalzahl` von M nennen wir den Allgemeinbegriff, welcher mit Hülfe unseres activen Denkvermögens dadurch aus der Menge M hervorgeht, dass von der Beschaffenheit ihrer verschiedenen Elemente m und von der Ordnung ihres Gegebenseins abstrahirt wird.
Das Resultat dieses zweifachen Abstractionsacts, die Kardinalzahl oder Mächtigkeit von M, bezeichnen wir mit |M|.

In the translation by Philip E. B. Jourdain this becomes

We will call by the name “power” or “cardinal number” of M the general concept which, by means of our active faculty of thought, arises from the aggregate M when we make abstraction of the nature of its various elements m and of the order in which they are given.
We denote the result of this double act of abstraction, the cardinal number or power of M by |M|.

As beautiful as this may sound it is actually meaningless. The phrases “active faculty of thought” and “abstraction of the nature” have no mathematical meaning. When one reads the next few pages of Cantor’s paper it becomes quite clear that this is an attempt to define `the number of elements’ of the set. Those next pages establish that two sets have the same power if and only if “it is possible to put them, by some law, in such a relation to one another that to every element of each one of them corresponds one and only one elemen of the other” (translation by Jourdain).

By way of example the sets of provinces of the Netherlands and of months of the year have the same power; the following relation between provinces and months establishes this:
(January,Groningen),
(February,Drente),
(March,Friesland),
(April,Overijssel),
(May,Flevoland),
(June,Gelderland),
(July,Utrecht),
(August,Noord-Holland),
(September,Zuid-Holland),
(October,Zeeland),
(November,Noord-Brabant),
(December,Limburg).
Every month corresponds to one and only one province and every province corresponds to one and only one month.

Before we continue: `cardinality’ is just another term for `power’.

The definition of power, or cardinality, or cardinal number is more incomplete than that of `set’. At least in the latter definition we had a synonym to fall back on; the definition of cardinality does not even have that contingency. However, and this is very important for what follows, even though `cardinality’ does not have a good definition the notion that two sets have the same cardinality does have a mathematically sound and workable definition: nowadays Cantor’s characterization of when two sets have the same power is taken as its definition.

As an aside: a similar thing can be said of the notion of length. If we ever come face to face it will be clear immediately whether the length of John Lloyd is larger or smaller than mine (or equal even) but unless we happen to have a tape measure handy we will not know our lengths, expressed in the local units.

Small children know how to compare the cardinalities of sets: a practical instance is given by chocolate sprinkles, a favourite Dutch breakfast item. If one takes two spoonfuls of these items it is quite easy to check whether these contain the same number of sprinkles. Here are two heaps of them:

I personally did the following: take one from each heap and eat them, and again, and again, and again, … after a while the … was empty and the other one was not. This means that the heaps did not contain the same number of sprinkles and I we can even say that the cardinality of the other heap of sprinkles was larger than that of the … one. This process was quite easy I could walk away and resume again later; I did not worry about losing my count because I did not count.

Thus we find ourselves in the strange situation that we have an undefined notion `cardinality of a set’, yet when we are given two sets we have a way of potentially deciding whether they have the same cardinality. We can even say when the cardinalities of two sets are comparable: if M has the same cardinality as some subset of N we can express this by saying that the cardinality of M is less than or equal to that of N, we can even write |M|≤|N| in that case. In the next installment we shall see that the next bit, strictly between, actually does have an unambiguous definition.

© 2011 TU Delft