Let S be the set of all real numbers that can be described precisely. (For example, the following is a precise description of a real number: x = 0.01011011101111..., where the nth "block" after the decimal point is of the form 01...1, one zero followed by n ones.) Each description is a finite sequence of symbols from a finite "alphabet" A that we agree on ahead of time. (For example, A could be the set of all Roman and Greek letters, the digits 0-9, punctuation symbols, and mathematical symbols.) Let T be the set of all finite sequences of symbols from the alphabet A (regardless of whether or not the sequence of symbols describes a real number).
(i) Show T is denumerable. Also show there exists a surjection from T to S. Conclude that S is denumerable.
(ii) It follows from (i) that S is also denumerable, so we can write S = { x0, x1 , x2, ...}. Let di,j be the jth digit after the decimal point in xi. (We start counting with 0; e.g., if x5 = Pi = 3.14..., then d5,0 is 1.) Let z = 0.b0b1b2... , where bi = di,i + 1 (mod 10). Show z is different from xi for every i.
(iii) It follows from (ii) that z is not in S. But z is a real number described precisely in (ii). So z is in S. Resolve this paradox!