JRStern
Posts:
35
Registered:
10/27/12


Re: Peerreviewed arguments against Cantor Diagonalization
Posted:
Oct 28, 2012 8:27 PM


On Sun, 28 Oct 2012 15:25:27 0700 (PDT), Arturo Magidin <magidin@member.ams.org> wrote:
>On Saturday, October 27, 2012 4:49:32 PM UTC5, JRStern wrote: >> Are there any such published? > >You said elsewhere you are interested in "peerreviewed" criticisms to >Cantor's diagonal argument, but not from the point of view of intuitionism >or some other logical framework, but strictly within the context of ZFC. > >There are no such things, because the argument is a valid argument >within ZF. It is in fact pretty short and clear.
Then there can be a book taking on the objections one at a time and knocking them down.
>Recall that given a set X, the Axiom of the Power Set states that >there is a set Y such that z in Y if and only if z is a subset of X. >We call this set the "power set of X", an denote it P(X). > >THEOREM (Cantor) Let X be any set, and let P(X) be the power set of >X. If f:X>P(X) is any function, then f is not onto; that is, there >exists B in P(X) that does not lie in the image of f. > >Proof. Let f:X>P(X) be a function. By the Axiom of Separation, > >B = {x in X  x is not an element of f(X)} > >is a subset of A, hence an element of P(X). We claim that f(y)=/=B for all y\in X. > >Indeed, let y in X. Either f(y)=/=B, or f(y)=B. If f(y)=B, >then y in B > y in f(y) > y not in B; since (P>not(P))>not(P) is a tautology, >we conclude that f(y)=/=B. So if y in X, then f(y)=/=B, proving that B is not >in the image of f. QED
... and not just telling us that there are other theories with the same consequent.
J.
> >LEMMA 1: There is a bijection g:(0,1)>P(N), where P(N) is the power set of the natural numbers. > >Proof: There is an injection (0,1) to P(N) as follows: given any number x in (0,1), we can express x in base 2; if there are two expressions for x in base 2, then select the one with finitely many 1s. Map the number x = 0.a_1a_2a_3... to the set S = {n in N  a_n=1}. The map is easily seen to be onetoone (given that we have specified which expansion to use). > >And there is an injection from P(N) to (0,1): given a subset X of N, let x be the real number Sum (a_n/10^n), where a_n=5 if n is not in X, and a_n=6 if n is in X. Again, this is easily seen to be an injection. > >Since we have an injection (0,1)>P(N), and an injection P(N)>(0,1), the CantorBernsteinSchroeder Theorem guarantees (in ZF) the existence of a bijection g:(0,1)>P(N). QED > > >COROLLARY: If f:N>R is any function, where N is the natural numbers and R is the real numbers, then f is not onto. > >Proof: First, there is a bijection h between R and (pi/2,pi/2), given by the arctan function; and there is a bijection t between (pi/2,pi/2) and (0,1), given by t(x) = (x+(pi/2))/pi. And from Lemma 1, we have a bijection g from (0,1) to P(N). Note that the compositum gth:R>P(N) is a bijection. > >Let f:N>R be any function. Then the compositum gthf is a function N>P(N). By Cantor's Theorem, this function is not onto. In particular, there exists a subset X of P(N) that is not in the image of gthf. Now let r = (gth)^{1}(X) (the function (gth)^{1} exists because gth is a bijection); then r is not in the image of f (for if r = f(n), then (gth)^{1}(X) = f(n), so X = (gth)((gth)^{1}(X)) = gth(f(n)) = gthf(n), which contradicts the choice of X). > >Thus, f is not onto, as claimed. QED

