| This presents a confused understanding of Cantor's diagonalization argument. You are shrouding in complexity something that is straightforward. The complete proof of distinct infinite cardinalities can be stated succinctly and clearly in only a few lines, without referencing the reals at all. You don't need to vaguely refer to "four steps", you should precisely elaborate the steps of the proof you view as problematic. First, forget the reals. Let's establish that there are sets that are infinite yet uncountable. ---- "Uncountable" means that there is no bijection with (a subset of) the natural numbers. An "infinite sequence of A's" means a function ℕ → A. For convenience, I'll denote the set of infinite sequences of A's with `A**` -- this is not standard notation. Theorem: There is no bijection between ℕ and {0, 1}**. Proof: Suppose for contradiction that there is a bijection f: ℕ → {0,1}**. Define a function z(n) = 1 - f(n)(n). z is clearly well defined and is clearly a member of {0,1}**. Since f is a bijection and z is in the codomain of f, there is an element k of ℕ such that f(k) = z. However, z(k) = 1 - f(k)(k). Yet f(k) = z, so z(k) = 1 - z(k). This is a contradiction. So, the assumption (that there exists a bijection f: ℕ ↔ {0,1}**) must be false. Q.E.D.: There does not exist a bijection between ℕ and {0, 1}**. ---- The linked paper claims that the above proof would work on a bijection of the form ℕ ↔ [ℕ] or ℕ ↔ [ℚ] (where the [] indicate some suitable representation of the set as sequences of bits; again, not standard notation), but that is mistaken: crucially, the constructed function `z` must be a member of the codomain of `f`. The construction 1 - f(n)(n) does not necessarily lie in that set when the set only permits _certain_ bit-sequences! For example, consider an encoding [ℕ] which is "one-hot"; the natural n is encoded as a function y(n) = 1 and otherwise y(k) = 0. Then there is an obvious bijection `f`: f(a, b) = 1 when a=b and otherwise 0. What is `z` for such an `f`? z(k) = 1 - f(k, k) = 1. So, `z` is not a member of [ℕ]. For a more involved example, consider an encoding of [ℕℕ] that is a unary-encoding of the first natural, followed by a single zero, followed by a unary encoding of the second natural, and followed by only 0s. (The rationals correspond to a subset of these). A standard bijection has the pairs appear in the order of their sum: (0, 0), (0, 1), (1, 0), (2, 0), (1, 1), (0, 2), ... It's an exercise left for the reader that z constructed on this set does not encode to a unary number, followed by a single zero, followed by a unary number, followed by only zeros. ---- If you have an issue with cardinalities, I expect it can be found in the above proof and does not actually lie with the reals. But, for completion, to tie in the real numbers, it's necessary to show that {0,1}** is bijective with ℝ, or with (0, 1). This falls out from the Cauchy-sequence definition of ℝ. For a sequence y : {0,1}** the sequence z(k) = y(0) + 1/2·y(1) + 1/4·y(2) + 1/8·y(3) + ... + 1/2^k·y(k) is clearly a Cauchy sequence with a limit in the interval [0, 1]. It's also straightforward to check that every real number in the interval [0, 1] is the limit of one such Cauchy sequence. |
I don't understand the notation f(n)(n). Is it related to f_{nn} in LaTeX notation? Your later text suggests maybe it was aiming at f(n,n) so I will assume that.
I recognise a form of this argument and I might have tackled it in the supplementary materials I created that are referenced in the article. Let me know.
> However, z(k) = 1 - f(k)(k). Yet f(k) = z, so z(k) = 1 - z(k).
I'm assuming this was intended to be: z(k) = 1 - f(k). Yet f(k) = z, so z(k) = 1 - z(k).
For some k, z(k) = 0.5. f(k) = 0.5. Seems Ok.