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 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