Diagonal wanderings (incongruent by construction)
LudovicoVan
Cantor claims: "whichever list of infinite (binary) strings you can
come up with, I will (anti-)diagonalise it."
It is (AFAIK) easy enough to come up with a production of _all_ the
infinite binary strings. The problem remains how to make the list
bullet-proof to diagonalisation. All we can do is falsify the
diagonalisation procedure itself, by following the claim to the
letter:
We start by producing our list, entry by entry; in parallel, our
opponent starts building the anti-diagonal (I will abstract from the
technical details, unnecessary here):
List Diagonal Anti-diagonal
.(0) 0 1
.(0)1 0 1
... ... ...
At this point, one migth wander: is there? is not there?
=== Cantor's diagonal is a non-halting machine. ===
Under this perspective, accepting the diagonal argument "simply"
implies a specific choice about infinity (and infinities; and what can
or cannot be proved; and a fundamental paradox: incongruent by
construction).
Now, what about Turing?
-LV
MoeBlee
> We start by producing our list, entry by entry; in parallel, our
> opponent starts building the anti-diagonal (I will abstract from the
> technical details, unnecessary here):
>
> List Diagonal Anti-diagonal
> .(0) 0 1
> .(0)1 0 1
> ... ... ...
>
> At this point, one migth wander: is there? is not there?
>
> === Cantor's diagonal is a non-halting machine. ===
>
> Under this perspective,
And that is not the perspective in which the proof is given.
The diagonal is not a machine, nor Turning machine, nor abstract
machine of any kind, halting or non-halting.
Rather, the diagonal is a sequence. And it is not defined "entry by
entry" as some list is given "entry by entry".
A denumerable list of denumerable binary strings is a sequence, so a
FUNCTION.
And a each denumerable binary string is a sequence, so a FUNCTION.
And the digaonal is a sequence, so a FUNCTION.
GIVEN ANY denumerable list of denumerable binary strings, which is a
FUNCTION whose values are FUNCTIONS, there exists the diagonal of that
list, and that diagonal is a FUNCTION and it is not one of the values
of the function that is the said list of denumerable binary strings.
That's IT. There are no machines, or "entry by entry" processes, or
other junk involved.
If you change the whole matter to something about "entry by entry"
process or machines or whatever then that is a DIFFERENT matter from
the diagonal proof that there is no list of the entire set of
denumerable binary strings.
MoeBlee
William Elliot
>> We start by producing our list, entry by entry; in parallel, our
>> opponent starts building the anti-diagonal (I will abstract from the
>> technical details, unnecessary here):
>>
>> At this point, one migth wander: is there? is not there?
>>
>> === Cantor's diagonal is a non-halting machine. ===
>>
>> Under this perspective,
>
> And that is not the perspective in which the proof is given.
>
> The diagonal is not a machine, nor Turning machine, nor abstract
> machine of any kind, halting or non-halting.
>
Clearly OP is has been duped into joining the currently popular religous
clut of computerism. The first tenante of computerism is that computers
know it all. Not only has no computer ever successfully passed a SAT
exam, Godel showed that there's somethings that computer will never know.
Anyway those computerism nuts are a NP hard case to get them to even admit
that there's not enough time for computers to know anything but the
simplest.
Indeed, is any computer capable of earning a master or even a graduate,
degree in computer science?
Barb Knox
William Elliot <ma...@rdrop.remove.com> wrote:
> On Wed, 6 May 2009, MoeBlee wrote:
>
> >> We start by producing our list, entry by entry; in parallel, our
> >> opponent starts building the anti-diagonal (I will abstract from the
> >> technical details, unnecessary here):
> >>
> >> At this point, one migth wander: is there? is not there?
> >>
> >> === Cantor's diagonal is a non-halting machine. ===
> >>
> >> Under this perspective,
> >
> > And that is not the perspective in which the proof is given.
> >
> > The diagonal is not a machine, nor Turning machine, nor abstract
> > machine of any kind, halting or non-halting.
> >
> Clearly OP is has been duped into joining the currently popular
> religous [cult] of computerism.
It's actually even worse than that. By framing the Cantor diagonal
construction in a computer-friendly way (e.g. for every i and j, the
"enumeration oracle" produces the j'th digit of the i'th list-entry in
finite time), one can readily construct a *computable* diagonal which
provably differs from every entry in the enumeration.
So it's less a case of computer-worship than self-worship (i.e.
believing that one's naive intuitions MUST be right, even when proven
wrong).
[snip]
> > Rather, the diagonal is a sequence. And it is not defined "entry by
> > entry" as some list is given "entry by entry".
> >
> > A denumerable list of denumerable binary strings is a sequence, so a
> > FUNCTION.
> >
> > And a each denumerable binary string is a sequence, so a FUNCTION.
> >
> > And the digaonal is a sequence, so a FUNCTION.
> >
> > GIVEN ANY denumerable list of denumerable binary strings, which is a
> > FUNCTION whose values are FUNCTIONS, there exists the diagonal of that
> > list, and that diagonal is a FUNCTION and it is not one of the values
> > of the function that is the said list of denumerable binary strings.
> >
> > That's IT. There are no machines, or "entry by entry" processes, or
> > other junk involved.
> >
> > If you change the whole matter to something about "entry by entry"
> > process or machines or whatever then that is a DIFFERENT matter from
> > the diagonal proof that there is no list of the entire set of
> > denumerable binary strings.
> >
> > MoeBlee
> >
--
---------------------------
| BBB b \ Barbara at LivingHistory stop co stop uk
| B B aa rrr b |
| BBB a a r bbb | Quidquid latine dictum sit,
| B B a a r b b | altum viditur.
| BBB aa a r bbb |
-----------------------------
jesko
The infinite union of infinite numerable sets is numarable?
Clearly no!
So Reals are not walkable!
Barb Knox
<c61e543e-18cd-40bf...@o27g2000vbd.googlegroups.com>,
jesko <fran...@gmail.com> wrote:
Yes: the infinite union of a denumerably infinite set of denumerably
infinite sets is denumerable. Let i:j indicate the j'th element of the
i'th set. One way to enumerate the infinite union is:
{1:1, 1:2, 2:1, 1:3, 2:2, 3:1, 1:4, 2:3, 3:2, 4:1, ...}
Clearly, this covers all i:j.
> Clearly no!
Clearly wrong!
> So Reals are not walkable!
A correct conclusion from an incorrect premise. (By "walkable" I assume
you mean denumerable.)
jesko
> In article
> <c61e543e-18cd-40bf-8c28-b4b7e31a9...@o27g2000vbd.googlegroups.com>,
>
> - Mostra testo citato -
Well, you're rigtht!
A correct conclusion from an incorrect premise
I say A wrong conclusion from a correct premise.
jesko
> In article
> <c61e543e-18cd-40bf-8c28-b4b7e31a9...@o27g2000vbd.googlegroups.com>,
>
>
>
>
>
>
> - Mostra testo citato -
If you map any real to N (Naturals) then you may conceive Reals as
the infinite uinion of denumerable
sets since N is always denumarable. But this is union must be not
walkable or not denumarable.
So a contradiction!
Thanks a lot!
jesko
Yes , I agree with your argument.
But consider this function.
F is defined so:
R is a real number. Every decimal digits of R can be mapped to a
subset of N
es.
5,892479847892798278974894279874289
0 246810..................................................
Since any properties over N is suitable for this mapping, the set of
Reals can be mapped to the set of all properties over Naturals.
Clearly since every property is denumerable , their union must be
denumerable or Naturals will be not walkable.
So ...........
Barb Knox
<c7ccbbf2-af51-448e...@r36g2000vbr.googlegroups.com>,
jesko <fran...@gmail.com> wrote:
It is indeed the case that each real in [0,1) can be mapped to a unique
(possibly infinite) set of naturals, e.g. by representing the fraction
in binary (not ending in 111...) and having your set of naturals be the
place positions which have a 1.
> since N is always denumarable.
A true statement, but how is it relevant here?
> But this is union must be not walkable or not denumarable.
You still haven't defined what you mean by "walkable". Tsk tsk.
As for denumerable, OF COURSE a union (even a non-denumerable union) of
subsets of N will be a subset of N. And so what?
> So a contradiction!
Nope.
> Thanks a lot!
(It doesn't seem to be helping much, n'est-ce pas?)
Face facts: Cantor's diagonal proof that |R| > |N| is SIMPLE. It has
even been CHECKED BY COMPUTERS. Therefore the only way that |R| = |N|
is if the various formulations of axiomatic set theory are internally
INCONSISTENT (which is emphatically NOT the same as being inconsistent
with someone's naive intuitions). Proving (say) ZFC to be inconsistent
would be worth at least a Fields Medal and a centrefold picture in the
Journal of the AMS. If it were easy (or even less than extremely
difficult) to do then it would already have been done. The chance of
you doing it is vanishingly small.
Plus, there are good reasons for believing that ZFC etc. ARE internally
consistent. For example, there is an intuitively not-unreasonable model
for ZFC etc. (Goedel's "constructible universe").
WM
> In article <20090506222934.N59...@agora.rdrop.com>,
> William Elliot <ma...@rdrop.remove.com> wrote:
>
>
>
>
>
> > On Wed, 6 May 2009, MoeBlee wrote:
>
> > >> We start by producing our list, entry by entry; in parallel, our
> > >> opponent starts building the anti-diagonal (I will abstract from the
> > >> technical details, unnecessary here):
>
> > >> At this point, one migth wander: is there? is not there?
>
> > >> === Cantor's diagonal is a non-halting machine. ===
>
> > >> Under this perspective,
>
> > > And that is not the perspective in which the proof is given.
>
> > > The diagonal is not a machine, nor Turning machine, nor abstract
> > > machine of any kind, halting or non-halting.
>
> > Clearly OP is has been duped into joining the currently popular
> > religous [cult] of computerism.
>
> It's actually even worse than that. By framing the Cantor diagonal
> construction in a computer-friendly way (e.g. for every i and j, the
> "enumeration oracle" produces the j'th digit of the i'th list-entry in
> finite time), one can readily construct a *computable* diagonal which
> provably differs from every entry in the enumeration.
The computed number differs from every entry checked up to the n-th
line.
It does not differ from all lines, given that there are more than n +
1 for every n.
It does not differ from all lines unless the list can be checked
completely.
It does not differ from all the paths of the infinite binary tree.
Regards, WM
WM
> Face facts: Cantor's diagonal proof that |R| > |N| is SIMPLE.
It presupposes actual infinity, i.e. a list that can be checked
completely.
If it is possible to go through a countable set (checking it) then it
is possible to construct every element. Then it is possible to
constrct the complete binarey tree (all its nodes) by means of a
contable number of steps using a countable number of paths.
< It has
> even been CHECKED BY COMPUTERS.
which do what their programmers want.
> Therefore the only way that |R| = |N|
> is if the various formulations of axiomatic set theory are internally
> INCONSISTENT
or that the assumption of actual infinity leads to a contradiction.
> (which is emphatically NOT the same as being inconsistent
> with someone's naive intuitions).
That means, all counter aruments will be qualifed as naive intuition?
Here is an agument that counts and counters:
In a (not necessarily finite) sequence of finite linear sets A c B c
C ... we
have never two elements a and b of the sets such that
(a e A & b !e A) & (b e B & a !e B).
This proves that there is a largest natural number if there are all
natural numbers.
Regards, WM
jesko
> In article
If Reals are defined as the set of all properties over N, then Reals
are numerable
since if not numearble then N would be so , that it is absurd.
>
> > So a contradiction!
>
> Nope.
>
> > Thanks a lot!
>
> (It doesn't seem to be helping much, n'est-ce pas?)
>
> Face facts: Cantor's diagonal proof that |R| > |N| is SIMPLE. It has
> even been CHECKED BY COMPUTERS. Therefore the only way that |R| = |N|
> is if the various formulations of axiomatic set theory are internally
> INCONSISTENT (which is emphatically NOT the same as being inconsistent
> with someone's naive intuitions). Proving (say) ZFC to be inconsistent
> would be worth at least a Fields Medal and a centrefold picture in the
> Journal of the AMS. If it were easy (or even less than extremely
> difficult) to do then it would already have been done. The chance of
> you doing it is vanishingly small.
>
> Plus, there are good reasons for believing that ZFC etc. ARE internally
> consistent. For example, there is an intuitively not-unreasonable model
> for ZFC etc. (Goedel's "constructible universe").
>
> --
> ---------------------------
> | BBB b \ Barbara at LivingHistory stop co stop uk
> | B B aa rrr b |
> | BBB a a r bbb | Quidquid latine dictum sit,
> | B B a a r b b | altum viditur.
> | BBB aa a r bbb |
jesko
> In article
The main paradox is:
" Counting infinite object is not coutable but I'm still counting "
This paradox arises when you want to count objects that are infinite
objects as reals.
Properties over N are infinite object as "To be a powers" , but no
one can admit that they don't constitute
an enumerable set. But clearly one can always construct a new property
from the preceding counted properties.
But for the same infinity notion one can always add a new natural to
Naturals.
Tha's all
Thanks.
jesko
Further one can easily prove that countability is never a property of
infinity.
So no classification of infinity can be based upon countability.
Thanks in advance
Thanks
Simply thanks.
David C. Ullrich
<ju...@diegidio.name> wrote:
>Mostly, a thought experiment:
>
>Cantor claims: "whichever list of infinite (binary) strings you can
>come up with, I will (anti-)diagonalise it."
>
>It is (AFAIK) easy enough to come up with a production of _all_ the
>infinite binary strings.
Exactly what does "come up with a production of" mean here?
>The problem remains how to make the list
>bullet-proof to diagonalisation. All we can do is falsify the
>diagonalisation procedure itself, by following the claim to the
>letter:
>
>We start by producing our list, entry by entry; in parallel, our
>opponent starts building the anti-diagonal (I will abstract from the
>technical details, unnecessary here):
>
> List Diagonal Anti-diagonal
> .(0) 0 1
> .(0)1 0 1
> ... ... ...
>
>At this point, one migth wander: is there? is not there?
Is there _what_?
> === Cantor's diagonal is a non-halting machine. ===
It's not a machine at all.
You're talking about infinite strings of digits. Can you
give an example of a _halting_ machine that produces
such a thing? No. This has nothing to do with the
diagonal argument - the question of halting machines
is simply irrelevant.
>Under this perspective, accepting the diagonal argument "simply"
>implies a specific choice about infinity (and infinities; and what can
>or cannot be proved; and a fundamental paradox: incongruent by
>construction).
You're aware that this entire post is incoherent, right?
>Now, what about Turing?
What about Turing?
>-LV
David C. Ullrich
"Understanding Godel isn't about following his formal proof.
That would make a mockery of everything Godel was up to."
(John Jones, "My talk about Godel to the post-grads."
in sci.logic.)
jesko
Authority wrote:
"We may begin with a dialectical argument and show as follows that
there is no such thing. If ‘bounded by a surface’ is the definition of
body there cannot be an infinite body either intelligible or sensible.
Nor can number taken in abstraction be infinite, for number or that
which has number is numerable. If then the numerable can be numbered,
it would also be possible to go through the infinite."
Aristotle : Physics III,5
From this it doesn't follow that Naturals are numbered while Reals
not!
Marshall
>
> Face facts: Cantor's diagonal proof that |R| > |N| is SIMPLE. It has
> even been CHECKED BY COMPUTERS. Therefore the only way that |R| = |N|
> is if the various formulations of axiomatic set theory are internally
> INCONSISTENT (which is emphatically NOT the same as being inconsistent
> with someone's naive intuitions).
Pardon me, but wouldn't it be more accurate to say: the only
way that |R| = |N| would be provable in [some] axiomatic
set theory would be if that theory was inconsistent? And even if
that were so, it would still be the case that |R| > |N| in a
consistent theory. Yes?
Marshall
James Burns
> The computed number differs from every entry
> checked up to the n-th line.
> It does not differ from all lines, given that
> there are more than n + 1 for every n.
> It does not differ from all lines unless the
> list can be checked completely.
Another consequence of your rule is
One (1) does not differ from all even integers unless the
list (of even integers) can be checked completely.
Since there are an infinite number of even integers, it
must follow, as night does the day, that one (1) is
an even integer.
Jim Burns
DavidA
I think what is going on is that you and several of the other
respondents are (perhaps without knowing it) mathematical
constructivists.
Classical mathematics rests on ZFC set theory. In that theory,
Cantor's argument is valid.
However, you and the other respondents have an intuition that there is
something wrong with the argument. This suggests to me that you would
prefer intuitionist mathematics (as developed by Brouwer and others),
or some other constructivist variant.
Intuitionistic mathematics is perfectly respectable, studied by
logicians, etc. Many of the results of classical mathematics can also
be proved in intuitionistic mathematics - but not all.
So I suppose the next question is, does Cantor's argument work in
intuitionist mathematics? I'm afraid I don't know the answer to that
one.
DavidA
http://en.wikipedia.org/wiki/Constructivism_(mathematics)
- does discuss Cantor's argument
Alan Smaill
> On May 7, 1:04ï¿œam, LudovicoVan <ju...@diegidio.name> wrote:
> > Mostly, a thought experiment:
> >
> > Cantor claims: "whichever list of infinite (binary) strings you can
> > come up with, I will (anti-)diagonalise it."
> >
> > It is (AFAIK) easy enough to come up with a production of _all_ the
> > infinite binary strings. The problem remains how to make the list
> > bullet-proof to diagonalisation. All we can do is falsify the
> > diagonalisation procedure itself, by following the claim to the
> > letter:
> >
> > We start by producing our list, entry by entry; in parallel, our
> > opponent starts building the anti-diagonal (I will abstract from the
> > technical details, unnecessary here):
> >
> > ￜ ￜ List ￜ Diagonal Anti-diagonal
> > ￜ ￜ .(0) ￜ ￜ ￜ ￜ 0 ￜ ￜ ￜ ￜ ￜ ￜ 1
> > ￜ ￜ .(0)1 ￜ ￜ ￜ ￜ0 ￜ ￜ ￜ ￜ ￜ ￜ 1
> > ￜ ￜ ￜ... ￜ ￜ ￜ ￜ ... ￜ ￜ ￜ ￜ ￜ ...
> >
> > At this point, one migth wander: is there? is not there?
> >
> > ￜ ￜ ￜ ￜ === Cantor's diagonal is a non-halting machine. ===
> >
> > Under this perspective, accepting the diagonal argument "simply"
> > implies a specific choice about infinity (and infinities; and what can
> > or cannot be proved; and a fundamental paradox: incongruent by
> > construction).
> >
> > Now, what about Turing?
> >
> > -LV
>
> I think what is going on is that you and several of the other
> respondents are (perhaps without knowing it) mathematical
> constructivists.
>
> Classical mathematics rests on ZFC set theory. In that theory,
> Cantor's argument is valid.
>
> However, you and the other respondents have an intuition that there is
> something wrong with the argument. This suggests to me that you would
> prefer intuitionist mathematics (as developed by Brouwer and others),
> or some other constructivist variant.
>
> Intuitionistic mathematics is perfectly respectable, studied by
> logicians, etc. Many of the results of classical mathematics can also
> be proved in intuitionistic mathematics - but not all.
>
> So I suppose the next question is, does Cantor's argument work in
> intuitionist mathematics? I'm afraid I don't know the answer to that
> one.
As others have noted, if you are serious about constructivism, so that
not only the decimal expansions of the reals is taken to be
constructive, but also an enumeration of such reals is itself given
constructively, then lo and behold it is possible to construct effectively
a real not in the given list.
This argument is given eg by Bishop in his book "Constructive Analysis".
It might help such as LV to note that Bishop does not state the claim in
the form that one set is larger than another, but in the form that says
that for any effectively given enumeration, a missing real can be constructed.
--
Alan Smaill
LudovicoVan
> On Wed, 6 May 2009 17:04:15 -0700 (PDT), LudovicoVan
> <ju...@diegidio.name> wrote:
> >Mostly, a thought experiment:
>
> >Cantor claims: "whichever list of infinite (binary) strings you can
> >come up with, I will (anti-)diagonalise it."
>
> >It is (AFAIK) easy enough to come up with a production of _all_ the
> >infinite binary strings.
>
> Exactly what does "come up with a production of" mean here?
I mean "production" in the constructive sense: at least predicative.
Though I'm not putting this burden on Cantor's diagonal argument
itself, it's just the reference point for my counter-argument. For
instance, one could give an inductive definition, then implement and
run it in, say, Prolog. The program is not more "non-halting" than a
program to output the naturals.
> >The problem remains how to make the list
> >bullet-proof to diagonalisation. All we can do is falsify the
> >diagonalisation procedure itself, by following the claim to the
> >letter:
>
> >We start by producing our list, entry by entry; in parallel, our
> >opponent starts building the anti-diagonal (I will abstract from the
> >technical details, unnecessary here):
>
> > List Diagonal Anti-diagonal
> > .(0) 0 1
> > .(0)1 0 1
> > ... ... ...
>
> >At this point, one migth wander: is there? is not there?
>
> Is there _what_?
The anti-diagonal: is it in the list? Is it not? The proper question
is: will the program ever output it's anti-diagonal?
> > === Cantor's diagonal is a non-halting machine. ===
>
> It's not a machine at all.
Turing machines can be an interpretation tool here. Anti-
diagonalisation is a process, not yet a total function, because
decisions about infinities are a consequence in our case, not a
premise (they are yet to be taken).
> You're talking about infinite strings of digits. Can you
> give an example of a _halting_ machine that produces
> such a thing? No.
As said, asking for a machine that produces all infinite binary
strings and halts is just as sensible as asking for a machine that
produces all naturals and halts.
> This has nothing to do with the
> diagonal argument - the question of halting machines
> is simply irrelevant.
> >Under this perspective, accepting the diagonal argument "simply"
> >implies a specific choice about infinity (and infinities; and what can
> >or cannot be proved; and a fundamental paradox: incongruent by
> >construction).
>
> You're aware that this entire post is incoherent, right?
It's all but incoherent. Maybe it's unclear, maybe it's incorrect in
many ways, maybe there is something you are still missing, maybe a bit
of all of them.
In synthesis, the incongruency I am talking about could be seen in
this fact: we are denied the existence of a complete list, in terms of
a construct that is claimed to be complete.
> >Now, what about Turing?
>
> What about Turing?
Turing leverages the diagonal argument to show the insolubility of the
halting problem (consequently failing Hilbert's program, by the way).
In any case, I find Turing and his machines interesting here because,
as far as I can see, Turing reasons at the same "primitive" (in the
theoretical sense) level as Cantor.
-LV
LudovicoVan
> I suppose the next question is, does Cantor's argument work in
> intuitionist mathematics? I'm afraid I don't know the answer to that
> one.
The diagonal argument, as well as all arguments about the
uncountability of the reals, are not predicative.
-LV
LudovicoVan
> Clearly OP is has been duped into joining the currently popular religous
> clut of computerism.
You are a simple man.
-LV
LudovicoVan
> In article <20090506222934.N59...@agora.rdrop.com>,
> William Elliot <ma...@rdrop.remove.com> wrote:
> > On Wed, 6 May 2009, MoeBlee wrote:
>
> > >> We start by producing our list, entry by entry; in parallel, our
> > >> opponent starts building the anti-diagonal (I will abstract from the
> > >> technical details, unnecessary here):
>
> > >> At this point, one migth wander: is there? is not there?
>
> > >> === Cantor's diagonal is a non-halting machine. ===
>
> > >> Under this perspective,
>
> > > And that is not the perspective in which the proof is given.
>
> > > The diagonal is not a machine, nor Turning machine, nor abstract
> > > machine of any kind, halting or non-halting.
>
> > Clearly OP is has been duped into joining the currently popular
> > religous [cult] of computerism.
>
> It's actually even worse than that. By framing the Cantor diagonal
> construction in a computer-friendly way (e.g. for every i and j, the
> "enumeration oracle" produces the j'th digit of the i'th list-entry in
> finite time), one can readily construct a *computable* diagonal which
> provably differs from every entry in the enumeration.
Provably how?
> So it's less a case of computer-worship than self-worship (i.e.
> believing that one's naive intuitions MUST be right, even when proven
> wrong).
Simple lady.
-LV
LudovicoVan
> Face facts: Cantor's diagonal proof that |R| > |N| is SIMPLE. It has
> even been CHECKED BY COMPUTERS.
Formal proofs are irrelevant to the diagonal argument: they have it
embedded, as an informing principle, into their axioms and
definitions.
> Therefore the only way that |R| = |N|
> is if the various formulations of axiomatic set theory are internally
> INCONSISTENT
Incorrect (and a myopic). They can be formally consistent with unsound
or otherwise invalid premises. Indeed, the diagonal argument here
under investigation, is an informing principle to standard axiomatic
set theories.
> Proving (say) ZFC to be inconsistent
> would be worth at least a Fields Medal and a centrefold picture in the
> Journal of the AMS.
That tells a lot about the current state of mathematics and not only.
-LV
LudovicoVan
> On May 7, 3:56 am, Barb Knox <s...@sig.below> wrote:
>
> > Face facts: Cantor's diagonal proof that |R| > |N| is SIMPLE. It has
> > even been CHECKED BY COMPUTERS. Therefore the only way that |R| = |N|
> > is if the various formulations of axiomatic set theory are internally
> > INCONSISTENT (which is emphatically NOT the same as being inconsistent
> > with someone's naive intuitions).
>
> Pardon me, but wouldn't it be more accurate to say: the only
> way that |R| = |N| would be provable in [some] axiomatic
> set theory would be if that theory was inconsistent?
It would be incorrect and, strictly speaking, false.
-LV
Alan Smaill
> On 7 May, 13:13, David C. Ullrich <dullr...@sprynet.com> wrote:
> > On Wed, 6 May 2009 17:04:15 -0700 (PDT), LudovicoVan
> > <ju...@diegidio.name> wrote:
> > >Mostly, a thought experiment:
> >
> > >Cantor claims: "whichever list of infinite (binary) strings you can
> > >come up with, I will (anti-)diagonalise it."
> >
> > >It is (AFAIK) easy enough to come up with a production of _all_ the
> > >infinite binary strings.
> >
> > Exactly what does "come up with a production of" mean here?
>
> I mean "production" in the constructive sense: at least predicative.
> Though I'm not putting this burden on Cantor's diagonal argument
> itself, it's just the reference point for my counter-argument. For
> instance, one could give an inductive definition, then implement and
> run it in, say, Prolog. The program is not more "non-halting" than a
> program to output the naturals.
>
> > >The problem remains how to make the list
> > >bullet-proof to diagonalisation. All we can do is falsify the
> > >diagonalisation procedure itself, by following the claim to the
> > >letter:
> >
> > >We start by producing our list, entry by entry; in parallel, our
> > >opponent starts building the anti-diagonal (I will abstract from the
> > >technical details, unnecessary here):
> >
> > > ￜ ￜList ￜ Diagonal Anti-diagonal
> > > ￜ ￜ.(0) ￜ ￜ ￜ ￜ 0 ￜ ￜ ￜ ￜ ￜ ￜ 1
> > > ￜ ￜ.(0)1 ￜ ￜ ￜ ￜ0 ￜ ￜ ￜ ￜ ￜ ￜ 1
> > > ￜ ￜ ... ￜ ￜ ￜ ￜ ... ￜ ￜ ￜ ￜ ￜ ...
> >
> > >At this point, one migth wander: is there? is not there?
> >
> > Is there _what_?
>
> The anti-diagonal: is it in the list? Is it not? The proper question
> is: will the program ever output it's anti-diagonal?
As you well know, a program will never produce infinite output.
So your choice of question is seriously loaded -- your program will
never output a binary expansion of even one real number.
Now, maybe this is a good way to think of the potential infinite
and constructivism -- but as you expressed it here, you need to
be more even-handed about what it means to construct a number (and a list
of numbers).
> > > ￜ ￜ ￜ ￜ=== Cantor's diagonal is a non-halting machine. ===
> >
> > It's not a machine at all.
>
> Turing machines can be an interpretation tool here. Anti-
> diagonalisation is a process, not yet a total function, because
> decisions about infinities are a consequence in our case, not a
> premise (they are yet to be taken).
That's fine, it is as good a tool as it needs to be.
> > You're talking about infinite strings of digits. Can you
> > give an example of a _halting_ machine that produces
> > such a thing? No.
>
> As said, asking for a machine that produces all infinite binary
> strings and halts is just as sensible as asking for a machine that
> produces all naturals and halts.
So what are *you* asking for when you ask whether the program can *output*
its anti-diagonal?
> > This has nothing to do with the
> > diagonal argument - the question of halting machines
> > is simply irrelevant.
>
> > >Under this perspective, accepting the diagonal argument "simply"
> > >implies a specific choice about infinity (and infinities; and what can
> > >or cannot be proved; and a fundamental paradox: incongruent by
> > >construction).
> >
> > You're aware that this entire post is incoherent, right?
>
> It's all but incoherent. Maybe it's unclear, maybe it's incorrect in
> many ways, maybe there is something you are still missing, maybe a bit
> of all of them.
>
> In synthesis, the incongruency I am talking about could be seen in
> this fact: we are denied the existence of a complete list, in terms of
> a construct that is claimed to be complete.
Complete in what sense?
-- that there is a completed infinite totality
-- that every real appears somewhere in the list
-- that every constructive real appears somewhere in the list
-- that the nth digit of the mth real can be computed on demand
-- something else??
>
> -LV
--
Alan Smaill
Alan Smaill
> On 7 May, 11:56, Barb Knox <s...@sig.below> wrote:
>
> > Face facts: Cantor's diagonal proof that |R| > |N| is SIMPLE. ï¿œIt has
> > even been CHECKED BY COMPUTERS.
>
> Formal proofs are irrelevant to the diagonal argument: they have it
> embedded, as an informing principle, into their axioms and
> definitions.
Why should we believe this assertion of yours?
You have made it several times, and not yet given the slightest
reason for anyone to believe it.
>
> -LV
--
Alan Smaill
LudovicoVan
> As others have noted, if you are serious about constructivism, so that
> not only the decimal expansions of the reals is taken to be
> constructive, but also an enumeration of such reals is itself given
> constructively, then lo and behold it is possible to construct effectively
> a real not in the given list.
> This argument is given eg by Bishop in his book "Constructive Analysis".
Interesting: could you maybe give an idea how this argument goes? How
to "construct effectively a real not in the given list"?
> It might help such as LV to note that Bishop does not state the claim in
> the form that one set is larger than another
Usually I don't either, so no help.
-LV
MoeBlee
> On 7 Mai, 12:56, Barb Knox <s...@sig.below> wrote:
>
> > Face facts: Cantor's diagonal proof that |R| > |N| is SIMPLE.
>
> It presupposes actual infinity,
If there is no set whose members are all and only the natural numbers,
then the very question of comparison between N and R reduces to what
'N' and 'R' would stand for; and this is not a very interesting
question. But we may put the matter in the hypothetical: IF there is a
set whose members are all and only the natural numbers (and building
from that set we get a set whose members are all and only the real
numbers) then the set of natural numbers is strictly dominated by the
set of real numbers.
In other words, yes, if there are no set of natural numbers, then we
hardly care about relative cardinality. But if there is a set of
natural numbers, then it is strictly dominated by the set of real
numbers.
You're not saying anything that is not completely understood already
by mathematicians. It is already well understood that we need to adopt
some axiom (such as the axiom of infinity) to prove that there exists
a set of all natural numbers.
> > Therefore the only way that |R| = |N|
> > is if the various formulations of axiomatic set theory are internally
> > INCONSISTENT
>
> or that the assumption of actual infinity leads to a contradiction.
That is silly. Your 'or' is not practically an alternative since the
alternative that set theoy is inconsistent was ALREADY MENTIONED.
MoeBlee
MoeBlee
> If Reals are defined as the set of all properties over N
Well, they're not defined that way.
MoeBlee
Alan Smaill
Let's look at total functions taking two natural numbers and returning
either 0 or 1, eg f(n,m). If we leave out the question of
multiple representations, let's suppose you have implemented
such a total function.
We can ask successive questions about the digits f(0,0), f(0,1), f(0,2), ...
for example, and take these as the digits of a constructive real.
Same story for f(1,0), f(1,1), f(1,2), ...
But the diagonal number f(0,0), f(1,1), f(2,2), ... is just as
computable as any of the individual reals. Likewise then the anti-diagonal,
which differs from every real in the given enumeration at at least
one position.
So, the anti-diagonal is itself something given algorithmically,
and you can easily write the procedure to return its nth digit,
provided that the given listing of reals itself is a total
function -- this does not mean that all the digits involved must
be computed, of course!
> Usually I don't either, so no help.
To put it another way, he does not say that the reals are "uncountable".
> -LV
--
Alan Smaill
WM
> WM wrote:
> > The computed number differs from every entry
> > checked up to the n-th line.
> > It does not differ from all lines, given that
> > there are more than n + 1 for every n.
> > It does not differ from all lines unless the
> > list can be checked completely.
>
> Another consequence of your rule is
>
> One (1) does not differ from all even integers unless the
> list (of even integers) can be checked completely.
No. If you know that an element exists only once in the world, you
need not search the whole universe in order to find a second one if
you have got the first.
But, yes, in order to be sure that 1 (or any other number) does not
appear in a sequence you must know the whole sequence.
> Since there are an infinite number of even integers, it
> must follow, as night does the day, that one (1) is
> an even integer.
Since there are an infinite number of even integers you cannot exclude
that there is a term a_2n = 1 unless you have searched them all.
Regards, WM
WM
> Classical mathematics rests on ZFC set theory. In that theory,
> Cantor's argument is valid.
In that theory N is given without construction. In that theory the
complete binary tree is given without construction. And its paths can
be shown to belong to a countable set.
>
> However, you and the other respondents have an intuition that there is
> something wrong with the argument. This suggests to me that you would
> prefer intuitionist mathematics (as developed by Brouwer and others),
> or some other constructivist variant.
>
> Intuitionistic mathematics is perfectly respectable, studied by
> logicians, etc. Many of the results of classical mathematics can also
> be proved in intuitionistic mathematics - but not all.
Only those which are correct.
>
> So I suppose the next question is, does Cantor's argument work in
> intuitionist mathematics? I'm afraid I don't know the answer to that
> one
It is asserted, erroneously, that it does.
But it does not, because there is no diagonal of the list of all
finite words
0
1
00
01
10
11
...
obviously.
Regards, WM
WM
> DavidA <polyom...@f2s.com> writes:
> > On May 7, 1:04 am, LudovicoVan <ju...@diegidio.name> wrote:
> > > Mostly, a thought experiment:
>
> > > Cantor claims: "whichever list of infinite (binary) strings you can
> > > come up with, I will (anti-)diagonalise it."
>
> > > It is (AFAIK) easy enough to come up with a production of _all_ the
> > > infinite binary strings. The problem remains how to make the list
> > > bullet-proof to diagonalisation. All we can do is falsify the
> > > diagonalisation procedure itself, by following the claim to the
> > > letter:
>
> > > We start by producing our list, entry by entry; in parallel, our
> > > opponent starts building the anti-diagonal (I will abstract from the
> > > technical details, unnecessary here):
>
> > > .(0) 0 1
> > > .(0)1 0 1
>
> > > At this point, one migth wander: is there? is not there?
>
That is only true if the reals are given as infinite sequences of
digits (which is in principle impossible). If they are given in the
form of finite words, the argument fails because the lis of all finite
words does not allow a diagonal:
o
1
00
01
10
11
...
Regards, WM
Denis Feldmann
MoeBlee
> On 7 Mai, 16:57, DavidA <polyom...@f2s.com> wrote:
>
> > Classical mathematics rests on ZFC set theory. In that theory,
> > Cantor's argument is valid.
>
> In that theory N is given without construction. In that theory the
> complete binary tree is given without construction. And its paths can
> be shown to belong to a countable set.
Of course the set of paths belongs to a countable set. The set of
paths is a member of the singleton set whose only member is the set of
paths. I don't see why you bother to remark on that fact.
But perhaps what you actually mean is that the set of paths is
countable. You've never proven that in ZFC
> > So I suppose the next question is, does Cantor's argument work in
> > intuitionist mathematics? I'm afraid I don't know the answer to that
> > one
>
> It is asserted, erroneously, that it does.
> But it does not, because there is no diagonal of the list of all
> finite words
> 0
> 1
> 00
> 01
> 10
> 11
> ...
> obviously.
Such silliness you write.
Whether an intuitionist accepts the axioms used in the diagonal
argument is one matter. But ASIDE from the axioms, the LOGIC used in
the diagonal argument IS intuitionistic.
And you've not shown any relevance of your list with the diagonal
argument.
MoeBlee
MoeBlee
You're silly. Of course if you declare that reals are not represented
by denumerable sequences, then there is no diagonal argument to make.
But there is no basis at all to think that ALL the reals can be
represented by finite sequences only.
MoeBlee
Virgil
<c7ccbbf2-af51-448e...@r36g2000vbr.googlegroups.com>,
jesko <fran...@gmail.com> wrote:
> If you map any real to N (Naturals) then you may conceive Reals as
> the infinite uinion of denumerable
> sets since N is always denumarable. But this is union must be not
> walkable or not denumarable.
How do you propose to map |R to |N ?
Virgil
<fc0b0e9b-c3e2-4249...@g20g2000vba.googlegroups.com>,
jesko <fran...@gmail.com> wrote:
> On 7 Mag, 02:04, LudovicoVan <ju...@diegidio.name> wrote:
> > Mostly, a thought experiment:
> >
> > Cantor claims: "whichever list of infinite (binary) strings you can
> > come up with, I will (anti-)diagonalise it."
> >
> > It is (AFAIK) easy enough to come up with a production of _all_ the
> > infinite binary strings. The problem remains how to make the list
> > bullet-proof to diagonalisation. All we can do is falsify the
> > diagonalisation procedure itself, by following the claim to the
> > letter:
> >
> > We start by producing our list, entry by entry; in parallel, our
> > opponent starts building the anti-diagonal (I will abstract from the
> > technical details, unnecessary here):
> >
> > � � List � Diagonal Anti-diagonal
> > � � .(0) � � � � 0 � � � � � � 1
> > � � .(0)1 � � � �0 � � � � � � 1
> > � � �... � � � � ... � � � � � ...
> >
> > At this point, one migth wander: is there? is not there?
> >
> > � � � � === Cantor's diagonal is a non-halting machine. ===
> >
> > Under this perspective, accepting the diagonal argument "simply"
> > implies a specific choice about infinity (and infinities; and what can
> > or cannot be proved; and a fundamental paradox: incongruent by
> > construction).
> >
> > Now, what about Turing?
> >
> > -LV
>
> Yes , I agree with your argument.
> But consider this function.
>
> F is defined so:
>
> R is a real number. Every decimal digits of R can be mapped to a
> subset of N
>
> es.
>
>
> 5,892479847892798278974894279874289
> 0 246810..................................................
>
> Since any properties over N is suitable for this mapping, the set of
> Reals can be mapped to the set of all properties over Naturals.
> Clearly since every property is denumerable
I am not quite sure of what you mean by "properties", but the
denumerability of each property, whatever it is, in no way guarantees
the denumerability of the set of properties.
> , their union must be
> denumerable or Naturals will be not walkable.
> So ...........
Virgil
<bca5b803-b94d-41d5...@t11g2000vbc.googlegroups.com>,
WM <muec...@rz.fh-augsburg.de> wrote:
> The computed number differs from every entry checked up to the n-th
> line.
> It does not differ from all lines, given that there are more than n +
> 1 for every n.
Which line does it not differ from?
The nth line has an nth digit different from the nth digit of the
anti-diagonal. What more is needed?
> It does not differ from all lines unless the list can be checked
> completely.
The construction rule assures the diagonal is different from every line
in at least one digit position, What more is needed?
> It does not differ from all the paths of the infinite binary tree.
True, but that set of all paths is already uncountable.
Virgil
<aeec5544-6d64-408e...@j12g2000vbl.googlegroups.com>,
WM <muec...@rz.fh-augsburg.de> wrote:
> On 7 Mai, 12:56, Barb Knox <s...@sig.below> wrote:
>
> > Face facts: Cantor's diagonal proof that |R| > |N| is SIMPLE.
>
> It presupposes actual infinity, i.e. a list that can be checked
> completely.
And all of WM's charms are not enough to banish actual infinity from
mainstream mathematics.
>
> >�Therefore the only way that |R| = |N|
> > is if the various formulations of axiomatic set theory are internally
> > INCONSISTENT
>
> or that the assumption of actual infinity leads to a contradiction.
Which neither WM nor anyone else has demonstrated to the satisfaction of
anyone but themselves.
>
> > (which is emphatically NOT the same as being inconsistent
> > with someone's naive intuitions). �
>
> That means, all counter aruments will be qualifed as naive intuition?
> Here is an agument that counts and counters:
> In a (not necessarily finite) sequence of finite linear sets A c B c
> C ... we
> have never two elements a and b of the sets such that
> (a e A & b !e A) & (b e B & a !e B).
>
> This proves that there is a largest natural number if there are all
> natural numbers.
Not to anyone other than WM himself.
Wm has repeated this argument too many times now, but has still found no
one who accepts it as valid.
He should retire it.
>
> Regards, WM
Virgil
<ef9fad85-dbf0-4fdb...@e20g2000vbc.googlegroups.com>,
jesko <fran...@gmail.com> wrote:
> If Reals are defined as the set of all properties over N, then Reals
> are numerable
> since if not numearble then N would be so , that it is absurd.
There are quite a few definitions of the reals, none of which are
anything like that, so why suggest it?
And until you can develop the reals as a complete Archimedean ordered
field strictly from that definition alone, no one else will accept it.
Virgil
<4509f4d7-fa18-4e05...@t11g2000vbc.googlegroups.com>,
LudovicoVan <ju...@diegidio.name> wrote:
> On 7 May, 07:31, Barb Knox <s...@sig.below> wrote:
> > In article <20090506222934.N59...@agora.rdrop.com>,
> > �William Elliot <ma...@rdrop.remove.com> wrote:
> > > On Wed, 6 May 2009, MoeBlee wrote:
> >
> > > >> We start by producing our list, entry by entry; in parallel, our
> > > >> opponent starts building the anti-diagonal (I will abstract from the
> > > >> technical details, unnecessary here):
> >
> > > >> At this point, one migth wander: is there? is not there?
> >
> > > >> === Cantor's diagonal is a non-halting machine. ===
> >
> > > >> Under this perspective,
> >
> > > > And that is not the perspective in which the proof is given.
> >
> > > > The diagonal is not a machine, nor Turning machine, nor abstract
> > > > machine of any kind, halting or non-halting.
> >
> > > Clearly OP is has been duped into joining the currently popular
> > > religous [cult] of computerism.
> >
> > It's actually even worse than that. �By framing the Cantor diagonal
> > construction in a computer-friendly way (e.g. for every i and j, the
> > "enumeration oracle" produces the j'th digit of the i'th list-entry in
> > finite time), one can readily construct a *computable* diagonal which
> > provably differs from every entry in the enumeration.
>
> Provably how?
Look it up!
>
> > So it's less a case of computer-worship than self-worship (i.e.
> > believing that one's naive intuitions MUST be right, even when proven
> > wrong).
>
> Simple lady.
There are varieties of simplicity, some good, some not.
Hers is considerably better than yours.
>
> -LV
Virgil
<f4166d96-5f73-4a86...@t10g2000vbg.googlegroups.com>,
LudovicoVan <ju...@diegidio.name> wrote:
> On 7 May, 11:56, Barb Knox <s...@sig.below> wrote:
>
> > Face facts: Cantor's diagonal proof that |R| > |N| is SIMPLE. �It has
> > even been CHECKED BY COMPUTERS.
>
> Formal proofs are irrelevant to the diagonal argument: they have it
> embedded, as an informing principle, into their axioms and
> definitions.
>
> > Therefore the only way that |R| = |N|
> > is if the various formulations of axiomatic set theory are internally
> > INCONSISTENT
>
> Incorrect (and a myopic). They can be formally consistent with unsound
> or otherwise invalid premises.
How does one test individual premises or sets of premises for
unsoundness or invalidity? Unless one has some absolute standards and
can make everyone agree with them, one can never be absolutely sure.
> Indeed, the diagonal argument here
> under investigation, is an informing principle to standard axiomatic
> set theories.
But until YOUR standards of consistency and soundness are universally
accepted, such questions are moot.
Virgil
<881bf5de-5158-4381...@g20g2000vba.googlegroups.com>,
LudovicoVan <ju...@diegidio.name> wrote:
Can you justify that claim of falsehood?
Virgil
<3ab27d49-89cc-4aec...@21g2000vbk.googlegroups.com>,
WM <muec...@rz.fh-augsburg.de> wrote:
> On 7 Mai, 16:10, James Burns <burns...@osu.edu> wrote:
> > WM wrote:
> > > The computed number differs from every entry
> > > checked up to the n-th line.
> > > It does not differ from all lines, given that
> > > there are more than n + 1 for every n.
> > > It does not differ from all lines unless the
> > > list can be checked completely.
> >
> > Another consequence of your rule is
> >
> > One (1) does not differ from all even integers unless the
> > list (of even integers) can be checked completely.
>
> No. If you know that an element exists only once in the world, you
> need not search the whole universe in order to find a second one if
> you have got the first.
> But, yes, in order to be sure that 1 (or any other number) does not
> appear in a sequence you must know the whole sequence.
Then WM is incapable of proving that 1 is not an even number.
Others might note that there is a property which distinguishes members
of the set of all even naturals from nonmembers, and testing for that
property test for membership in that set.
>
> > Since there are an infinite number of even integers, it
> > must follow, as night does the day, that one (1) is
> > an even integer.
>
> Since there are an infinite number of even integers you cannot exclude
> that there is a term a_2n = 1 unless you have searched them all.
You can in ZFC, where its membership in a set can be determined by
whether the object has, or does not have, some property.
Perhaps WM needs to go back to his Gymnasium for a refresher.
WM
wrote:
> DavidA a écrit :
Anyhow, whatever Bishop may or may not have said:
It is impossible for him and for anybody else to construct a digit
sequence that identifies pi.
The only way to identify pi (or its multiples) is by saying "pi", or
ratio between circumference and diameter of a circle, or by stating
the series of Gregory-Leibniz, or by Euler's zeta functions, or by
Wallis' product, or by Vieta's infinite product or by many related
finite words.
All these words are finite and are written in the following list:
0
1
00
01
10
11
...
This list contains all finite words in all languages over all finite
alphabets. (It contains all dictionaries too.) This list, however,
does not facilitate diagonalization. Therefore in real constructivism
Cantor's proof fails. There are not more than countably many ideas
that can be expressed by words. The real (and other) numbers are a
subset of these ideas.
Regards, WM
Virgil
<aa2c587b-e259-438d...@v17g2000vbb.googlegroups.com>,
WM <muec...@rz.fh-augsburg.de> wrote:
> On 7 Mai, 16:57, DavidA <polyom...@f2s.com> wrote:
>
> > Classical mathematics rests on ZFC set theory. In that theory,
> > Cantor's argument is valid.
>
> In that theory N is given without construction. In that theory the
> complete binary tree is given without construction. And its paths can
> be shown to belong to a countable set.
>
>
> >
> > However, you and the other respondents have an intuition that there is
> > something wrong with the argument. This suggests to me that you would
> > prefer intuitionist mathematics (as developed by Brouwer and others),
> > or some other constructivist variant.
> >
> > Intuitionistic mathematics is perfectly respectable, studied by
> > logicians, etc. Many of the results of classical mathematics can also
> > be proved in intuitionistic mathematics - but not all.
>
> Only those which are correct.
In intuitionist mathematics, adepts do not say that that which has not
been proved by their methods is not correct, they merely say it is
unproven.
> >
> > So I suppose the next question is, does Cantor's argument work in
> > intuitionist mathematics? I'm afraid I don't know the answer to that
> > one
>
> It is asserted, erroneously, that it does.
Which is WM's own erroneous assertion.
There is a sense in which Cantor's argument does work, i.e., for any
constructible binary list, one can show by constructible methods that
there is a constructible non-member.
Virgil
<090e5499-f16b-4ff5...@m24g2000vbp.googlegroups.com>,
WM <muec...@rz.fh-augsburg.de> wrote:
If a real is defined well enough in words to be constructively
distinguished from any other equally well defined real, its decimal
expansion to any desired finite extent should be finitely constructible,
so that, however it is listed, a diagonal for that list can be
constructed which differs from it.
So that WM is wrong, again, as usual!
Marshall
> On 7 May, 13:13, David C. Ullrich <dullr...@sprynet.com> wrote:
> > On Wed, 6 May 2009 17:04:15 -0700 (PDT), LudovicoVan
> > <ju...@diegidio.name> wrote:
>
> > >infinite binary strings.
>
>
> I mean "production" in the constructive sense: at least predicative.
> Though I'm not putting this burden on Cantor's diagonal argument
> itself, it's just the reference point for my counter-argument. For
> instance, one could give an inductive definition, then implement and
> run it in, say, Prolog. The program is not more "non-halting" than a
> program to output the naturals.
You can write a program to output all of the naturals. This program
won't halt, as you say, and for any natural n, will eventually output
n. (We are glossing over some resource limits here, but that is
customary and reasonable.) It will never finish running, though;
there are always more naturals.
You can't do the same for the reals. That's because the reals
aren't countable and the naturals are.
The analogous situation with printing out all the naturals is printing
out a single real. For any digit position n, the program will
eventually
print out that digit, but it will never finish running; there are
always
more digits.
If you want to say, hey, I'll stop printing a particular number when
I get to some repeating pattern, then you're talking about a
program to print out all the rational numbers, not the reals.
If you want to print out real numbers, you can start, but you can't
finish even one. If you want to print out an uncomputable real,
you can't even start.
So no, it is not easy enough to print out all the infinite binary
strings; it's impossible actually to print out even one.
Marshall
lwa...@lausd.net
> On May 7, 3:56 am, Barb Knox <s...@sig.below> wrote:
> > Face facts: Cantor's diagonal proof that |R| > |N| is SIMPLE. It has
> > even been CHECKED BY COMPUTERS. Therefore the only way that |R| = |N|
> > is if the various formulations of axiomatic set theory are internally
> > INCONSISTENT (which is emphatically NOT the same as being inconsistent
> > with someone's naive intuitions).
> Pardon me, but wouldn't it be more accurate to say: the only
> way that |R| = |N| would be provable in [some] axiomatic
> that were so, it would still be the case that |R| > |N| in a
> consistent theory. Yes?
And so LV has started another thread about his opposition to
Cantor's theorem and the uncountability of the real numbers,
and of course, the responses to LV have been typical of the
standard set theorists' responses.
Marshall claims that "card(R)=card(N)" is impossible in a
consistent set theory. Of course, it's easy to come up with
a consistent set theory in which card(R)=card(N) -- just
define N to be {0} and R to be {1}. But of course, the
context is that N should be something resembling the set of
naturals and R something resembling the set of reals. In
particular, N and R should be infinite sets.
There have been other attempts, of course, to make N and R
have the same size. Some have considered the countable
model of ZFC whose existence is guaranteed by Lowenheim and
Skolem -- until it's mentioned that in that model, the
theorem of Cantor is still true. Some have tried to use the
set of computable reals in lieu of the classical reals --
until it's pointed out that the bijection between N and
that set is _not_ computable, and so the computable reals
are not _effectively_ enumerable. Others have tried to use
nonstandard naturals or hypernaturals, also without any
acceptance by the standard set theorists.
The problem is that many sci.math posters, including LV,
want to be able to work with something resembling natural
and real numbers, but just don't want those sets to have
different sizes. Call them Platonists, or some sort of
intuitionists, or whatever -- they simply don't accept
different sizes of infinity, and the fact that ZFC proves
the existence of more than one infinite cardinality is
sufficient for them to reject ZFC. Also, they don't care
whether they can come up with an explicit bijection
between N and R or not -- they want to have a theory in
which every infinite set has the same size.
And so what should one do, if one wants to work with
natural and real numbers, but is philosophically opposed
to the existence of more than one infinite set size? I
still refuse to believe that there can't be a rigorous
theory in which their claim is provable -- and which
isn't trivially inconsistent.
Of course, as I mentioned in another thread, there are
some things that standard set theorists will never accept
in a "reasonable" set theory. Such would be having N and R
have the same set sizes. Even though the theory NFU proves
the existence of non-Cantorian sets, no theory that proves
N to be a non-Cantorian set will be considered to be
"reasonable" by the standard set theorists.
WM is in this thread as well, but WM is an ultrafinitist,
so his dispute with standard theory is fundamentally
different from LV's.
MoeBlee
Marshall
>
> > On May 7, 3:56 am, Barb Knox <s...@sig.below> wrote:
> > > Face facts: Cantor's diagonal proof that |R| > |N| is SIMPLE. It has
> > > even been CHECKED BY COMPUTERS. Therefore the only way that |R| = |N|
> > > is if the various formulations of axiomatic set theory are internally
> > > INCONSISTENT (which is emphatically NOT the same as being inconsistent
> > > with someone's naive intuitions).
> > Pardon me, but wouldn't it be more accurate to say: the only
> > way that |R| = |N| would be provable in [some] axiomatic
> > set theory would be if that theory was inconsistent? And even if
> > that were so, it would still be the case that |R| > |N| in a
> > consistent theory. Yes?
>
> And so LV has started another thread about his opposition to
> Cantor's theorem and the uncountability of the real numbers,
> and of course, the responses to LV have been typical of the
> standard set theorists' responses.
>
> Marshall claims that "card(R)=card(N)" is impossible in a
> consistent set theory. Of course, it's easy to come up with
> a consistent set theory in which card(R)=card(N) -- just
> define N to be {0} and R to be {1}.
You make things so hard. If you want to go that way, just
define N := R. Then you get the benefit that |N| = |R|
no matter what the definition of |x| and no matter what
the definition of R.
> The problem is that many sci.math posters, including LV,
> want to be able to work with something resembling natural
> and real numbers, but just don't want those sets to have
> different sizes.
I totally know the feeling. I want to work with integers, but
I don't want 7 to be larger than 5.
> Call them Platonists, or some sort of
> intuitionists, or whatever -- they simply don't accept
> different sizes of infinity, and the fact that ZFC proves
> the existence of more than one infinite cardinality is
> sufficient for them to reject ZFC.
It's such a shame then that they are required by law
to use ZFC. They should work to get those laws changed!
"After all, this is a democracy!" [1]
> And so what should one do, if one wants to work with
> natural and real numbers, but is philosophically opposed
> to the existence of more than one infinite set size? I
> still refuse to believe that there can't be a rigorous
> theory in which their claim is provable -- and which
> isn't trivially inconsistent.
They could use a theory in which the "size" of a set
is defined to be zero. That way, size(N) = size(R).
Hey, maybe we could have a thread about that.
Something about having Axy.x+y=0 as an axiom.
> Of course, as I mentioned in another thread, there are
> some things that standard set theorists will never accept
> in a "reasonable" set theory.
We have to swear we'll never accept that as part of our
induction into the grand ZFC conspiracy, which I joined
for the medical and dental benefits. Our primary goal
is to hold back mathematics from the tremendous
but civilization-changing insights of certain individuals
on sci.math. Our primary weapons are fear and surprise.
Marshall
Marshall
Historically, a set is said to "cant over" (later
shortened to "canto'r" in the sixteenth century)
if it has enough of a slope or a tilt to it that
it can be considered to lie on the diagonal.
Such sets are immune to any kind of
diagonalization argument, which made them
popular with the mathematical cranks of the
late Victorian age. However, this immunity
was short-lived, as they were later shown
to be susceptible to finding an element that
was straight up and down.
Marshall
PS. Apologies to MoeBlee.
David R Tribble
>> The computed number differs from every entry
>> checked up to the n-th line.
>> It does not differ from all lines, given that
>> there are more than n + 1 for every n.
>> It does not differ from all lines unless the
>> list can be checked completely.
>
James Burns wrote:
>> Another consequence of your rule is
>> One (1) does not differ from all even integers unless the
>> list (of even integers) can be checked completely.
>
WM wrote:
> No. If you know that an element exists only once in the world, ...
And how do you know that?
> ... you need not search the whole universe in order to find a second one if
> you have got the first.
> But, yes, in order to be sure that 1 (or any other number) does not
> appear in a sequence you must know the whole sequence.
Or perhaps you need to only know a property shared by every
element in the sequence. For example, every element in the
sequence of even integers is even. This is true regardless
of how many elements have been "searched" or how many
remain to be "searched".
Jesse F. Hughes
> Marshall claims that "card(R)=card(N)" is impossible in a
> consistent set theory.
For what it's worth, I've no idea why he claims this.
I don't know of any interesting and consistent set theory in which R
is much like the reals, N is much like the naturals, card is much
like cardinality and card(R) = card(N) is a theorem, but I don't see
offhand why there can be no such theory.
--
Damn John Jay.
Damn everyone who won't damn John Jay.
Damn everyone who won't put lights in his windows and sit up all night
damning John Jay. -- Political graffiti from late 18th c. Boston
Marshall
> lwal...@lausd.net writes:
> > Marshall claims that "card(R)=card(N)" is impossible in a
> > consistent set theory.
>
> For what it's worth, I've no idea why he claims this.
Actually, I don't claim that. I did, however, ask if that
would be correct. (Please be careful of Mr. Walker's
restatement of people's positions.) Although it's fair
to say that I suspect it might be true.
> I don't know of any interesting and consistent set theory in which R
> is much like the reals, N is much like the naturals, card is much
> like cardinality and card(R) = card(N) is a theorem, but I don't see
> offhand why there can be no such theory.
Certainly I'm clear that if we are free to choose our definitions
of such symbols as "card", "N" and "R" we can make them
dance to whatever tune strikes our fancy. For example, I
proposed the definition N := R, and I *will* claim that with
that definition of N, card(N) = card(R). 'Cause I'
Brian Chandler
> On May 7, 4:08 pm, lwal...@lausd.net wrote:
> > On May 7, 6:22 am, Marshall <marshall.spi...@gmail.com> wrote:
> >
> > > On May 7, 3:56 am, Barb Knox <s...@sig.below> wrote:
> > > > Face facts: Cantor's diagonal proof that |R| > |N| is SIMPLE. It has
> We have to swear we'll never accept that as part of our
> induction into the grand ZFC conspiracy, which I joined
> for the medical and dental benefits.
And the chicks, surely?
Brian Chandler
Marshall
>
> For example, I
> proposed the definition N := R, and I *will* claim that with
> that definition of N, card(N) = card(R). 'Cause I'
Sorry about the interruption; I was going to type "'Cause I'm
the sort of person who has a bandage on his index finger
and is going to accidentally tab over the "SEND" key and
hit enter."
Okay, my actual point was that, first-order theories are
swell and all, but is that sort of machinery *necessary*
to notice that there is no bijection from the naturals
to the reals? Can't we just call the reals a model and
work from there? Any first-order theory we come up
with is going to be an abstraction of the thing we want
to talk about, and as such, is going to fail to capture
certain properties of that thing. (Seems I've heard
of some guy named "Godel" and some kind of
"theorem" about some sort of "incompleteness".)
(Although I suppose failing to capture certain properties
is irrelevant if we do capture the properties we care
about at that moment.)
I guess it feels like, if we're in a position to speak
of an "interesting and consistent set theory in which
R is much like the reals", why are we bothering?
We already have the reals themselves, and we
know there's uncountably many of them. Why
are we dicking around with theories that are
abstractions of a thing, as if that will settle anything
better than the actual thing would?
Of course it's entirely possible this thinking is just
the result of my ignorance; if someone would
care to hit me with the education stick, I'd be
most obliged. Although I've noticed that unless
one is making strong, ridiculous claims one does
not necessarily get much attention, so let me just
add as an aside that I have a proof that P != NP
here on my desk but I'm the only person alive
today smart enough to understand it.
Marshall
LudovicoVan
> Sorry about the interruption; I was going to type "'Cause I'm
> the sort of person who has a bandage on his index finger
Wow, I had not yet realised you could be such a consistent moron.
I also notice that this thread has already broken the barrier of
readability, with the journals, and 11 posts by Virgil only. Cool...
-LV
Marshall
> On 8 May, 05:08, Marshall <marshall.spi...@gmail.com> wrote:
>
> > Sorry about the interruption; I was going to type "'Cause I'm
> > the sort of person who has a bandage on his index finger
>
> Wow, I had not yet realised you could be such a consistent moron.
Yeah, you always were pretty slow to pick things up.
Marshall
PS. And I take objection to you calling me "consistent."
Marshall
Totally. That's what really makes the membership dues a "real" deal.
You reminded me of a story. A few years ago, I had a company
laptop that was rather out of date, and that had started behaving
erratically. I went to visit the techs in charge of such things, and
after a few days of diagnosing they told me I really ought to get
a new one. Fine by me. So I'm standing there in the tech area
with all those guys, and one female. (Not sure how she got
in there; perhaps separated from the herd by bad weather.)
I doubt any of them were within twenty years of my age.
So the tech explains to me the options: low-weight,
low processing power vs. heavier, better performance. Since
I'm a programmer and not the sort of guy to be writing up
reports in MS-WORD on the plane, I naturally picked the latter
one. "Gotta have the faster processor," I say. Tech says
sure and walks off to get one. And then, actually just to myself
and entirely under my breath I said, "Chicks will flock."
Cause, you know, gotta keep the funny in constant practice.
From ten feet away, the girl's head whips around and she
demands to know, "Did you just say, 'chicks will flock'?"
Oh, shit. "Uh, yeah," I admit. And then she just cracks up,
as does everyone else who witnessed the exchange.
Whew!
Marshall
Albrecht
Marshall schrieb:
> On May 7, 9:24 am, LudovicoVan <ju...@diegidio.name> wrote:
> > On 7 May, 13:13, David C. Ullrich <dullr...@sprynet.com> wrote:
> > > On Wed, 6 May 2009 17:04:15 -0700 (PDT), LudovicoVan
> > > <ju...@diegidio.name> wrote:
> >
> > > >It is (AFAIK) easy enough to come up with a production of _all_ the
> > > >infinite binary strings.
> >
> > > Exactly what does "come up with a production of" mean here?
> >
> > I mean "production" in the constructive sense: at least predicative.
> > Though I'm not putting this burden on Cantor's diagonal argument
> > itself, it's just the reference point for my counter-argument. For
> > instance, one could give an inductive definition, then implement and
> > run it in, say, Prolog. The program is not more "non-halting" than a
> > program to output the naturals.
>
> You can write a program to output all of the naturals. This program
> won't halt, as you say, and for any natural n, will eventually output
> n. (We are glossing over some resource limits here, but that is
> customary and reasonable.) It will never finish running, though;
> there are always more naturals.
>
> You can't do the same for the reals. That's because the reals
> aren't countable and the naturals are.
Really funny.
You say: "You can write a program to output _all_ of the naturals."
I'm sure, you can't.
You say: "It will never finish running, though;there are always more
naturals." Yes, but the same holds for the reals.
You "believe" in the set of real numbers. Let's have this set and a
program which arbitrarily picks out numbers of this set and put them
out (building a new set). This program never stops, right? So, what is
the difference? Naturals never ends, reals never ends.
And don't forget: ZFC must have a countable model.
> The analogous situation with printing out all the naturals is printing
> out a single real. For any digit position n, the program will
> eventually
> print out that digit, but it will never finish running; there are
> always
> more digits.
>
> If you want to say, hey, I'll stop printing a particular number when
> I get to some repeating pattern, then you're talking about a
> program to print out all the rational numbers, not the reals.
>
> If you want to print out real numbers, you can start, but you can't
> finish even one. If you want to print out an uncomputable real,
> you can't even start.
Wrong:
Start printing an (irrational) real number > phi < End printing an
(irrational) real number.
>
> So no, it is not easy enough to print out all the infinite binary
> strings; it's impossible actually to print out even one.
>
Some of your ideas are not well considered.
Regards
Albrecht Storz
William Elliot
>>> Clearly OP is has been duped into joining the currently popular
>>> religous cult of computerism.
>>
>> It's actually even worse than that. By framing the Cantor diagonal
>> construction in a computer-friendly way (e.g. for every i and j, the
>> "enumeration oracle" produces the j'th digit of the i'th list-entry in
>> finite time), one can readily construct a *computable* diagonal which
>> provably differs from every entry in the enumeration.
>
> Provably how?
>
Marshall
10 LET I=0
20 PRINT I
30 LET I = I + 1
40 GOTO 20
There. I just wrote a program to output _all_ the naturals.
Now surely you must abandon your claim that I can't, despite
your initial surety, for clearly I have written the program.
> You "believe" in the set of real numbers. Let's have this set and a
> program which arbitrarily picks out numbers of this set and put them
> out (building a new set). This program never stops, right? So, what is
> the difference?
The difference is the reals aren't countable. Also: every natural
is finitely representable; not every real is. So once your program
hits once such, it will never complete putting out its representation,
so it will never output any further numbers, and hence cannot output
every real.
> Start printing an (irrational) real number > phi < End printing an
> (irrational) real number.
Congratulations on being able to type a greek letter.
Marshall
lwa...@lausd.net
> <c7ccbbf2-af51-448e-b9da-773e185ec...@r36g2000vbr.googlegroups.com>,
> > So a contradiction!
> > Thanks a lot!
> Face facts: Cantor's diagonal proof that |R| > |N| is SIMPLE. It has
Of course Knox isn't the first standard set theorist to mention
computer proofs. Metamath, Prover9, and other computer proving
algorithms have been mentioned in these set theory threads. But
here I agree with WM's response:
"[Computers] do what their programmers want."
And their programmers want them to formulate proofs in the
dominant theory, not in alternate theories.
On the other hand, computers can't completely do what their
programmers want. Surely typing in the Riemann Hypothesis or
Goldbach's Conjecture and clicking "Prove" isn't going to
result in a proof of either conjecture -- at least not during
any of our lifetimes.
> Proving (say) ZFC to be inconsistent
> would be worth at least a Fields Medal and a centrefold picture in the
> Journal of the AMS. If it were easy (or even less than extremely
> difficult) to do then it would already have been done. The chance of
> you doing it is vanishingly small.
I actually agree with Knox here -- but only partly.
As I've mentioned before, Cantor's original theory, naive set
theory, was quickly proved inconsistent by Russell. This is the
reason Zermelo came up with ZFC. And ZFC has lasted for over a
century without any inconsistency proofs. The irony here is:
The more time passes, the _more_ likely we'll see a proof of,
say, the Riemann Hypothesis or Goldbach's Conjecture.
The more time passes, the _less_ likely we'll see a proof that
ZFC is inconsistent.
And I doubt, like Knox and the other standard set theorists,
that such an inconsistency proof, if it ever appears, will have
anything to do with Cantor's Theorem.
Right now, the only mathematician of whom I am aware is making
an attempt at an inconsistency proof is Ed Nelson. He believes
that he can proof PA to be inconsistent -- and since ZFC proves
that PA is consistent, if PA is proved to be inconsistent, then
ZFC would also be proved inconsistent.
If Nelson is successful, then some standard set theorists might
wonder why such a proof would have eluded them for so long when
compared to Russell's proof of the inconsistency of Cantor's
naive set theory. The reason is Nelson's attempt is based on
the operation of tetration, also called superexponentiation by
Nelson himself. Tetration, an operation which results in very
large numbers, is unknown to most of the set theorists who have
previously sought the Fields Medal due the prover of ~Con(ZFC),
and so it's not unreasonable that a proof that depends on
tetration would be unknown for so long.
If Nelson were to be successful, I suspect that an alternate
set theory to replace ZFC would develop, one which would avoid
the large numbers that led to Nelson's Paradox. Perhaps some
WM-style ultrafinitism would be in order.
But regardless of whether anyone can or will ever prove ZFC
inconsistent, if someone is opposed to ZFC because it proves
the existence of uncountable sets, then I see no reason why
such opponents of ZFC can't have an alternate set theory, one
which does agree with some of their intuitions. If there were a
rigorous theory in which more of their intutions are provable
than in ZFC, then maybe LV and the other opponents of the
dominant set theory would have less reason to start these
threads and complain about set theory all the time.
lwa...@lausd.net
In some theories other than ZFC, one can prove the existence
of non-Cantorian sets. In particular, their existence is
provable in the theory NFU.
A Cantorian set is essentially a set that satisfy's Cantor's
theorem -- so if x is a Cantorian set, then we must have
that card(x) < card(P(x)). So a non-Cantorian set is a set
that doesn't satisfy Cantor's theorem. So if y is a
non-Cantorian set, then card(y) >= card(P(y)).
Notice that NFU proves the existence of V, the set (not a
proper class, but a _set_) of all sets. Since P(V) is V
itself, it follows that the universal set must in fact be a
non-Cantorian set.
IIRC, the formal definition of a non-Cantorian set is a
set which fails to have the same cardinality as the set of
its singleton subsets. There is no bijection between V and
the set of all singletons, because the natural bijection
that maps each set to its own singleton is not a legal set
according to the Stratified Comprehension Schema. It's the
Stratified Comprehension Schema that allows there to be a
universal set yet still avoids Russell's Paradox.
But I assume (unless an NFU expert informs me otherwise)
that the ordinary sets of analysis, such as N and R, are
provably Cantorian in NFU. And so P(N), the powerset of N,
is still strictly larger than N. And NFU would still prove
that R is uncountable, presumably.
It might be interesting to see what would happen if there
were a set theory (not NFU) in which sets like N or R
turned out to be non-Cantorian. Such a theory might
satisfy the opponents of ZFC in this thread.
jesko
> In article
> <c7ccbbf2-af51-448e-b9da-773e185ec...@r36g2000vbr.googlegroups.com>,
>
> > If you map any real to N (Naturals) then you may conceive Reals as
> > the infinite uinion of denumerable
> > sets since N is always denumarable. But this is union must be not
> > walkable or not denumarable.
>
> How do you propose to map |R to |N ?
It is a coomon fact that the number of all properties over N is not
denumerable.
Since anyway you list those properties another property not in the
list can be added.
so is R ---> N x N x N ...... x N
But if you fixed a list of those properties than you may add a new
property to the starting list
a your list is numbered.
But also with sinply Naturals you do the same!
This to make evident that N as R are not really numbered cause you can
find alway find a new elements in both case.
So infinite is not numbered by definition.
Albrecht
This program doesn't output _all_ naturals. Sketch of a proof: let's
say your program outputs the number n. Since there are infinitely many
naturals N > n there are nearly all naturals which won't be output -
for every n!
>
>
> > You "believe" in the set of real numbers. Let's have this set and a
> > program which arbitrarily picks out numbers of this set and put them
> > out (building a new set). This program never stops, right? So, what is
> > the difference?
>
> The difference is the reals aren't countable. Also: every natural
> is finitely representable; not every real is. So once your program
> hits once such, it will never complete putting out its representation,
> so it will never output any further numbers, and hence cannot output
> every real.
10 LET I=0
15 LET r=random real number of R
20 PRINT r
25 LET R=R without r
30 LET I = I + 1
40 GOTO 15
So, what is the difference between naturals and reals?
>
>
> > Start printing an (irrational) real number > phi < End printing an
> > (irrational) real number.
>
> Congratulations on being able to type a greek letter.
>
Some people see a greek letter. Others are aware of an irrational
number - and are able to compute it.
Regards
Albrecht Storz
David C. Ullrich
<ju...@diegidio.name> wrote:
>On 7 May, 13:13, David C. Ullrich <dullr...@sprynet.com> wrote:
>> On Wed, 6 May 2009 17:04:15 -0700 (PDT), LudovicoVan
>> <ju...@diegidio.name> wrote:
>> >Mostly, a thought experiment:
>>
>> >Cantor claims: "whichever list of infinite (binary) strings you can
>> >come up with, I will (anti-)diagonalise it."
>>
>> >It is (AFAIK) easy enough to come up with a production of _all_ the
>> >infinite binary strings.
>>
>> Exactly what does "come up with a production of" mean here?
>
>I mean "production" in the constructive sense: at least predicative.
That really doesn't answer my question.
>Though I'm not putting this burden on Cantor's diagonal argument
>itself, it's just the reference point for my counter-argument. For
>instance, one could give an inductive definition, then implement and
>run it in, say, Prolog.
But _this_ is a good hint what you mean.
No, it is _not_ possible to write a Prolog program that produces
all infinite binary strings. You can _say_ that's "easy enough"
if you wish.
>The program is not more "non-halting" than a
>program to output the naturals.
Halting or not is not the problem.
>> >The problem remains how to make the list
>> >bullet-proof to diagonalisation. All we can do is falsify the
>> >diagonalisation procedure itself, by following the claim to the
>> >letter:
>>
>> >We start by producing our list, entry by entry; in parallel, our
>> >opponent starts building the anti-diagonal (I will abstract from the
>> >technical details, unnecessary here):
>>
>> > � �List � Diagonal Anti-diagonal
>> > � �.(0) � � � � 0 � � � � � � 1
>> > � �.(0)1 � � � �0 � � � � � � 1
>> > � � ... � � � � ... � � � � � ...
>>
>> >At this point, one migth wander: is there? is not there?
>>
>> Is there _what_?
>
>The anti-diagonal: is it in the list? Is it not?
It is not. This is incredibly obvious.
>The proper question
>is: will the program ever output it's anti-diagonal?
The "proper question" according to you asks a question
about a program that does not exist.
>> > � � � �=== Cantor's diagonal is a non-halting machine. ===
>>
>> It's not a machine at all.
>
>Turing machines can be an interpretation tool here. Anti-
>diagonalisation is a process, not yet a total function, because
>decisions about infinities are a consequence in our case, not a
>premise (they are yet to be taken).
>
>> You're talking about infinite strings of digits. Can you
>> give an example of a _halting_ machine that produces
>> such a thing? No.
>
>As said, asking for a machine that produces all infinite binary
>strings and halts is just as sensible as asking for a machine that
>produces all naturals and halts.
Yes it is. Who has ever said anything about a TM that produces
all the naturals and then halts?
>> This has nothing to do with the
>> diagonal argument - the question of halting machines
>> is simply irrelevant.
>
>> >Under this perspective, accepting the diagonal argument "simply"
>> >implies a specific choice about infinity (and infinities; and what can
>> >or cannot be proved; and a fundamental paradox: incongruent by
>> >construction).
>>
>> You're aware that this entire post is incoherent, right?
>
>It's all but incoherent. Maybe it's unclear, maybe it's incorrect in
>many ways, maybe there is something you are still missing, maybe a bit
>of all of them.
>
>In synthesis, the incongruency I am talking about could be seen in
>this fact: we are denied the existence of a complete list, in terms of
>a construct that is claimed to be complete.
>
>> >Now, what about Turing?
>>
>> What about Turing?
>
>Turing leverages the diagonal argument to show the insolubility of the
>halting problem (consequently failing Hilbert's program, by the way).
>In any case, I find Turing and his machines interesting here because,
>as far as I can see, Turing reasons at the same "primitive" (in the
>theoretical sense) level as Cantor.
>
>-LV
David C. Ullrich
"Understanding Godel isn't about following his formal proof.
That would make a mockery of everything Godel was up to."
(John Jones, "My talk about Godel to the post-grads."
in sci.logic.)
Marshall
> > > I'm sure, you can't.
>
> > 10 LET I=0
> > 20 PRINT I
> > 30 LET I = I + 1
> > 40 GOTO 20
>
> > There. I just wrote a program to output _all_ the naturals.
> > Now surely you must abandon your claim that I can't, despite
> > your initial surety, for clearly I have written the program.
>
> This program doesn't output _all_ naturals. Sketch of a proof: let's
> say your program outputs the number n. Since there are infinitely many
> naturals N > n there are nearly all naturals which won't be output -
> for every n!
Oh, you didn't see the third and fourth line of
the program. Try to read *all* the lines; they all
do something.
Marshall
Herbert Newman
> On May 8, 4:01�am, Albrecht <albst...@gmx.de> wrote:
>
>> Marshall schrieb:
>>>
>>> 10 LET I=0
>>> 20 PRINT I
>>> 30 LET I = I + 1
>>> 40 GOTO 20
>>
>>> There. I just wrote a program to output _all_ the naturals.
>>> Now surely you must abandon your claim that I can't, despite
>>> your initial surety, for clearly I have written the program.
>>>
>> This program doesn't output _all_ �naturals. Sketch of a proof: let's
>> say your program outputs the number n. Since there are infinitely many
>> naturals N > n there are nearly all naturals which won't be output -
>> for every n!
>>
> Oh, you didn't see the third and fourth line of
> the program. Try to read *all* the lines; they all
> do something.
>
Never mind, Albrecht is a complete i***.
@Albrecht: Which natural number will not being printed out by the program?
Sooner or later (if we want to refer to the time metaphor) _any_ natural
number is produced and (printed out) by the program.
Herb
Owen Jacobson
Would you prefer he called you a "complete" moron?
:),
-o
Brian Chandler
Oh yes, but don't you see? There's an infinite number of numbers that
won't be printed "for every n". So if we play "My Dad has more money
than yours" for exactly two rounds, you say: "For any n, n will be
printed". Which wins round 1, but I say "So for that n being printed,
there's squillions more, like n*230 and n!, and ceil(pi * n * 35000)
which have not been printed. So I can always show more unprinted
numbers than printed ones, and that's round 2, which is the end, so I
win.
(Incidentally, what's an i***?)
Brian Chandler
jellovirus
I'm surprised no one mentioned that this program will eventually either
crash with an overflow (if I is of an integer type) or stop counting (if
I is of a floating-point type, where once it hits a certain size it will
discard the least-significant bits). Of course, your variable could be
a BigInt, but even then your computer would run out of RAM long before
all the natural numbers have been counted (and I'd like to see someone
implement bigint in basica).
Marshall
> >>>> Marshall schrieb:
> >>>>> 10 LET I=0
> >>>>> 20 PRINT I
> >>>>> 30 LET I = I + 1
> >>>>> 40 GOTO 20
>
> crash with an overflow (if I is of an integer type) or stop counting (if
> I is of a floating-point type, where once it hits a certain size it will
> discard the least-significant bits). Of course, your variable could be
> a BigInt, but even then your computer would run out of RAM long before
> all the natural numbers have been counted (and I'd like to see someone
> implement bigint in basica).
I did mention that. I said "We are glossing over some
resource limits here, but that is customary and reasonable."
Just to be absolutely clear, my choice of BASIC as
a language was meant to underscore the triviality of
the problem being solved.
Marshall
Mariano Suárez-Alvarez
> On May 7, 3:56 am, Barb Knox <s...@sig.below> wrote:
>
> > In article
> > <c7ccbbf2-af51-448e-b9da-773e185ec...@r36g2000vbr.googlegroups.com>,
> > > So a contradiction!
> > > Thanks a lot!
> > Face facts: Cantor's diagonal proof that |R| > |N| is SIMPLE. It has
> > even been CHECKED BY COMPUTERS.
>
> Of course Knox isn't the first standard set theorist to mention
> computer proofs. Metamath, Prover9, and other computer proving
> algorithms have been mentioned in these set theory threads. But
> here I agree with WM's response:
>
> "[Computers] do what their programmers want."
>
> And their programmers want them to formulate proofs in the
> dominant theory, not in alternate theories.
Programmers are mostly theory-agnostic when they are
programming provers. What on earth suggests to you
that, say, Prover9 is restricted to (whatever it is
that you consider) dominant set theory? That you
seem to think there is such a restriction is a
clear sign that you have absolutely no idea what
an automatic prover is.
Your theory of "dominat theories" becomes more and
more absurd...
> On the other hand, computers can't completely do what their
> programmers want. Surely typing in the Riemann Hypothesis or
> Goldbach's Conjecture and clicking "Prove" isn't going to
> result in a proof of either conjecture -- at least not during
> any of our lifetimes.
>
> > Proving (say) ZFC to be inconsistent
> > would be worth at least a Fields Medal and a centrefold picture in the
> > Journal of the AMS. If it were easy (or even less than extremely
> > difficult) to do then it would already have been done. The chance of
> > you doing it is vanishingly small.
>
> I actually agree with Knox here -- but only partly.
>
> As I've mentioned before, Cantor's original theory, naive set
> theory, was quickly proved inconsistent by Russell. This is the
> reason Zermelo came up with ZFC. And ZFC has lasted for over a
> century without any inconsistency proofs. The irony here is:
>
> The more time passes, the _more_ likely we'll see a proof of,
> say, the Riemann Hypothesis or Goldbach's Conjecture.
> The more time passes, the _less_ likely we'll see a proof that
> ZFC is inconsistent.
You must operate under a rather strange definition of
what "irony" means. Moreover, your divining powers seem
to be quite great... What possible basis do you have
for the two claims you make?
Can you please point to *someone* who *does* see
a reason why opponents of ZFC can't have an alternate
theory?
-- m
MoeBlee
> And don't forget: ZFC must have a countable model.
Oh yeah, as if we were all going to forget about that.
You're silly.
MoeBlee
MoeBlee
> Cantor's original theory, naive set
> theory, was quickly proved inconsistent by Russell.
Russell proved Frege's formal system inconsistent. Cantor himself
already knew of the ordinal and cardinal paradoxes.
> This is the
> reason Zermelo came up with ZFC.
Would you please site where Zermelo said that.
> and since ZFC proves
> that PA is consistent, if PA is proved to be inconsistent, then
> ZFC would also be proved inconsistent.
Correct conlusion, but INCORRECT reasoning. If PA is inconsistent but
ZFC proves PA consistent, then all we can infer from those mere facts
is that ZFC proves false arithmetical statements, not necessarily that
ZFC is inconsistent. The actual reasoning for the inconsistency of ZFC
given the inconsistency of PA is that PA is embedded in ZFC. So this
is not a matter of whether ZFC proves PA consistent. Rather, if PA is
inconsistent then ZFC is inconsistent, since ZFC embeds PA.
> But regardless of whether anyone can or will ever prove ZFC
> inconsistent, if someone is opposed to ZFC because it proves
> the existence of uncountable sets, then I see no reason why
> such opponents of ZFC can't have an alternate set theory, one
> which does agree with some of their intuitions.
Sure. And this theory will be rich enough to do the kinds of things
ZFC does?
> If there were a
> rigorous theory in which more of their intutions are provable
> than in ZFC, then maybe LV and the other opponents of the
> dominant set theory would have less reason to start these
> threads and complain about set theory all the time.
There's no problem making such a theory. The problem is making such a
theory that is ALSO rich enough to do the kinds of things ZFC does.
MoeBlee
MoeBlee
> IIRC, the formal definition of a non-Cantorian set is a
> set which fails to have the same cardinality as the set of
> its singleton subsets.
So y is a non-Cantorian set <-> card(y) ~= {{x} | xey}.
Okay, thanks.
MoeBlee
Marshall
> >
> > Face facts: Cantor's diagonal proof that |R| > |N| is SIMPLE. It has
> > even been CHECKED BY COMPUTERS.
>
> Of course Knox isn't the first standard set theorist to mention
> computer proofs. Metamath, Prover9, and other computer proving
> algorithms have been mentioned in these set theory threads. But
> here I agree with WM's response:
>
> "[Computers] do what their programmers want."
I can state with firm authority that programs almost
never do what their programmers want. Computation
follows its own logic, and is entirely immune to the
wishes, intent, or dress code of those who set it
in motion.
> And their programmers want them to formulate proofs
> in the dominant theory, not in alternate theories.
Prover9 takes your first order theory as input.
It doesn't have any way to tell if the input you gave
it is "dominant" or not.
> On the other hand, computers can't completely do what their
> programmers want. Surely typing in the Riemann Hypothesis or
> Goldbach's Conjecture and clicking "Prove" isn't going to
> result in a proof of either conjecture -- at least not during
> any of our lifetimes.
A few years back you could have said the same thing
about the Robbins Conjecture. It had survived many
decades without anyone coming up with a proof or
a counterexample, and it had been worked on by the
likes of Huntington, Tarski, and of course Robbins.
Then one day Bill McCune typed the Robbins conjecture
into EQP, hit "Prove" and got out a proof. (EQP is a
precursor to Otter which is a precursor to Prover9.)
(I'm not a number theorist, but couldn't Goldbach's
conjecture be expressed as a first order sentence, within
some appropriate axiomatization of the naturals? If so,
it is entirely possible that someone will one day type
it in a hit "prove" and get a proof, if it is actually true.)
> But regardless of whether anyone can or will ever prove ZFC
> inconsistent, if someone is opposed to ZFC because it proves
> the existence of uncountable sets, then I see no reason why
> such opponents of ZFC can't have an alternate set theory, one
> which does agree with some of their intuitions.
My own feeling is that if someone is opposed to ZFC
because they would rather put flowers in their garden,
I see no reason why they can't plant some geraniums. And
I dare the niggling nabobs of natural numbers to naysay me.
Marshall
MoeBlee
> > 10 LET I=0
> > 20 PRINT I
> > 30 LET I = I + 1
> > 40 GOTO 20
>
> > There. I just wrote a program to output _all_ the naturals.
> > Now surely you must abandon your claim that I can't, despite
> > your initial surety, for clearly I have written the program.
>
> This program doesn't output _all_ naturals.
Then please say what is the least natural number not outputted by the
program.
MoeBlee
Jan
I have some naive questions:
On 8 Maj, 13:01, Albrecht <albst...@gmx.de> wrote:
>> 10 LET I=0
>> 20 PRINT I
>> 30 LET I = I + 1
>> 40 GOTO 20
>
>This program doesn't output _all_ naturals. Sketch of a proof: let's
>say your program outputs the number n. Since there are infinitely many
>naturals N > n there are nearly all naturals which won't be output -
>for every n!
Can you supply a natural number n, that the program won't print?
> 10 LET I=0
> 15 LET r=random real number of R
> 20 PRINT r
> 25 LET R=R without r
> 30 LET I = I + 1
> 40 GOTO 15
>
> So, what is the difference between naturals and reals?
Can you please define the "function" returning: "random real number of
R"?
How do you represents the reals?
> Start printing an (irrational) real number > phi < End printing an
> (irrational) real number.
Following that approach - how will you represent/present all the other
transcendental real numbers? (e is of cause obvious...)
Kind regards, Jan
LudovicoVan
> On May 7, 4:21 am, WM <mueck...@rz.fh-augsburg.de> wrote:
>
> > On 7 Mai, 12:56, Barb Knox <s...@sig.below> wrote:
>
> > > Face facts: Cantor's diagonal proof that |R| > |N| is SIMPLE.
>
>
> If there is no set whose members are all and only the natural numbers,
> then the very question of comparison between N and R reduces to what
> 'N' and 'R' would stand for; and this is not a very interesting
> question.
As I have already noted in this thread, the formal, axiomatic proofs
presuppose what here is in question, mainly a decision about
"infinities".
-LV
LudovicoVan
> Whether an intuitionist accepts the axioms used in the diagonal
> argument is one matter. But ASIDE from the axioms, the LOGIC used in
> the diagonal argument IS intuitionistic.
The diagonal argument is impredicative.
-LV
LudovicoVan
>
> LudovicoVan <ju...@diegidio.name> wrote:
> > On 7 May, 11:56, Barb Knox <s...@sig.below> wrote:
>
> > > Face facts: Cantor's diagonal proof that |R| > |N| is SIMPLE. It has
> > > even been CHECKED BY COMPUTERS.
>
> > embedded, as an informing principle, into their axioms and
> > definitions.
>
> > > Therefore the only way that |R| = |N|
> > > is if the various formulations of axiomatic set theory are internally
> > > INCONSISTENT
>
> > Incorrect (and a myopic). They can be formally consistent with unsound
> > or otherwise invalid premises.
>
> How does one test individual premises or sets of premises for
> unsoundness or invalidity? Unless one has some absolute standards and
> can make everyone agree with them, one can never be absolutely sure.
It's not a matter of being sure or of absolute standards. It's a
*choice*, possibly related to the requirements and constraints at
hand, and so on. Obviously.
> > Indeed, the diagonal argument here
> > under investigation, is an informing principle to standard axiomatic
> > set theories.
>
> But until YOUR standards of consistency and soundness are universally
> accepted, such questions are moot.
Your objection is senseless.
-LV
LudovicoVan
> There is a sense in which Cantor's argument does work, i.e., for any
> constructible binary list, one can show by constructible methods that
> there is a constructible non-member.
This is false, as a matter of fact. Cantor's argument is
impredicative, so constructively invalid.
-LV
LudovicoVan
> On May 7, 9:24 am, LudovicoVan <ju...@diegidio.name> wrote:
>
> > On 7 May, 13:13, David C. Ullrich <dullr...@sprynet.com> wrote:
> > > On Wed, 6 May 2009 17:04:15 -0700 (PDT), LudovicoVan
> > > <ju...@diegidio.name> wrote:
>
> > > >It is (AFAIK) easy enough to come up with a production of _all_ the
> > > >infinite binary strings.
>
> > > Exactly what does "come up with a production of" mean here?
>
> > I mean "production" in the constructive sense: at least predicative.
> > itself, it's just the reference point for my counter-argument. For
> > instance, one could give an inductive definition, then implement and
> > program to output the naturals.
>
> won't halt, as you say, and for any natural n, will eventually output
> n. (We are glossing over some resource limits here, but that is
> customary and reasonable.) It will never finish running, though;
> there are always more naturals.
>
> You can't do the same for the reals. That's because the reals
> aren't countable and the naturals are.
That ultimately depends on your stance on the diagonal argument.
[snip]
> So no, it is not easy enough to print out all the infinite binary
> strings; it's impossible actually to print out even one.
I tend to be quite informal. The actual form of such a program is
shown in this post by Alan Smaill:
http://groups.google.co.uk/group/sci.logic/msg/f97f03e6962c091a?hl=en
-LV
LudovicoVan
> LudovicoVan <ju...@diegidio.name> writes:
> > On 7 May, 11:56, Barb Knox <s...@sig.below> wrote:
>
> > > Face facts: Cantor's diagonal proof that |R| > |N| is SIMPLE. It has
> > > even been CHECKED BY COMPUTERS.
>
> > Formal proofs are irrelevant to the diagonal argument: they have it
> > embedded, as an informing principle, into their axioms and
> > definitions.
>
> You have made it several times, and not yet given the slightest
> reason for anyone to believe it.
There has been a discussion specifically on this in the thread "Levy
proof that R is uncountable":
http://groups.google.co.uk/group/sci.logic/browse_frm/thread/876837fdd0fdfc6e/6d8e02441eb1e5f8
-LV
LudovicoVan
> LudovicoVan <ju...@diegidio.name> writes:
> > is: will the program ever output it's anti-diagonal?
>
> So your choice of question is seriously loaded -- your program will
> never output a binary expansion of even one real number.
>
> Now, maybe this is a good way to think of the potential infinite
> and constructivism -- but as you expressed it here, you need to
> be more even-handed about what it means to construct a number (and a list
> of numbers).
I am fine with an approach like Bishop's as you show in another post,
with some provisions to follow.
> > As said, asking for a machine that produces all infinite binary
> > strings and halts is just as sensible as asking for a machine that
> > produces all naturals and halts.
>
> So what are *you* asking for when you ask whether the program can *output*
> its anti-diagonal?
That's the key issue here: what's this anti-diagonal at all. Note that
the OP is about falsifying the diagonalisation procedure: by showing
that the anti-diagonal is not a valid construct. I have put this in
terms of an incongruency: an incomplete list by a complete anti-
diagonal.
-LV
Marshall
> On 8 May, 00:03, Marshall <marshall.spi...@gmail.com> wrote:
>
> > You can write a program to output all of the naturals. This program
> > won't halt, as you say, and for any natural n, will eventually output
> > n. (We are glossing over some resource limits here, but that is
> > customary and reasonable.) It will never finish running, though;
> > there are always more naturals.
>
> > You can't do the same for the reals. That's because the reals
> > aren't countable and the naturals are.
>
> That ultimately depends on your stance on the diagonal argument.
My stance controls what programs it is possible to write, you say?
So if I change my stance, a different set of things become
computable? I Did Not Know That.
> [snip]
>
> > So no, it is not easy enough to print out all the infinite binary
> > strings; it's impossible actually to print out even one.
>
> I tend to be quite informal. The actual form of such a program is
> shown in this post by Alan Smaill:
>
> http://groups.google.co.uk/group/sci.logic/msg/f97f03e6962c091a?hl=en
That shows how to write a program that will output an infinite
binary string? If I used a small font, will the whole string
fit on a single page?
Marshall
LudovicoVan
> Let's look at total functions taking two natural numbers and returning
> either 0 or 1, eg f(n,m). If we leave out the question of
> multiple representations, let's suppose you have implemented
> such a total function.
Great.
[snip]
> So, the anti-diagonal is itself something given algorithmically,
> and you can easily write the procedure to return its nth digit,
> provided that the given listing of reals itself is a total
> function -- this does not mean that all the digits involved must
> be computed, of course!
My point (my take) is that this simply does not solve our issue: the
fact that the anti-diagonal does not belong to the list cannot be
proven from the algorithmic definition alone. The key issue is what
happens at infinity, and my thesis, to report it here in short, is
that the anti-diagonal, as any other computable string, is simply
there, in the range of a putative function 'f' like you describe
above: there is no member missing. If we extend for
"compactification" (trying some possibly wrong terminology), the anti-
diagonal is just a "limit point" of 'f'.
-LV
MoeBlee
And I already responded to that claim. You just skipped dealing with
my response. Please, if there is to be any dialogoue, it is not
practical if you are going to just pretend that my responses don't
exist.
[start previous exchange (you're first):]
> In
> particular, any formal, axiomatic proof is absolutely of no relevance
> to an enquiry on the diagonal argument (and, strictly speaking, a way
> to beg the question), because it is derived from axioms that embed, as
> informing principles, the very results under investigation.
EVERY formal system embeds ALL the results that are provable from its
axioms. That is the NATURE of a formal system. Yes, OF COURSE, in Z
set theory, we adopt the axioms that will prove what we want the
axioms to prove (in Zermelo's particular case, it was to prove the
well ordering theorem from axioms including the axioms of choice).
Sure, granted, there are two basic approaches (and a combination of
them): (1) Adopt only axioms that express some principles that we
consider to be bedrock true and then let the chips fall where they may
(i.e., let whatever theorems come out or don't come out from the
bedrock principles). (2) Have in mind a whole bunch of theorems we
wish to axiomatize (such as the theorems that make up the mathematics
for the sciences) and then find axioms that prove those theorems. (3)
Some combination of (1) and (2).
It seems to me that set theory is in category (3). We'd like to have
an axiomatization for the mathematics for the sciences (at least) and
also we (editorial 'we') find the basic axioms THEMSELVES of set
theory to be quite faithful to our most basic notions of the
membership relation among sets.
So, if you're going to object to set theory on this basis, then what
category (1) axiomatization do you propose instead? And what are you
going to answer if that axoimatization doesn't even prove the basic
theorems for the mathematics for the sciences?
[end previous exchange]
So would you please address that question: What axiomatization do you
propose instead? And what are you
going to answer if that axoimatization doesn't even prove the basic
theorems for the mathematics for the sciences?
MoeBlee
Alan Smaill
So, where does impredicativity play a role in the argument?
> -LV
--
Alan Smaill
David R Tribble
>> 10 LET I=0
>> 20 PRINT I
>> 30 LET I = I + 1
>> 40 GOTO 20
>> There. I just wrote a program to output _all_ the naturals.
>> Now surely you must abandon your claim that I can't, despite
>> your initial surety, for clearly I have written the program.
>
jellovirus wrote:
> I'm surprised no one mentioned that this program will eventually either
> crash with an overflow (if I is of an integer type) or stop counting (if
> I is of a floating-point type, where once it hits a certain size it will
> discard the least-significant bits). Of course, your variable could be
> a BigInt, but even then your computer would run out of RAM long before
> all the natural numbers have been counted (and I'd like to see someone
> implement bigint in basica).
That problem is easily fixed. Instead of printing out each natural
as a separate string of digits, this new program will print out
each natural as a base-1 number, i.e., as a string of '1' digits:
10 LET I = 0
20 PRINT I;
30 GOTO 10
Now each and every natural will be printed.
MoeBlee
If you are the same poster about a year ago under a different name
whom I'm thinking of, then it was *I* who first told you about
impredicativity. What is impredicative is the axiom schema of
separation. (But we figured out something with Aatu's help as to
whether the PARTICULAR instance of the axiom schema of separation used
in the diagonal argument is impredicative, though, alas, I've
forgotten what we concluded.)
In any case, my point stands, an intuitionist may not accept the
AXIOMS used, but the LOGIC used is purely intuitionistic.
MoeBlee
Alan Smaill
> On 7 May, 18:06, Alan Smaill <sma...@SPAMinf.ed.ac.uk> wrote:
> > LudovicoVan <ju...@diegidio.name> writes:
> > > On 7 May, 11:56, Barb Knox <s...@sig.below> wrote:
> >
> > > > Face facts: Cantor's diagonal proof that |R| > |N| is SIMPLE. ï¿œIt has
> > > > even been CHECKED BY COMPUTERS.
> >
> > > Formal proofs are irrelevant to the diagonal argument: they have it
> > > embedded, as an informing principle, into their axioms and
> > > definitions.
> >
> > Why should we believe this assertion of yours?
> > You have made it several times, and not yet given the slightest
> > reason for anyone to believe it.
>
> There has been a discussion specifically on this in the thread "Levy
> proof that R is uncountable":
>
> http://groups.google.co.uk/group/sci.logic/browse_frm/thread/876837fdd0fdfc6e/6d8e02441eb1e5f8
I have been following the thread.
You have rightly said that logical priority is different from historical
priority. At no point have you or anyone else given us any reason
to suppose that the diagonal argument is embedded into the axioms
and definitions of either classical or constructive theories
of the real numbers.
> -LV
--
Alan Smaill