Conversation

Cantor's claim is that the infinity of the set real numbers, |ℝ|, is larger than the infinity of the set of counting numbers, |ℕ|. If Cantor is wrong, then there must be a function 𝑓:ℕ⟶ℝ such that the set of real numbers, ℝ, is exactly the same as the image of all natural numbers under function 𝑓, 𝑓(ℕ) = { 𝑓(1), 𝑓(2), 𝑓(3), ... }. If Cantor is right, then there is no such function, 𝑓 where 𝑓(ℕ) = ℝ.

Cantor's diagonal argument is, at its heart, a proof that a set of size 2^n is strictly larger than n, is true for all n when n is the size of a set, and this works for infinite sets. If n is 3, we have A = {1, 2, 3}, B={000, 001, 010, 011, 100, 101, 110, 111}, and if 𝑓(1) = 𝑎𝑏𝑐, 𝑓(2) =𝑟𝑠𝑡, 𝑓(3) = 𝑥𝑦𝑧, the symbol D = 𝑎𝑠𝑧 might or might not be in 𝑓(A), but D̅ = 𝑎̅𝑠̅𝑧̅ cannot be. We know 𝑓(1) ≠ D̅ since 𝑎 ≠ 𝑎̅; we know 𝑓(2) ≠ D̅ since 𝑠 ≠ 𝑠̅; we know 𝑓(3) ≠ D̅ since 𝑧 ≠ 𝑧̅, so we know 𝑓(A) failed to include all the elements of B. The diagonal argument is not a procedure or task to be carried out, but logical reasoning about operating 𝑓 on the whole of A at once, even when A is an infinite set, like ℕ.

ℕ and ℝ are already concrete. ℝ^ℕ, the set of all injective functions from ℕ into ℝ, is already concrete. So 𝑓 is an element of ℝ^ℕ and 𝑓(ℕ) ≠ ℝ, because none of the injective functions from ℕ into ℝ is also an surjective function from ℕ onto every element of ℝ. That's pretty much the definition of "larger."

Since D̅ differs from 𝑓(𝑛) at the 𝑛th position, D̅ cannot be an element of 𝑓(ℕ) because there is no 𝑛 such that 𝑓(𝑛) = D̅.

Effectively, Cantor's diagonal argument is the proposition that describes a concrete 𝑔:ℝ^ℕ⟶ℝ such that for all 𝑓 in ℝ^ℕ, 𝑔(𝑓) = D̅, is in ℝ but not in 𝑓(ℕ).

#Cantor #DiagonalArgument