Drexel dragonThe Math ForumDonate to the Math Forum



Search All of the Math Forum:

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


Math Forum » Discussions » sci.math.* » sci.math

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

Advanced Search

Back to Topic List Back to Topic List Jump to Tree View Jump to Tree View   Messages: [ Previous | Next ]
magidin@math.berkeley.edu

Posts: 11,147
Registered: 12/4/04
Re: Peer-reviewed arguments against Cantor Diagonalization
Posted: Oct 28, 2012 6:25 PM
  Click to see the message monospaced in plain text Plain Text   Click to reply to this topic Reply

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


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

Point your RSS reader here for a feed of the latest messages in this topic.

[Privacy Policy] [Terms of Use]

© Drexel University 1994-2014. All Rights Reserved.
The Math Forum is a research and educational enterprise of the Drexel University School of Education.