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


On Oct 29, 8:25 am, Arturo Magidin <magi...@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. > > 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 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 > >  > Arturo Magidin
In 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)}
SO B = {x  ~xex}

THAT A PURE SET ARGUMENT
HERE IS AN INFINITE SET ARGUMENT

http://freewebs.com/namesort/matheology/powersets.html
For 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

