Cantor’s Diagonal Argument

Because of its importance to the IFF metastack, we discuss, quote and paraphrase here in some detail Cantor’s diagonal argument as presented in the book Sets for Mathematics (2003) by Lawvere and Rosebrugh. As discussed in that book, in the nineteenth century George Cantor proved an important theorem using a diagonal argument, which implies the result that any set X is smaller than its power set

X < 2^X = PX.

(For sets X and Y, the inequality X ≤ Y means that there exists at least one injection from X to Y, and the strict inequality X < Y means X ≤ Y and that no surjection X → Y exists.) The two essential ingredients in Cantor’s argument are the diagonal function and a fixed point free map. As Lawvere and Rosebrugh point out,

Definition 1. Let Y be any set. An endofunction τ : Y → Y has an element y ∈ Y as a fixed point when τ(y) = y. The endofunction τ : Y → Y is fixed point free when no element of Y is a fixed point. The set Y has the fixed point property when no endofunction τ : Y → Y is fixed point free; that is, every endofunction τ : Y → Y has at least one fixed point.

Although there are objects in the category of continuous spaces with the fixed point property (Brouwer: n-dimensional unit ball), most abstract sets do not have the fixed point property. We prove the contrapositive of Cantor’s theorem.

Theorem 1. Suppose there is a set X and a function φ : X×X → Y whose curry φ̂ : X → Y^X, where φ̂(a) = φ(a,–) for all a ∈ X, is surjective; that is, such that for every function f : X → Y there is at least one element a ∈ X such that f = φ̂(a) = φ(a,–). Then Y has the fixed point property.

Proof: Consider any endofunction τ : Y → Y. We must show that τ has a fixed point. Using the diagonal function δ_X : X → X×X, define the function f = δ_X · φ · τ : X → X×X → Y → Y. In other words, for all x ∈ X, f(x) = τ(φ(x,x)). By the assumption, f = φ(a,–) for some element element a ∈ X; that is, f(x) = φ(a,x) for some element element a ∈ X and all elements x ∈ X. Hence, τ(φ(x,x)) = φ(a,x) for all x ∈ X. In particular, letting x = a, τ(φ(a,a)) = φ(a,a). Hence, φ(a,a) = φ(δ_X(a)) is a fixed point of τ. □

Corollary 1 (Cantor). If a set Y has at least one endofunction τ : Y → Y with no fixed points, then for every set X there is no surjection X → Y^X.

Corollary 2. For any set X,

Proof: Let 2 be the set of two elements 2 = {0,1}. Logical negation ¬ : 2 → 2, defined by ¬(0) = 1 and ¬(1) = 0, has no fixed point. Hence, there is no surjection X → 2^X = PX. But, the singleton map {–} : X → 2^X = PX is injective. □

Corollary 3. There cannot exist a “universal set” U for which every set X is a subset X ⊆ U.

Proof: If so, then the inclusion X → U is an injection. Hence, the exponent map 2^U → 2^X is a surjection. Define X = 2^U to get a contradiction. □

Corollary 4. The collection set of all sets is not a set.

Proof: If set were a set, then U = ∪set = ∪{X | X ∈ set }, the union of all sets, would be a well-defined set. But, U would clearly be a “universal set”. Hence, the assumption that set is a set leads to a contradiction. □

Let us take inventory of the assumptions on sets that were needed to prove this. We have assumed that sets have: (basic) singleton maps, diagonal maps, local unions, the two-element (truth-value) set 2, logical negation; (finite limits) terminal elements, finite products; and (exponents) exponent sets, curry operators, exponent functions. What is the meaning of “local union”. A local union operator at level n maps a level n set of level n sets to a level n set (consisting of all elements in at least one of the component sets), and hence is a function ∪ : Pset_n → set_n, where Pset_n = {X ⊂ set_n | X ∈ set_n}. A local union is equivalent to an “indexed union”, which takes an level n indexed collection of level n sets {X_i ∈ set_n | i ∈ I ∈ set_n} to a level n set. These notions are stronger than the ordinary “powerset union” operators ∪ : PPX → PX for level n sets X ∈ set_n.