Search All of the Math Forum:

Views expressed in these public forums are not endorsed by NCTM or The Math Forum.

Notice: We are no longer accepting new posts, but the forums will continue to be readable.

Topic: Peer-reviewed arguments against Cantor Diagonalization
Replies: 156   Last Post: Nov 4, 2012 3:01 PM

 Messages: [ Previous | Next ]
 INFINITY POWER Posts: 117 Registered: 11/1/11
Re: Peer-reviewed 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 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

Date Subject Author
10/27/12 JRStern
10/27/12 Frederick Williams
10/27/12 JRStern
10/28/12 Tim Little
10/28/12 Peter Webb
10/28/12 JRStern
10/28/12 J. Antonio Perez M.
10/29/12 Michael Stemper
10/29/12 David C. Ullrich
10/29/12 JRStern
10/29/12 JRStern
10/30/12 David C. Ullrich
10/30/12 David C. Ullrich
10/29/12 LudovicoVan
10/27/12 J. Antonio Perez M.
10/28/12 INFINITY POWER
10/28/12 Shmuel (Seymour J.) Metz
10/28/12 Graham Cooper
10/28/12 magidin@math.berkeley.edu
10/28/12 INFINITY POWER
10/28/12 Graham Cooper
10/28/12 Virgil
10/28/12 Graham Cooper
10/28/12 JRStern
10/28/12 magidin@math.berkeley.edu
10/28/12 Graham Cooper
10/28/12 Graham Cooper
10/28/12 magidin@math.berkeley.edu
10/28/12 Graham Cooper
10/28/12 magidin@math.berkeley.edu
10/29/12 Frederick Williams
10/29/12 LudovicoVan
10/29/12 Richard Tobin
10/29/12 LudovicoVan
10/29/12 J. Antonio Perez M.
10/29/12 J. Antonio Perez M.
10/29/12 magidin@math.berkeley.edu
10/29/12 Frederick Williams
10/28/12 Graham Cooper
10/28/12 JRStern
10/28/12 Peter Webb
10/28/12 magidin@math.berkeley.edu
10/28/12 Hercules ofZeus
10/28/12 magidin@math.berkeley.edu
10/28/12 Hercules ofZeus
10/28/12 Arturo Magidin
10/28/12 Hercules ofZeus
10/28/12 Arturo Magidin
10/28/12 Hercules ofZeus
10/29/12 J. Antonio Perez M.
10/29/12 Graham Cooper
10/29/12 JRStern
10/29/12 Frederick Williams
10/29/12 magidin@math.berkeley.edu
10/29/12 Pubkeybreaker
10/29/12 JRStern
10/29/12 magidin@math.berkeley.edu
10/29/12 Graham Cooper
10/29/12 JRStern
10/29/12 magidin@math.berkeley.edu
10/30/12 Graham Cooper
10/30/12 magidin@math.berkeley.edu
10/30/12 Graham Cooper
10/30/12 J. Antonio Perez M.
10/31/12 Peter Webb
10/29/12 Peter Webb
10/29/12 magidin@math.berkeley.edu
10/29/12 Shmuel (Seymour J.) Metz
10/29/12 Virgil
10/29/12 Graham Cooper
10/29/12 Peter Webb
10/29/12 Graham Cooper
10/29/12 Peter Webb
10/29/12 Graham Cooper
10/29/12 Peter Webb
10/29/12 Graham Cooper
10/29/12 Peter Webb
10/30/12 Graham Cooper
10/30/12 Peter Webb
10/30/12 Graham Cooper
10/30/12 Peter Webb
10/30/12 Graham Cooper
10/30/12 MoeBlee
10/30/12 Peter Webb
10/30/12 Graham Cooper
10/31/12 Peter Webb
10/31/12 Graham Cooper
10/31/12 Peter Webb
10/31/12 Graham Cooper
11/2/12 Peter Webb
11/1/12 Peter Webb
11/1/12 Hercules ofZeus
11/2/12 Peter Webb
10/31/12 Peter Webb
10/30/12 Richard Tobin
10/30/12 Graham Cooper
10/30/12 MoeBlee
10/30/12 Graham Cooper
10/30/12 MoeBlee
10/30/12 Graham Cooper
10/31/12 Richard Tobin
10/31/12 Graham Cooper
10/31/12 Graham Cooper
10/31/12 Graham Cooper
10/31/12 Richard Tobin
10/31/12 Graham Cooper
10/31/12 Richard Tobin
10/31/12 Graham Cooper
10/31/12 Graham Cooper
10/29/12 Peter Webb
10/29/12 LudovicoVan
10/29/12 J. Antonio Perez M.
10/29/12 LudovicoVan
10/29/12 Peter Webb
10/29/12 LudovicoVan
10/30/12 Peter Webb
10/30/12 LudovicoVan
10/30/12 Peter Webb
10/30/12 LudovicoVan
10/30/12 Peter Webb
10/30/12 J. Antonio Perez M.
10/30/12 LudovicoVan
10/30/12 Virgil
10/30/12 J. Antonio Perez M.
10/30/12 LudovicoVan
10/31/12 Peter Webb
10/31/12 LudovicoVan
10/31/12 J. Antonio Perez M.
10/31/12 Shmuel (Seymour J.) Metz
11/1/12 LudovicoVan
11/1/12 Jesse F. Hughes
11/2/12 Peter Webb
11/2/12 LudovicoVan
11/2/12 Graham Cooper
11/2/12 Shmuel (Seymour J.) Metz
11/2/12 Virgil
11/2/12 Peter Webb
11/2/12 Peter Webb
11/3/12 J. Antonio Perez M.
11/3/12 Shmuel (Seymour J.) Metz
11/4/12 Peter Webb
11/4/12 Virgil
11/4/12 Shmuel (Seymour J.) Metz
11/1/12 Shmuel (Seymour J.) Metz
10/31/12 Shmuel (Seymour J.) Metz
10/31/12 Shmuel (Seymour J.) Metz
10/29/12 JRStern
10/29/12 Shmuel (Seymour J.) Metz
10/28/12 Graham Cooper
10/28/12 J. Antonio Perez M.
10/29/12 David C. Ullrich
10/29/12 JRStern
10/29/12 LudovicoVan
10/29/12 Fernando Revilla
10/29/12 Shmuel (Seymour J.) Metz