Search All of the Math Forum:
Views expressed in these public forums are not endorsed by
Drexel University or The Math Forum.
|
|
|
|
Re: Cantor's Proofs
Posted:
Oct 13, 2011 1:09 PM
|
|
Dick <DBatchelo1@aol.com> writes:
> Cantor provided two proofs that the real numbers are ?uncountable.?
>
> First proof.
> If the reals are enumerable then each real has a corresponding integer
> and they can be written in a sequential list.
> The interval (0,1) contains a point that is not in this list. To prove
> this choose the first two numbers in the list that are inside this
> interval. They define a smaller interval. Now choose the first two
> numbers in the list that are inside this smaller interval and repeat
> the process. . There are a couple of cases to worry about, but this
> process provides sequences whose limit is NOT in the original list.
> Hence: NO ENUMERABLE LIST IS COMPLETE
> The reals are complete; and so THERE IS NO ENUMERABLE SET THAT IS A
> MODEL FOR THE REALS.
> This proof makes use of the fact that the reals are complete. I find
> it convincing.
>
> Second proof
> If the reals are enumerable they can be written in a list,
> ?Diagonalization? produces a number that is not on the list. Hence the
> reals are uncountable.
> I don?t find this conclusion valid.
>
> First, some definitions.
> A set is ?recursively- enumerable? if there is a (simple) Turing
> Machine that produces it.
>
> Suppose that a Turing Machine has an ?oracle? that will answer ?1' if
> a number is in a set A and ?0' otherwise. A set is ?A-recursively-
> enumerable? if it can be produced by a Turing Machine that has an
> oracle for set A. (Machines with an oracle are "non-simple")
>
> A real number is ?computable? if it can be produced by a simple TM. It
> is ?A-computable? if it can be produced by a TM with an oracle for A.
>
> I will call a set ?Goedelizable? if each member can be associated with
> a different integer (its ?Goedel Number?) (There are other names for
> this concept, including ?subcountable?(used by constructivists) and
> ?enumerable? (as used by classic mathematicians. However each of these
> words carries some ?baggage? that may be confusing. ?Goedelizable is
> not likely to be misunderstood)
>
> A set P is called a ?productive set? if it has the property. that
> there is a ?productive function? that, when applied to any recursively
> enumerable subset of P will produce a member of P that is NOT in the
> recursively-enumerable subset.
>
> There are many examples of productive sets. One relevant here is the
> set of computable numbers. Its ?productive function? is
> ?diagonalization?; if S is a recursively-enumerable subset of the
> computables then the diagonalization of S is a computable number that
> is not in S.
>
> So, consider the set of computable reals. Take any recursively-
> enumerable subset. Diagonalization produces a number not on the list.
> However, all that this proves is that the computable nymbers are not
> recursively-enumerable. They are Goedalizable.. They form a
> productive set (with?diagonalization? as productive function.)
>
> The computable reals are NOT recursively-enumerable. However, one can
> form a list of all Goedel numbers. This list obviously contains as a
> sublist the Goedel numbers of the computable numbers. The obvious next
> step is to say ?Let me supposr that I have a way to tell if an
> arbitrary Goedel number is a computable real or not. Then I can list
> the computable reals.?
> Put more formally: if A is the set of Goedel numbers of computable
> reals then the set of computable reals is A-recursively-enumerable
> The diagonalization of this A-recursively-enumerable list is an A-
> computable number. It is not a computable number. If we are to
> consider it a real number we must broaden the definition of real from
> computable real to A-computable real. We then find that this enlarged
> set is A-productive (and not A-recursively enumerable. We are in the
> same predicament as before!
>
> This process of progressively enlarging the set can be carried out
> repeatedly. The family of increasing sets produced is called the
> ?Kleene Hierarchy.? The Kleene Hierarchy has no maximum.
>
> Let me go back to the computable reals and take the point of view of a
> Constructivist. A Constructivist holds that nothing exists unless a
> procedure can be described to actually build it. Thus, to him, the
> only real numbers are the computable reals. They are:
> Not enumerable (The only concept of enumerable that is acceptable is
> recursive-enumerable.)
> Goedelizable.
>
> Talk to him about forming the diagonalization of the full set of
> computables and he will look at you pityingly and say ? There is NO
> WAY to build the list you want. Therefore its diagonalization does not
> exist.?
>
> To confound the Constructivist ypu must point out that not all bounded
> recursively-enumerable sets have a Least Upper Bound. (This is true
> and is the main reason that Constructivism id so difficult.) However,
> this is NOT stated in the conditions of Cantor?s proof!
I am baffled by this bit. Why should the proof make any reference to
the LUB of RE sets?
> The distinguishing feature of the teal number field is that it is
> complete; that it contains the least upper bound of each of its
> bounded subsets. Cantor?s first proof uses this. The second does
> not.It seems unlikely that a ?proof? that it is ?uncountable? (not
> Goedelizable) that does not use this fact will be valid.
Surely it does use the fact that R is complete? Simply remove any
single real from the interval in question and the argument fails.
--
Ben.
|
|
|
|
