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 12:14 PM

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 about exactly what argument you are talking about.

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

> >The government doesn't like it when I read minds without a
>
> >warrant, so I try not to do it, you see.
>
>
>
> There are constructivist objections to the whole enterprise. If
> nothing else, I was hoping to see something like these addressed
> against the diagonal argument piecemeal.

In a constructivist universe, you cannot have a function defined on the natural numbers, and you cannot have a set of real numbers at all. The very premise ("Suppose f:N-->(0,1) is a function") is considered nonsensical in the constructivist point of view.

You can only talk about a "rule" that will allow you, in principle, to compute f(n) up to any degree of exactness that you care to specify. You can encode the procedure in the proof given assuming that the function f is given by Turing Machine which, when given n as an input, will give you the number of a Turing machine that computes f(n). Then you can establish the existence of a Turing machine r which, when given as input the number of a Turing machine that computes a function f as described above, will produce as an output the sequence b_n which is not equal to the output of any Turing machine whose number is produced by the Turing machine corresponding to f. That much is allowable within the computational universe.

> I'm vaguely aware of some of the several paradoxes of set theory.

There were several antinomies in the original, naive version of Set Theory, which included things like "unlimited comprehension" (which allowed almost any expression to define a set).

There are no known antinomies in Axiomatic Set Theory.

As for paradoxes, recall that a paradox is **not** (as is commonly believed) a logical contradiction, but merely means "a statement that is **seemingly** contradictory or opposed to common sense, and yet is perhaps true."

Yes, there are paradoxes that derive from set theory (usually through the use of the Axiom of Choice, such as the Banach-Tarski paradox), but they do not represent a logical contradiction: they represent a failure of intuition. In any case, Cantor's Theorem does not require the Axiom of Choice; and even if it did, Goedel demonstrated (using techniques that are accepted by constructivists) that *if* there is any logical contradiction that arises from using the Axiom of Choice, *then* that logical contradiction is already present in set theory without using the Axiom of Choice. He also demonstrated (again, using techniques that are accepted by cosntructivists) that the Constructivist version of set theory suffers from the same problems that regular ZF set theory does: if it is consistent, then it is incomplete; and if it is consistent, then it cannot provide a constructivist proof of its own consistency.

> Another question I have is whether the structure of the diagonal
>
> argument doesn't include something like that.

Since you don't specify what "something like that" might be, it is impossible to answer your question. It may very well be that the diagonal argument contradicts your intuition, and as such is paradoxical to you. But that would only mean your intuition isn't up to par in this instance.

> >I have given you a complete proof of Cantor's Theorem; the
>
> >diagonal argument is embedded in that theorem.
>
>
>
> What does that mean to you, or me: "embedded"?

It means that it is a small part of the argument. The diagonal argument is contained in the part of the proof I gave which constructed the set B given by

B = { x in X | x not in f(x) }

If you represent real numbers as binary sequences, and ignore the issue of dual representation (so that we consider the sequence 0.1000000.... to be a "different number" from the sequence 0.011111...., even though viewed as binary expansions they represent the same real number), then the set B corresponds *exactly* to the "diagonal argument" given in the form of taking a list of real numbers written in binary expansion and "going down the diagonal" changing the digits. I'll leave it to you as an exercise to verify this.

The issue of dual representation *is* something to be careful with, but it can be dealt with.

>
>
>
> Can you throw me a bone here, like use the word "diagonal"?
>
>
>

> >What is it that you find incoherent?
>
>
>
> Is it not true that what you've given is more like a rephrased version
>
> of Cantor's original proof, and not at all of his later offered
>
> diagonal argument?

Cantor's "original proof" of uncountability of the real numbers involved an intersection of a nested sequence of closed sets, though it is not very well known, and has little resemblance to the proof of Cantor's Theorem, or of the usual presentations using 'diagonal numbers'. So, no. As for his *second proof*, again, no. I've given the standard proof of Cantor's Theorem.

What you usually seen is an application to the specific case, and like I said, there are some mangled presentations out there.

But, look: you say you don't know much about the subject, but you want to see criticisms of the argument. Shouldn't you have asked *first* for the argument, since you say you don't know it very well, before starting to ask for criticisms of the argument? One cannot understand criticisms to X until one knows what X is.

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