Re: Cantor's Diagonal Argument
- From: The Ghost In The Machine <ewill@xxxxxxxxxxxxxxxxxxxxxxx>
- Date: Sat, 03 Sep 2005 03:00:03 GMT
In sci.logic, Peter Webb
<webbfamily-diespamdie@xxxxxxxxxxxxxxx>
wrote
on Fri, 2 Sep 2005 16:50:03 +1000
<4317f61d$0$25984$afc38c87@xxxxxxxxxxxxxxxxxxxx>:
>
> "The Ghost In The Machine" <ewill@xxxxxxxxxxxxxxxxxxxxxxx> wrote in message
> news:4dsku2-gst.ln1@xxxxxxxxxxxxxxxxxxxxxxxxxx
>> In sci.logic, William of Ockham
>> <d3uckner@xxxxxxxxxxxxxx>
>> wrote
>> on 1 Sep 2005 13:57:39 -0700
>> <1125608259.159687.210780@xxxxxxxxxxxxxxxxxxxxxxxxxxxx>:
>>> A new Wikipedia page
>>>
>>> http://philosophy.wikicities.com/wiki/Cantor%27s_Diagonal_Argument
>>>
>>> has appeared. It is "a page to discuss philosophical objections to
>>> Cantor's Diagonal Argument.", but consists at the moment only of links
>>> to other sites, one of which is mine.
>>>
>>> To avoid any misunderstanding, the page linked to is simply a list of
>>> sources on philosophical writing on infinity, one of which is
>>> Wittgenstein.
>>>
>>> Wittgenstein did have objections to the diagonal argument, but these
>>> were *not* cranky objections to Cantor's Theorem (the theorem that any
>>> attempt to correlate elements of a set with sets of elements, must omit
>>> some sets of elements). Indeed, he argues that the diagonal procedure
>>> for the production of a real number might have been well known before
>>> the invention of set theory, and familiar even to school-children, as a
>>> way of writing down a decimal number which is different from all the
>>> decimals in a long list.
>>>
>>> Wittgenstein's objection is to the idea that there is a set of all such
>>> numbers, and to the idea we can pretend to compare the "set" of real
>>> numbers in magnitude with that of cardinal numbers. " I believe, and I
>>> hope, that a future generation will laugh at this hocus pocus."
>>>
>>> I include some links to new material
>>>
>>> http://uk.geocities.com/frege@xxxxxxxxxxxxxx/cantor/wittgensteinquotes.htm
>>>
>>>
>>> - more Wittgenstein anti-set-theoretic material, and
>>>
>>> http://uk.geocities.com/frege@xxxxxxxxxxxxxx/cantor/cantorquotes.htm
>>>
>>> - selections from Cantor's philosohical writing on the infinite.
>>>
>>>
>>> "William"
>>>
>>
>> Color me slightly puzzled, but one can easily generate an uncountable
>> set of "diagonal numbers".
>>
>
> Please show me an algorithmic procedure for generating an
> uncountable set of Real numbers, whether they appear on a
> countable list or not.
Hmm...I seem to have veered into a minefield. I shall have to
step carefully.
First, there's an interesting issue on how one can construe
"generate" here; the set of all possible algorithms is
finite, or at most countably infinite. (There is a 1-1,
not necessarily onto, mapping between the set of all Turing
machines (including alphabet specifications, if they're
finite) and the natural numbers.)
Given such a definition of "generate", I must admit defeat.
Nevertheless uncountable sets provably exist. Why?
Because for any mapping of N to the interval [0,1) I can
prove that it's not onto, by explicitly constructing an
r known to not be equal to any N(i), by the method of
its construction. Also, r is in [0,1) as well. Hence no
mapping of N to [0,1) is onto.
However, that doesn't mean I can explicitly construct such
a set. The typical definition of a real number involves
squeezing it between two series or using a Dedekind cut
(the two are equivalent AFAIK). If one defines a certain
metric on a rational number -- the simplest one I can think
of is the number of states of the absolute simplest machine
that can provably generate its decimal expansion, given
a blank input tape -- then it's far from clear that one can
deduce whether the squeezed number has to be generated by
a Turing machine with an infinite number of states, for
one might get a lowerbound series of
..3, .33, .333, .3333, ...
and an upperbound series of
..4, .34, .334, .3334, ...
As far as I can tell, the number of states in the Turing machine
generators will grow without bound, but the number at the limit
is 1/3, which can be generated by a turing machine with but
one state and one transition: write a "3" and move.
Of course all this means that there exist elements of R which
can never be computed. The discussion reminds me of
the set of "boring numbers"... :-)
>
> (I can't even see that the Axiom of Choice helps us here,
> and without that, it certainly can't be done, because
> without AC we can only generate computable Reals which
> are a countable subset of R).
>
They are a *finite* subset of R, for various reasons.
(It's not clear how one would easily calculate the upper
limit but obviously no state machine can have more than
about 15 billion light-years' worth of states, where each
state is about the size of an atom -- or maybe a neutron.
That's a rather large number!)
Even with AC one can only stipulate that there exists a 1-1
onto mapping n : S(S(R)) -> a subset of S(R). But what
does S(S(R)) really mean? If one simplifies the problem
somewhat and stipulates
n : S(S(I)) -> a subset of S(I)
where I've written I = [0,1) for simplicity, then S(S(I))
becomes some sort of weird 2-dimensional surface.
The mapping n then becomes a curve on that surface, as far
as I can tell.
I'd have to study ZFC/AC in more detail to coherently proceed
out of this minefield.
--
#191, ewill3@xxxxxxxxxxxxx
It's still legal to go .sigless.
.
- References:
- Cantor's Diagonal Argument
- From: William of Ockham
- Re: Cantor's Diagonal Argument
- From: The Ghost In The Machine
- Re: Cantor's Diagonal Argument
- From: Peter Webb
- Cantor's Diagonal Argument
- Prev by Date: Re: Proof of p ^ !q |- !(p v q)
- Next by Date: Re: Non-standard models of PA
- Previous by thread: Re: Cantor's Diagonal Argument
- Next by thread: Re: Cantor's Diagonal Argument
- Index(es):
Relevant Pages
|
