# 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, ^{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),

Now, for some x, G(x) crosses the diagonal

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

^{R}is strictly greater than the cardinality of R:

|2^{R}| > |R|.

### 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 ^{N}|.

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

### References

- 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

- Does It Blink?
- Apparent paradox
- Set of all subsets
- An Impossible Page
- Russell's paradox
- An Impossible Machine
- A theorem with an obvious proof
- The Diagonal Argument
- A link to a very similar puzzle

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

Copyright © 1996-2018 Alexander Bogomolny

63713432 |