Date: Oct 28, 2012 8:20 PM
Author: INFINITY POWER
Subject: Re: Peer-reviewed arguments against Cantor Diagonalization

On Oct 29, 8:25 am, Arturo Magidin <magi...@member.ams.org> wrote:> On Saturday, October 27, 2012 4:49:32 PM UTC-5, JRStern wrote:> > Are there any such published?>> You said elsewhere you are interested in "peer-reviewed" 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.>> 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>> 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 one-to-one (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 > Cantor-Bernstein-Schroeder 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>> --> Arturo MagidinIn Peano Arithmetic, the relation e(#NUM,#NUM) can represent set membership.e(1,1)e(2,1)e(3,1)e(2,2)e(4,2)e(6,2)e(7,3)e(8,3)e(9,3)set1 = {1,2,3)set2 = {2,4,6}set3 = {7,8,9}B = {x in X | x is not an element of f(X)}SOB = {x | ~xex}--------------------------------THAT A PURE SET ARGUMENTHERE IS AN INFINITE SET ARGUMENT--------------------------------http://freewebs.com/namesort/matheology/powersets.htmlFor any 2 infinite sets f & g of subsets of N.f(1) = { 3 4 7 8 9 11 }f(2) = { 7 10 12 13 16 20 }f(3) = { 1 6 8 12 18 19 }f(4) = { 1 6 16 }f(5) = { 2 4 5 6 8 13 18 }f(6) = { 1 3 7 11 12 17 }f(7) = { 1 4 5 7 10 11 13 17 }f(8) = { 2 5 6 7 9 16 20 }f(9) = { 4 9 10 }f(10) = { 2 6 7 8 9 11 14 15 16 17 20 }f(11) = { 5 11 12 20 }f(12) = { 2 3 6 10 14 17 18 }f(13) = { 3 4 6 9 18 }f(14) = { 1 4 8 9 12 15 16 19 20 }f(15) = { 1 2 7 11 14 16 19 }f(16) = { 1 6 9 13 14 16 20 }f(17) = { 2 4 5 10 11 13 16 17 }f(18) = { 1 2 3 5 8 9 10 17 }f(19) = { 6 7 11 13 }f(20) = { 2 7 13 14 15 18 }...B = {x in X | x is not an element of f(X)}  = { 1 2 3 4 6 8 10 12 13 14 15 18 19 20 ...}--------------------------------g(1) = { 1 2 9 11 12 14 17 19 }g(2) = { 9 10 12 14 15 20 }g(3) = { 1 3 8 10 12 20 }g(4) = { 1 2 3 4 6 11 12 17 18 19 }g(5) = { 3 4 5 7 8 9 11 13 15 }g(6) = { 1 8 12 13 18 }g(7) = { 7 10 11 20 }g(8) = { 2 3 4 5 7 16 }g(9) = { 1 5 11 13 18 }g(10) = { 5 8 9 10 14 17 18 19 }g(11) = { 3 }g(12) = { 4 5 6 8 9 13 }g(13) = { 1 2 4 5 7 9 11 12 18 }g(14) = { 3 5 6 8 18 }g(15) = { 1 2 3 6 9 13 15 17 19 }g(16) = { 1 8 9 10 14 17 }g(17) = { 1 3 4 5 10 11 14 17 }g(18) = { 1 7 8 13 15 }g(19) = { 2 3 4 6 9 12 14 15 19 }g(20) = { 3 4 6 10 17 }...C = {x in Y | x is not an element of f(Y)}{ 2 6 8 9 11 12 13 14 16 18 20 ...}--------------------------------f'f(1) = { 3 4 7 8 9 11 }f(2) = { 7 10 12 13 16 20 }f(3) = { 1 6 8 12 18 19 }f(4) = { 2 4 5 6 8 13 18 }f(5) = { 1 6 16 }f(6) = { 1 3 7 11 12 17 }f(7) = { 1 4 5 7 10 11 13 17 }f(8) = { 2 5 6 7 9 16 20 }f(9) = { 4 9 10 }f(10) = { 2 6 7 8 9 11 14 15 16 17 20 }f(11) = { 2 3 6 10 14 17 18 }f(12) = { 3 4 6 9 18 }f(13) = { 5 11 12 20 }f(14) = { 1 4 8 9 12 15 16 19 20 }f(15) = { 1 2 7 11 14 16 19 }f(16) = { 1 2 3 5 8 9 10 17 }f(17) = { 2 4 5 10 11 13 16 17 }f(18) = { 1 6 9 13 14 16 20 }f(19) = { 6 7 11 13 }f(20) = { 2 7 13 14 15 18 }...---------------------------g'g(1) = { 9 10 12 14 15 20 }g(2) = { 1 3 8 10 12 20 }g(3) = { 1 2 9 11 12 14 17 19 }g(4) = { 1 2 3 4 6 11 12 17 18 19 }g(5) = { 1 8 12 13 18 }g(6) = { 3 4 5 7 8 9 11 13 15 }g(7) = { 7 10 11 20 }g(8) = { 2 3 4 5 7 16 }g(9) = { 5 8 9 10 14 17 18 19 }g(10) = { 1 5 11 13 18 }g(11) = { 3 }g(12) = { 4 5 6 8 9 13 }g(13) = { 1 2 4 5 7 9 11 12 18 }g(14) = { 3 5 6 8 18 }g(15) = { 1 8 9 10 14 17 }g(16) = { 1 2 3 6 9 13 15 17 19 }g(17) = { 1 3 4 5 10 11 14 17 }g(18) = { 1 7 8 13 15 }g(19) = { 3 4 6 10 17 }g(20) = { 2 3 4 6 9 12 14 15 19 }...---------------------------------B' = {x in X | x is not an element of f'(X)}   = { 1 2 3 5 6 8 10 11 12 13 14 15 16 18 19 20 ...}C' = {x in Y | x is not an element of f'(Y)}   = { 1 2 3 5 6 8 10 11 12 13 14 15 16 18 19 20 ...}----------------------------------That is:  the 'missing subset' of any' infinite set of subsets are the same, depending on the enumeration not the data in the set.Herc