Students in advanced mathematics courses in the final two years of high school formalize the concepts of bijection and cardinality. By counting the subsets of a set H with n elements, and knowing that 2*n > n*, they conclude that trying to establish a bijection between H and its power set is futile. In other words, H and P(H) are not equinumerous (see the article "A Journey into Infinity").
Once this hurdle has been cleared, it is worth going a little further and proving the same result for an arbitrary, possibly infinite set H. The appeal is manifold: discovering the genius of a proof whose very brevity and simplicity make it miraculous; retracing the footsteps of Cantor and his century; getting a first taste of the staggering hierarchy of infinities; pondering the continuum hypothesis...
A proof by contradiction
-----------------------------
There is always an injective map from any set H to its power set, if only by associating with each element h of H the singleton {h}. On the other hand, there can never be a surjection (and a fortiori a bijection) from H onto P(H). To prove this theorem, which he had anticipated and stated, Cantor first... assumes its opposite. He therefore considered a hypothetical surjective map f from H onto P(H). He then had the apparently preposterous but truly brilliant idea of considering the subset C of H defined as follows:
The nature of C hardly matters: a priori, it could be the whole set H, a pair, a singleton, or the empty set. We need not decide which: by hypothesis—since C is a subset of H and f is assumed to be surjective—C has at least one preimage under f. Choose one, denote it by b, and ask where it lies relative to C. There are two possibilities:
• Either b belongs to C = f (b). Then, by definition of C, b does not belong to f (b), which equals C;
• Or else b does not belong to C = f (b). Yet that same definition of C conversely requires b to belong to f (b) = C.
In both cases, the element b is required simultaneously to belong to C and not to belong to C. These contradictions show that the map f cannot exist, which settles the matter.
Presented this way, the argument broadens the range of proofs by contradiction. It sits nicely alongside other classic examples: the irrationality of √2, the infinitude of prime numbers, and the uniqueness of a limit.
For all its elegance, Cantor's proof remains abstract. A diagram helps: it can show a few elements (c, c', c''... making up C) and place b, a preimage of C under f, according to whichever alternative applies.
**Cantor's argument.
In red, the elements that do not belong to their image under f (and therefore make up the set C);
in blue, those that do belong to it (and therefore make up the complement of C).
When b, a preimage of C, lies in C (left), it is both red and blue.
When it does not lie in C (right), it is both blue and red.**
In addition to leading to a contradiction by a case distinction, Cantor's argument creates a vicious circle.
Cantor's argument, in which each of the two propositions
(on the left and right) negates itself, creates a vicious circle.
The barber and the hairdresser
--------------------------
But what is the barber doing in this story? Dropping into Cantor's soup rather like a hair, the analogy—accordingly known as the barber analogy—provides a mnemonic for remembering the recipe. Its origins are disputed, but the metaphor was taken up and popularized by Bertrand Russell and his contemporaries. Here, the set H represents the residents of a city—say, Seville in Spain. The map f sends each resident h of Seville to the set of fellow residents whom he shaves.
Now, f is assumed to be surjective. Consequently, every group of people has at least one barber in common, whether or not that barber belongs to the group, though he must be a resident of the city. In particular—because of surjectivity—every resident is assumed to be shaved, while some residents may shave nobody; for them, f assigns the empty set Ø. A priori, there is nothing inconsistent about a resident shaving himself and also occasionally being shaved by someone else.
With one exception.
In this case, the set C consists of all residents who do not shave themselves—or, put another way, who are mere clients. A preimage of C is what we shall call a "professional barber" b. The question "Who shaves this barber?" then brings out the paradox:
• Suppose b shaves himself (that is, b ∈ f (b) = C). This conflicts with his role: to shave only people who do not shave themselves—in other words, mere clients. So this barber does not shave himself;
• Suppose b does not shave himself (that is, b ∉ f (b) = C). As a mere client, he must be shaved by the person or people whose job it is: the professional barbers... So he shaves himself!
It is enough to drive anyone mad. So how can we escape this implacable logic? By bringing humanity back into the picture! That could be what the letter h stands for. After all, why should the residents of H be men—and hairy ones at that? Where are the women? Women who shave others, shave themselves, or do not shave themselves? Or could the moral of the story be... that the barber was a woman... and that Russell and his contemporaries were men...
But then, to turn the question back on them... who does the hairdresser's hair?
