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 ]
 magidin@math.berkeley.edu Posts: 11,749 Registered: 12/4/04
Re: Peer-reviewed arguments against Cantor Diagonalization
Posted: Oct 29, 2012 11:44 PM

On Monday, October 29, 2012 9:38:59 PM UTC-5, Peter Webb wrote:
> Arturo Magidin wrote:
>
>
>

> > On Monday, October 29, 2012 9:37:20 AM UTC-5, JRStern wrote:
>
> > > On Sun, 28 Oct 2012 19:20:51 -0700 (PDT), Arturo Magidin
>
> > >
>
> > > <magidin@member.ams.org> wrote:
>
> > >
>
> > >
>
> > >
>
> > > >> How can this be unclear?
>
> > >
>
> > > >
>
> > >
>
> > > > Because I did not simply state the conclusion.
>
> > >
>
> > > > I gave you the "diagonal argument".
>
> > >
>
> > >
>
> > >
>
> > > I did not recognize the argument you gave as a/the "diagonal"
>
> > >
>
> > > argument.
>
> >
>
> > That suggests you are not very familiar with the argument.
>
> >
>
> > > I saw a separate argument for the same conclusion.
>
> >
>
> > It was not.
>
> >
>
> > > The diagonal argument as I've seen it starts with enumerations of
>
> > >
>
> > > numbers, selects out digits, and constructs from those digits, and
>
> > >
>
> > > then makes an assertion about the result.
>
> >
>
> > Like I said: if you want to discuss specific steps in a specific
>
> > argument, then you must provide that argument explicitly and in
>
> > detail. Otherwise, we may be talking about different things.
>
> >
>
> > I will allow that there are many expositions of the argument that are
>
> > not very precise, or very clear, or that are overly complicated (it
>
> > is very common to present the argument as an argument by
>
> > contradiction, although it really is not such). But that only makes
>
> > it all the more necessary that you be very explicit and very precise
>
>
> >
>
> > > > If you are questioning whether it is "coherent", then you should
>
> > >
>
> > > > point to whatever point you find incoherent, rather than simply
>
> > >
>
> > > > quote and then give a sentence fragment.
>
> > >
>
> > >
>
> > >
>
> > > This is (perhaps too obviously) not my area of expertise, and rather
>
> > >
>
> > > than try to present my own proof or even formal objection at this
>
> > >
>
> > > point - I came looking for further background.
>
> >
>
> > A common presentation of the corollary (which in reality can be
>
> > obtained from the presentation I gave), is the following:
>
> >
>
> > THEOREM. If N is the natural numbers, (0,1) are the real numbers
>
> > between 0 and 1, not inclusively, and f:N-->(0,1) is any function,
>
> > then f is not onto. That is, there exists a real number r(f) (which
>
> > depends on f) such that f(n)=/=r(f) for every n in N.
>
> >
>
> > Proof. Suppose that f:N-->(0,1) if any function from the natural
>
> > numbers to the numbers in (0,1) (this is equivalent to a function
>
> > from N to the reals, using the bijection between (0,1) and the reals
>
> > afforded by the arctan function and a simple linear map, like I did).
>
> >
>
> > I claim that f is not onto.
>
> >
>
> > To that end, for each n in N, consider the decimal expansion of f(n)
>
> > (if f(n) has two expansions, select the one with only finitely many
>
> > nonzero entries). That is,
>
> >
>
> > f(n) = Sum_{i=1}^infty (a_{n,i}/10^n) 0<= a_{n,i} <= 9
>
> >
>
> > (this is equivalent to saying f(n) = 0.a_{1,1}a_{1,2}a_{1,3}.... is
>
> > the decimal expansion)
>
> >
>
> > We construct a sequence b_n of digits as follows:
>
> >
>
> > b_n = 5 if a_{nn}=/=5
>
> > b_n = 6 if a_{nn} = 5.
>
> >
>
> > The existence of (b_n) is guaranteed by the Principle of Induction,
>
> > which is a theorem of ZF (follows from the construction of N, which
>
> > is well-defined by the Axiom of Infinity).
>
> >
>
> > Let r(f) = Sum_{i=1}^{infty} b_n/10^n.
>
> >
>
> > This is a real number, since the sequence is Cauchy. It is less than
>
> > 1, because it is term by term strictly smaller than Sum (9/10^n) = 1;
>
> > it is greater than 1 because it is term by term strictly larger than
>
> > Sum (1/10^n) = 0.11111.... Thus, r(f) is a real number in (0,1).
>
> >
>
> > I claim that r(f)=/=f(n) for all n. First, note that r(f) has a
>
> > unique decimal expansion; thus, if f(n) has two decimal expansions,
>
> > then it cannot equal r(f). Hence, in order to ensure that r(f)=/=f(n)
>
> > it suffices to show that there is a k such that b_k=/=a_{n,k}
>
> > (because either f(n) has a unique decimal expansion, in which case
>
> > the fact that b_k=/=a_{n,k} suffices; or else f(n) has two decimal
>
> > expansions, in which case it cannot equal r(f)).
>
> >
>
> > By construction, b_k=/=a_{k,k}; hence r(f)=/=f(n). Thus, r(f) is not
>
> > in the range of f, so f is not onto. QED
>
> >
>
> > As to its validity: we are assuming that f is given; the fact that
>
> > f(n) has a decimal expansion follows by construction of the real
>
> > numbers as equivalence classes of Cauchy sequences. Our ability to
>
> > define b_n is guaranteed by the fact that we know f and we know the
>
> > expansion of f(n) (because we know f); and the fact that we have
>
> > defined a full sequence follows by induction. That r(f) is a real
>
> > number follows because the sequence of partial sums is Cauchy, hence
>
> > it represents a unique real number.
>
> >
>
> >
>
>
>
> You have made the proof slightly more rigorous by pointing out the
>
> anti-diagonal is Real using Cachy sequences.
>
>
>
> Two problems with this:
>
>
>
> 1. The cranks don't dispute the anti-diagonal is a Real, so you are not
>
> addressing their issue (whatever it is, but its not that the
>
> anti-diagonal is not Real).

This is only a "problem" if you think that my presentation was an attempt at convincing or arguing with a crank. It was not. I was addressing the Original Poster of this thread, which seems to suffer not from crankiness or "anti-Cantorianism", but rather from simple and pure lack of knowledge about the subject (and a lack of desire to acquire that knowledge, prefering instead to ask and talk in vague terms). It was an attempt at presenting a specific instance of the argument so that he could provide specific questions about specific steps... something, alas, he seem sunwilling to do.

> 2. Your average Cantor crank wouldn't recognise a decimal expansion is
>
> a Cauchy sequence, or that Cauchy sequences specify Real numbers.

Again, only a problem if you think I believe I have provided an "answer" to cranks. I have neither the intention nor the desire to do so.

> You may have been better off proving |P(S)| > |S| (where you have
>

Amusingly enough, I did do so earlier.

> and then showing |c| > |N| is a special
>
> case where S = N. As of course others have done in this thread.

Where "me" happens to be one of the value of "others [...] in this thread".

--
Arturo Magidin

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