The Diagonal Argument

This is just a second look at the question of the relative magnitudes of a set and the set of its subsets.

Let R be a set, and F a function that maps x ∈ R to a subset of R, F(x) ⊂ R. In other words, F: R → 2^R.

Such a function can be visualized in a square R × R. For every x ∈ R, F(x) can be depicted in the vertical unit segment just over x. We'll call it G(x), G(x) = {x} × F(x).

Now, for some x, G(x) crosses the diagonal D = {(x, x)}, G(x) ∩ D ≠ Ø; and for some x, G(x) does not cross the diagonal, G(x) ∩ D = Ø. Of course, G(x) ∩ D ≠ Ø is equivalent to x ∈ F(x), and G(x) ∩ D = Ø is equivalent to x ∉ F(x).

Introduce set Z of all x with the latter property:

Z = {x ∈ R: G(x) ∩ D = Ø} = {x ∈ R: x ∉ F(x)}.

(Quite obviously the introduction of the diagonal D was not strictly necessary. But its presence illuminates the reason why the proof of the following theorem is known as the diagonal argument.)

Theorem

For no x ∈ R, F(x) = Z.

Proof

Suppose on the contrary that, for some a, F(a) = Z. We may ask then whether or not a ∈ Z. We shall see that both possibilities lead to a contradiction.

Assume first that a ∈ Z. This would mean G(a) ∩ D = Ø, implying that a ∉ F(a), i.e., a ∉ Z.

Assume now that a ∉ Z. This would mean G(a) ∩ ≠ Ø, implying that a ∈ F(a), i.e., a ∈ Z.

Corollary 1

No function R→ 2^R can be onto.

Corollary 2

Corollary 3

The set of the reals is uncountable.

Proof

Let R = [0, 1] and N is the set of positive integers. If we think of the reals as represented by their binary expansions, then, with some caveats, each such expansion is a characteristic function of a subset of N which associates with every x ∈ R a subset of N, viz., the subset of the indices whose corresponding digits in the binary expansion of x are 1. Such an association tells us that |R| = |2^N|. And Corollary 2 then implies that |R| > |N|.

It is clear that uncountability of the reals and Russell's Paradox are of the same origin.

References

1. K. Kuratowski, A. Mostowski, Set Theory, North-Holland; 2nd revised edition (February 26, 1976)

Uncountability of Real Numbers

• Irrational Numbers: Diagonal Argument with Decimals
• The Diagonal Argument
• Uncountability of the Reals - via a Game
• Cantor's First Uncountability Proof
• The set of all subsets of a given set

Self-reference and apparent self-reference

1. Does It Blink?
2. Apparent paradox
3. Set of all subsets
4. An Impossible Page
5. Russell's paradox
6. An Impossible Machine
7. A theorem with an obvious proof
8. The Diagonal Argument
9. A link to a very similar puzzle

|Contact| |Front page| |Contents| |Algebra| |Store|

Copyright © 1996-2012 Alexander Bogomolny