halting problem proof, via diagonalization?
RichD
machine halting problem is an example of diagonalization."
I don't see that. As I recall, it's proof by contradiction;
assume a program which accomplishes the goal, feed
the code of this program to itself, etc., ad absurdum. QED
Whereas diagonalization consists of constructing a list,
then constructing a new object not in the list, etc.
Can anyone reconcile this?
--
Rich
David C. Ullrich
The word "diagonalization" gets used a little informally -
in some sense the idea behind the two proofs, or part
of the structure of the two proofs, is the same.
In the proof of the uncountability of the reals we
start with a sequence x_1, x_2, ... of reals.
Say x_j[n] is the n-th digit in the decimal expansion
of x_j. Then x_j[j] is a "diagonal" element of a
certain "matrix", and the proof proceeds by constructing
a real number x such that x[j] is _not_ equal to x_j[j].
Note the "not".
Here's another proof by "diagonalization" that's just
one notch more abstract. If A is a set then P(A)
is the power set of A; that is, P(A) is the set of
all subsets of A.
Thm 1. If A is a set then there is no function
mapping A _onto_ P(A).
In other words, if f : A -> P(A) is any function
then there exists S in P(A) (ie S is a subset of A)
such that S is not equal to f(a) for any a in A.
Proof: Suppose f : A -> P(A). Define S, a subset
of A, by
S = {x in A such that x is not an element of f(x)}.
(Note the "not" there...)
Then for any a in A, S is not equal to f(a).
Suppose on the other hand that S = f(a)
for some particular a in A. Now, either
a is an element of S or a is not an element
of S. But if a is an element of S then the
definition of S shows that a is not an element
of S. And if a is not an element of S then the
definition of S shows that a _is_ an element
of S.
So both a in S and a not in S are impossible.
Contradiction, QED.
Let''s rephrase the theorem and the proof to make it look
more like the diagonal argument showing the reals are
uncountable. If A is a set then 2^A is the set of all
function mapping A into the two-element set {0,1}.
Since there _is_ an obvious one-to-one correspondence
between P(A) and 2^A, Theorem 1 is the same as saying
that there is no function mapping A onto 2^A. And that's
the same as this:
Thm 2. Suppose A is a set, and suppose that for every
a in A we are given a function x_a, which maps A into
{0,1}. (So x_a(b) is 0 or 1 for every a, b in S.) Then
there exists x, a function mapping A into {0,1},
such that x is not equal to x_a for any a in A.
Proof: Define x : A -> {0,1} by
x(a) = 1 - x_a(a) (for all a in A).
The point to that funny formula 1 - x_a(a)
is just that x(a) is _not_ equal to x_a(a)
(because 1 - 0 = 1 <> 0 and 1 - 1 = 0 <> 1.)
Since x(a) is not equal to x_a(a), x is not the
same as x_a. QED.
Note that x_a(a) is the "diagonal" element of
our array of functions {x_a}, and the key is
constructing x so x(a) <> x_a(a). Exactly
like the x[j] <> x_x[j] in the proof of uncountability
of the reals.
So Theorem 2 really is a diagonalization argument;
the proof is almost exactly the same as the proof
of uncountability of the reals. But the proof of
Theorem 1 is really the same as the proof of Theorem 2,
just in different notation. So Theorem 1 gets called
a diagonal argument as well.
Now look at the "Sketch of Proof" at
http://en.wikipedia.org/wiki/Halting_problem
and the comments that follow.
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.)
Peter_Smith
There's something about the aptness of extending the idea of
diagonalization from "diagonalizing out of a list" to the sorts of
constructions involved in constructing a standard Gödel sentence (or
in proving the unsolvability of the halting problem) in my
Introduction to Gödel's Theorems [www.godelbook.net], at p. 130, cf.
p. 307.
Daryl McCullough
You can express the unsolvability of the halting problem
as a theorem that is proved by diagonalization:
Pick some standard way to assign a unique integer to every Turing
machine program that takes exactly one input. We will say that
the integer assigned to a Turing machine M is the "code" of M.
Say that a pair <n,x> of integers is a "non-halting pair" if
the Turing machine with code n does not halt on input x.
Theorem 1: If <n_1,x_1>, <n_2,x_2>, ... is any computable list
of non-halting pairs, then there is a non-halting pair <n,x>
that is not on that list.
Proof: Let M(x) be the program that checks to see if <x,x> is
on the list, and if so, halts. If <x,x> is not on the list, then
M(x) runs forever. Let n be the code of M. Then <n,n> is a
non-halting pair, but it is not on the list.
--
Daryl McCullough
Ithaca, NY
LauLuna
Diagonalization is a very general tecnique aiming at showing thet a
certain set S does not exist: e.g. a countable set of all reals
(Cantor), a bijection between A and P(A) (Cantor), a recursively
enumerable set of all arithmetical truths (Gödel), an arithmetically
definable set of all arithmetical truths (Tarski), etc.
The tecnique can be seen as a reductio of the assumption that S exists
and it typically proceeds by constructing a diagonal object D that
should be in S if S existed but that, by construction, cannot be in
S.
This is sometimes put as the indefinite extensibility of any set T
'purporting' to be S; then it's shown that there is a (diagonal)
function f that for any T gives an object d such that d is in T if T=S
and it's shown that d is actually not in T. You may or may not require
that f be computable.
Now consider the usual proof of Turing's theorem. Assume there is a
Turing machine H that computes the halting problem for any Turing
machine. Then we can use H to construct a double input matrix M that
for any pair (m, n), where m is a code (a Gödel number) of a Turing
machine and n is a natural, displays 1 if m terminates on n and 0
otherwise.
Now H must be in M coded (say) by h. We give h to H (h acting as a
code for (h, h)) in order to fill in the corresponding square in M. To
decide the halting problem for this specific input, H has to compute
what H does when fed h, that is, it has to compute whether its current
computation terminates; the ensuing circularity prevents H from giving
an output and forces us to leave the corresponding square in M blank.
So, under the assumption that H exists, we've produced a computation
(h, h) whose behavior is not represented in M, which contradicts the
assumption.
Since M can be regarded as a set, (h, h) is an object that should be a
member of M (if H existed) but is not such; thus the procedure fits
with the general diagonal procedure described above.
Regards
ju...@diegidio.name
> On Aug 8, 11:09 am, RichD <r_delaney2...@yahoo.com> wrote:
>
> > I heard someone say recently, "The proof of the Turing
> > machine halting problem is an example of diagonalization."
>
> > I don't see that. As I recall, it's proof by contradiction;
> > assume a program which accomplishes the goal, feed
> > the code of this program to itself, etc., ad absurdum. QED
>
> > Whereas diagonalization consists of constructing a list,
> > then constructing a new object not in the list, etc.
>
> > Can anyone reconcile this?
>
> > --
> > Rich
>
> Diagonalization is a very general tecnique aiming at showing thet a
> certain set S does not exist: e.g. a countable set of all reals
> (Cantor), a bijection between A and P(A) (Cantor), a recursively
> enumerable set of all arithmetical truths (Gödel), an arithmetically
> definable set of all arithmetical truths (Tarski), etc.
>
> The tecnique can be seen as a reductio of the assumption that S exists
> and it typically proceeds by constructing a diagonal object D that
> should be in S if S existed but that, by construction, cannot be in
> S.
And this is where there are most of the objections.
Below again a simple argument to show that from the very same
construction we could induce the exact opposite result:
1: The diagonal differs from the 1st entry in the 1st place;
2: The diagonal differs from the 2nd entry in the 2nd place;
...
n: The diagonal differs from the n-th entry in the n-th place;
It seems straightforward to induce that, at the limit, the difference
between the diagonal and the limit entry tends to zero.
-LV
MoeBlee
> Below again a simple argument to show that from the very same
> construction we could induce the exact opposite result:
>
> 1: The diagonal differs from the 1st entry in the 1st place;
> 2: The diagonal differs from the 2nd entry in the 2nd place;
> ...
> n: The diagonal differs from the n-th entry in the n-th place;
>
> It seems straightforward to induce that, at the limit, the difference
> between the diagonal and the limit entry tends to zero.
WHAT limit? You need to DEFINE "limit" in terms of some topology,
metric, ordering, or whatever. We don't just use the word "limit"
without the context of the EXACT sense of a limit as it has been
DEFINED.
Moreover, the anti-diagonal differes from every entry in the list.
That's all that is required to show that the anti-diagonal is not on
the list.
MoeBlee
Aatu Koskensilta
> Below again a simple argument to show that from the very same
> construction we could induce the exact opposite result:
>
> 1: The diagonal differs from the 1st entry in the 1st place;
> 2: The diagonal differs from the 2nd entry in the 2nd place;
> ...
> n: The diagonal differs from the n-th entry in the n-th place;
>
> It seems straightforward to induce that, at the limit, the difference
> between the diagonal and the limit entry tends to zero.
Wonderful. I wonder how many people will rush in to the rescue, asking
"What limit entry?" or exclaiming most ferociously "There is no limit
entry!". Surely you can anticipate this response just as well as the
next man. The obvious question, then, is why bother? Why not come up
with some novel rubbish?
--
Aatu Koskensilta (aatu.kos...@uta.fi)
"Wovon man nicht sprechen kann, darüber muss man schweigen"
- Ludwig Wittgenstein, Tractatus Logico-Philosophicus
ju...@diegidio.name
> ju...@diegidio.name writes:
> > Below again a simple argument to show that from the very same
> > construction we could induce the exact opposite result:
>
> > 1: The diagonal differs from the 1st entry in the 1st place;
> > 2: The diagonal differs from the 2nd entry in the 2nd place;
> > ...
> > n: The diagonal differs from the n-th entry in the n-th place;
>
> > It seems straightforward to induce that, at the limit, the difference
> > between the diagonal and the limit entry tends to zero.
>
> Wonderful. I wonder how many people will rush in to the rescue, asking
> "What limit entry?" or exclaiming most ferociously "There is no limit
> entry!". Surely you can anticipate this response just as well as the
> next man. The obvious question, then, is why bother? Why not come up
> with some novel rubbish?
Because I cannot get what is wrong with it.
The "limit" is of course induction.
-LV
> --
> Aatu Koskensilta (aatu.koskensi...@uta.fi)
ju...@diegidio.name
> On Aug 8, 9:39 am, ju...@diegidio.name wrote:
>
> > Below again a simple argument to show that from the very same
> > construction we could induce the exact opposite result:
>
> > 1: The diagonal differs from the 1st entry in the 1st place;
> > 2: The diagonal differs from the 2nd entry in the 2nd place;
> > ...
> > n: The diagonal differs from the n-th entry in the n-th place;
>
> > It seems straightforward to induce that, at the limit, the difference
> > between the diagonal and the limit entry tends to zero.
>
> WHAT limit? You need to DEFINE "limit" in terms of some topology,
> metric, ordering, or whatever. We don't just use the word "limit"
> without the context of the EXACT sense of a limit as it has been
> DEFINED.
It's induction over the infinite ordered list (we have discussed this
for hundred posts and you still ask the same question).
> Moreover, the anti-diagonal differes from every entry in the list.
> That's all that is required to show that the anti-diagonal is not on
> the list.
There is no reason for your "moreover". Moreover, the difference in
question tends to zero, so that the anti-diagonal happens to
correspond to the limit entry: you have (yet) not addressed that.
-LV
> MoeBlee
MoeBlee
> The "limit" is of course induction.
Please state EXACTLY what induction schema you have in mind.
MoeBlee
Aatu Koskensilta
> The "limit" is of course induction.
Alas, that makes no sense whatsoever. But I see someone has already
rushed in to the rescue, asking "WHAT limit?" so you're in safe
hands. I'll make a hasty retreat myself.
--
Aatu Koskensilta (aatu.kos...@uta.fi)
ju...@diegidio.name
> ju...@diegidio.name writes:
> > The "limit" is of course induction.
>
> Alas, that makes no sense whatsoever.
Doesn't it?
Thanks for the moral support...
-LV
> But I see someone has already
> rushed in to the rescue, asking "WHAT limit?" so you're in safe
> hands. I'll make a hasty retreat myself.
>
> --
> Aatu Koskensilta (aatu.koskensi...@uta.fi)
Balthasar
wrote:
To make a long story short: we are not interested in the "limit entry"
(whatever that may be), but in the fact that the diagonal differs from
each and any entry in the list.
Of course there's still a loophole mentioned by WM, see signature below.
B.
--
"For every line of Cantor's list it is true that this line does not
contain the diagonal number. Nevertheless the diagonal number may
be in the infinite list." (WM, sci.logic)
Balthasar
<aatu.kos...@uta.fi> wrote:
>>
>> Below again a simple argument to show that from the very same
>> construction we could induce the exact opposite result:
>>
>> 1: The diagonal differs from the 1st entry in the 1st place;
>> 2: The diagonal differs from the 2nd entry in the 2nd place;
>> ...
>> n: The diagonal differs from the n-th entry in the n-th place;
>>
>> It seems straightforward to induce that, at the limit, the difference
>> between the diagonal and the limit entry tends to zero.
>>
> Wonderful. I wonder how many people will rush in to the rescue, asking
> "What limit entry?" or exclaiming most ferociously "There is no limit
> entry!"
>
Right. I just wrote:
"To make a long story short: we are not interested in the "limit entry"
(whatever that may be), but in the fact that the diagonal differs from
each and any entry in the list."
Not though that there's still a loophole mentioned by WM! (See signature
below.)
ju...@diegidio.name
> On Fri, 8 Aug 2008 09:44:09 -0700 (PDT), MoeBlee <jazzm...@hotmail.com>
> wrote:
>
> >> Below again a simple argument to show that from the very same
> >> construction we could induce the exact opposite result:
>
> >> 1: The diagonal differs from the 1st entry in the 1st place;
> >> 2: The diagonal differs from the 2nd entry in the 2nd place;
> >> ...
> >> n: The diagonal differs from the n-th entry in the n-th place;
>
> >> It seems straightforward to induce that, at the limit, the difference
> >> between the diagonal and the limit entry tends to zero.
>
> > WHAT limit? You need to DEFINE "limit" in terms of some topology,
> > metric, ordering, or whatever. We don't just use the word "limit"
> > without the context of the EXACT sense of a limit as it has been
> > DEFINED.
>
> > Moreover, the anti-diagonal differes from every entry in the list.
> > That's all that is required to show that the anti-diagonal is not on
> > the list.
>
> To make a long story short: we are not interested in the "limit entry"
> (whatever that may be), but in the fact that the diagonal differs from
> each and any entry in the list.
Interested or not, you cannot just dismiss it. The "limit" entry makes
just as much sense as the above (or the below) "[for] every entry in
the list". Is the list "infinite" or is it not? I am saying, yours is
not a valid objection.
-LV
MoeBlee
> On 8 Aug, 17:53, Aatu Koskensilta <aatu.koskensi...@uta.fi> wrote:
>
> > ju...@diegidio.name writes:
> > > The "limit" is of course induction.
>
> > Alas, that makes no sense whatsoever.
>
> Doesn't it?
No, it doesn't. It's been explained to you over and over (and then you
complain about repetition), but it's clear by now that you just don't
want to understand the mathematical explanations as it suits you
better to posture.
MoeBlee
Balthasar
wrote:
>
> ... but it's clear by now that you just don't want to understand the
> mathematical explanations as it suits you better to posture.
>
Sure? I'd suppose to try harder, Moe! Don't give up so fast! :-)
MoeBlee
> > To make a long story short: we are not interested in the "limit entry"
> > (whatever that may be), but in the fact that the diagonal differs from
> > each and any entry in the list.
>
> Interested or not, you cannot just dismiss it. The "limit" entry makes
> just as much sense as the above (or the below) "[for] every entry in
> the list". Is the list "infinite" or is it not? I am saying, yours is
> not a valid objection.
Whether the list is infinite or NOT, the anti-diagonal is not on the
list. Otherwise, you are free to mention EXACTLY what premises in the
proof or what rule of logic used you disagree with. Then we could at
least say, "Yes, given that you don't accept those premises and rules
of logic, you don't have to accept the theorem that is proved from
them. Now, what premises and logic DO you accept for the purpose of
deriving mathematical conclusions?" See, that would be productive. But
we can't get there if all you do is use UNDEFINED hocus pocus about
"limit induction", and amphiboly in your symbolisms, along with
recriminations about what dishonest idiots mathematicians are.
MoeBlee
Balthasar
wrote:
>>>
>>> To make a long story short: we are not interested in the "limit entry"
>>> (whatever that may be), but in the fact that the diagonal differs from
>>> each and any entry in the list.
>>>
>> Interested or not, you cannot just dismiss it. [Crank]
>>
Well, actually there's nothing to "dismiss".
Balthasar
> suppose
"propose", of course.
B.
Balthasar
wrote:
>
> Whether the list is infinite or NOT, the anti-diagonal is not on the
> list.
>
Wait a second, Moe! This is not necessarily the case. Actually:
"For every line of Cantor's list it is true that this line does not
contain the diagonal number. Nevertheless the diagonal number may
be in the infinite list." (WM)
Try to get that straight!
B.
tc...@lsa.umich.edu
Balthasar <nomail@invalid> wrote:
>Not though that there's still a loophole mentioned by WM! (See signature
>below.)
>"For every line of Cantor's list it is true that this line does not
> contain the diagonal number. Nevertheless the diagonal number may
> be in the infinite list." (WM, sci.logic)
This is an amusing one. So a number may be "in" a list of numbers without
being in any *line* of the list? The whole is greater than the sum of its
parts, or something like that? A list can contain things that don't appear
in any line of the list? But then where exactly are these things located?
And how can you tell whether some non-line-item is *in* the list rather than
*after* the list, or above the list, or through the list, or between the
list, or just hanging around the neighborhood for the joy of rubbernecking?
--
Tim Chow tchow-at-alum-dot-mit-dot-edu
The range of our projectiles---even ... the artillery---however great, will
never exceed four of those miles of which as many thousand separate us from
the center of the earth. ---Galileo, Dialogues Concerning Two New Sciences
Alan Smaill
> In article <8qvo941tgkic4areb...@4ax.com>,
> Balthasar <nomail@invalid> wrote:
> >Not though that there's still a loophole mentioned by WM! (See signature
> >below.)
> >--
> >"For every line of Cantor's list it is true that this line does not
> > contain the diagonal number. Nevertheless the diagonal number may
> > be in the infinite list." (WM, sci.logic)
>
> This is an amusing one. So a number may be "in" a list of numbers without
> being in any *line* of the list? The whole is greater than the sum of its
> parts, or something like that? A list can contain things that don't appear
> in any line of the list? But then where exactly are these things located?
> And how can you tell whether some non-line-item is *in* the list rather than
> *after* the list, or above the list, or through the list, or between the
> list, or just hanging around the neighborhood for the joy of rubbernecking?
I'm told that intelligent people "read between the lines" ...
> --
> Tim Chow tchow-at-alum-dot-mit-dot-edu
> The range of our projectiles---even ... the artillery---however great, will
> never exceed four of those miles of which as many thousand separate us from
> the center of the earth. ---Galileo, Dialogues Concerning Two New Sciences
--
Alan Smaill
Balthasar
>>
>> Note though that there's still a loophole mentioned by WM!
>>
>> "For every line of Cantor's list it is true that this line does not
>> contain the diagonal number. Nevertheless the diagonal number may
>> be in the infinite list." (WM, sci.logic)
>>
> This is an amusing one. So a number may be "in" a list of numbers without
> being in any *line* of the list? The whole is greater than the sum of its
> parts, or something like that? A list can contain things that don't appear
> in any line of the list? But then where exactly are these things located?
> And how can you tell whether some non-line-item is *in* the list rather than
> *after* the list, or above the list, or through the list, or between the
> list, or just hanging around the neighborhood for the joy of rubbernecking?
>
*lol*
Well, WM is certainly an artist, no question. :-)
B.
cplx...@gmail.com
I have no comment on the argument itself; I'm sure it's incorrect, I
just haven't read it in detail.
I just wanted to say that while I haven't been on this forum very
long, this is by far the most vicious discussion of theoretical
computer science I've ever seen!
I'm glad no one reacts that strongly to the incorrect arguments I've
posted....
-Phil
ju...@diegidio.name
> On Aug 8, 10:23 am, ju...@diegidio.name wrote:
>
> > > To make a long story short: we are not interested in the "limit entry"
> > > (whatever that may be), but in the fact that the diagonal differs from
> > > each and any entry in the list.
>
> > Interested or not, you cannot just dismiss it. The "limit" entry makes
> > just as much sense as the above (or the below) "[for] every entry in
> > the list". Is the list "infinite" or is it not? I am saying, yours is
> > not a valid objection.
>
> Whether the list is infinite or NOT, the anti-diagonal is not on the
> list.
You keep saying so as if it were the starting point, while that's the
result to get. The first problem is indeed in your general way of
argumentation.
> Otherwise, you are free to mention EXACTLY what premises in the
> proof or what rule of logic used you disagree with.
The diagonal argument is broken in its essence, and this comes before
your axioms, another problem of yours. But I am not trying to disprove
*you*. Here I have provided the simpliest of the arguments based on
the naturals and induction, to build the very same list and the very
same diagonal as Cantor's, with quite opposite results: and they are
very natural results. You have not been able to provide a meaningful
objection that is one. Somewhere else, though, you have finally
admitted that there exists such a thing as constructive theories. So
all the fuzz for nothing?
> Then we could at
> least say, "Yes, given that you don't accept those premises and rules
> of logic, you don't have to accept the theorem that is proved from
> them. Now, what premises and logic DO you accept for the purpose of
> deriving mathematical conclusions?" See, that would be productive. But
> we can't get there if all you do is use UNDEFINED hocus pocus about
> "limit induction", and amphiboly in your symbolisms, along with
> recriminations about what dishonest idiots mathematicians are.
Let's be serious. I have given the simpliest of the arguments. Can you
spot any significant flaw? If not, then I guess it's really the time
to revisit Cantor's... and then I can see what is the fuzz for.
How do you dismiss constructive theories? I'd be very interested in
learning what eventually there is to lose.
-LV
> MoeBlee
MoeBlee
> On 8 Aug, 19:10, MoeBlee <jazzm...@hotmail.com> wrote:
>
> > On Aug 8, 10:23 am, ju...@diegidio.name wrote:
>
> > > > To make a long story short: we are not interested in the "limit entry"
> > > > (whatever that may be), but in the fact that the diagonal differs from
> > > > each and any entry in the list.
>
> > > Interested or not, you cannot just dismiss it. The "limit" entry makes
> > > just as much sense as the above (or the below) "[for] every entry in
> > > the list". Is the list "infinite" or is it not? I am saying, yours is
> > > not a valid objection.
>
> > Whether the list is infinite or NOT, the anti-diagonal is not on the
> > list.
>
> You keep saying so as if it were the starting point, while that's the
> result to get. The first problem is indeed in your general way of
> argumentation.
We state exactly the premises and rules of inference. I've been that
saying over and over, because YOU are not responsive to the poing
(instead you just complain about the repetition of my answer while you
don't ADDRESS my answer).
One more time:
Theorems of Z set theory are from an explicit set of premises (axioms)
and an explicit logic (the inference rules). Yes, if you fault the
axioms and/or inference rules, then you don't have to accept the
theorems. But that is a separate question from what is or is not a
theorem from whatever given set of axioms and inference rules.
PLEASE LISTEN THIS TIME:
You and I have NO DISAGREEMENT that if you fault the axioms and rules,
then you don't have to accept the conclusions. BUT, then an
INTELLEGENT discussion starts with you saying just which axioms and
rules you don't accept, and then perhaps to tell us what axioms and
rules that you instead propose to derive theorems of mathematics.
> > Otherwise, you are free to mention EXACTLY what premises in the
> > proof or what rule of logic used you disagree with.
>
> The diagonal argument is broken in its essence, and this comes before
> your axioms, another problem of yours.
You see. You didn't answer the question. You won't say what axioms or
rules you disagree with. Okay, fine, so we just leave it at that.
Since the axioms and rules entail a conclusion you disagree with,
there is at least one, though unspecified axiom or rule, that you
don't accept.
> But I am not trying to disprove
> *you*. Here I have provided the simpliest of the arguments based on
> the naturals and induction, to build the very same list and the very
> same diagonal as Cantor's, with quite opposite results:
No, you have not. Please, we keep telling you, but you keep evading,
that your "argument" doesn't work because it uses an UNDEFINED notion
of a 'limit'. We DEFINE the use of limits EXACTLY. But your just
SAYING "in the limit case" is not a mathematical argument. It is using
mathematical sounding terminology, but without defintion of the sense
of a limit that would apply.
> and they are
> very natural results. You have not been able to provide a meaningful
> objection that is one.
Please, it is INSULTING that you say that when people have taken the
time to SPECIFICALLY articulate the objections to your "argument".
> Somewhere else, though, you have finally
> admitted that there exists such a thing as constructive theories. So
> all the fuzz for nothing?
Because, as far as I know, such constructive mathematics does not work
by just going around using mathematical sounding terminology such as
vacuously spouting about some UNDEFINED "limit case".
> > Then we could at
> > least say, "Yes, given that you don't accept those premises and rules
> > of logic, you don't have to accept the theorem that is proved from
> > them. Now, what premises and logic DO you accept for the purpose of
> > deriving mathematical conclusions?" See, that would be productive. But
> > we can't get there if all you do is use UNDEFINED hocus pocus about
> > "limit induction", and amphiboly in your symbolisms, along with
> > recriminations about what dishonest idiots mathematicians are.
>
> Let's be serious. I have given the simpliest of the arguments. Can you
> spot any significant flaw?
So you will never actually READ the posts given to you, I guess. We've
said over and over and over that the flaw is using an UNDEFINED notion
of 'limit'.
> If not, then I guess it's really the time
> to revisit Cantor's... and then I can see what is the fuzz for.
>
> How do you dismiss constructive theories?
I DON'T dismiss well presented constructive theories. And I very much
DO appreciate the importance of constructivism in mathematics. What I
do dismiss is an argument that just uses mathematical sounding
terminology without properly defining it.
> I'd be very interested in
> learning what eventually there is to lose.
Constructivism has drawbacks and advantages, while classical
mathematics also has its drawbacks and advantages. That is a rich area
for discussion, but it requires at least two things you are not
willing to bring: (1) An understanding of the basics of the subject,
and (2) a willingness to rise from mindless recriminations about
mathematicians and instead pay attention at least long enough so that
you understand what various mathematicians - constructivst and non-
constructivist - are actually saying.
MoeBlee
MoeBlee
> constructive theories?
P.S. It is decidedy NOT constructivist to assert the existence of a
"limit" without CONSTRUCTING it (and just saying "the limit case" is
decidedly not a construction), let alone, not even defining what
possible sense you might mean by a "limit" in such a context.
MoeBlee
ju...@diegidio.name
So you cannot add anything significant, you just reiterate your
insults to my intelligence. Never mind, it was anyway very
"instructive".
Now, from Cantor to Goedel...
See you soon.
-LV
> MoeBlee
Balthasar
wrote:
>
> On Aug 8, 3:09 pm, ju...@diegidio.name wrote:
>>
>> [...] Here I have provided the simpliest of the arguments based on
>> the naturals and induction, to build the very same list and the very
>> same diagonal as Cantor's, with quite opposite results: [...].
>>
Well, what you [Crank] have provided is just a truckload full of crap.
>
> No, you have not. Please, we keep telling you, but you keep evading,
> that your "argument" doesn't work because it uses an UNDEFINED notion
> of a 'limit'. We DEFINE the use of limits EXACTLY. But your just
> SAYING "in the limit case" is not a mathematical argument. It is using
> mathematical sounding terminology, but without definition of the sense
> of a limit that would apply.
>
Actually, he's just using words without any significance whatsoever.
Maybe it's really another personification of JJ?
>>
>> You have not been able to provide a meaningful objection [...].
>>
You see: a crank or troll. (JJ again?)
>>
>> [...] I have given the simpliest of the arguments. Can you spot any
>> significant flaw?
>>
*sigh*
Daryl McCullough
>Below again a simple argument to show that from the very same
>construction we could induce the exact opposite result:
>
>1: The diagonal differs from the 1st entry in the 1st place;
>2: The diagonal differs from the 2nd entry in the 2nd place;
>n: The diagonal differs from the n-th entry in the n-th place;
>
>It seems straightforward to induce that, at the limit, the difference
>between the diagonal and the limit entry tends to zero.
That's completely false. Let's try an example: Suppose
your list is the following:
0.[1]000000....
0.0[1]00000....
0.00[1]0000...
0.000[1]000...
etc. (Note, I put a [] around each digit of the diagonal)
Now, to diagonalize, we add 1 to each diagonal element. This
gives the number
0.22222...
That number does not appear on the list, and it is certainly
not equal to the limit of the numbers on the sequence.
When someone says "The diagonal differs from the 2nd entry in the
2nd place" they don't mean that that is the *only* place they
differ. The diagonal may differ from the 2nd entry in many places,
but it differs in at least the 2nd place.
So, no, your simple argument doesn't show the opposite result.
--
Daryl McCullough
Ithaca, NY
ju...@diegidio.name
> On Aug 8, 3:09 pm, ju...@diegidio.name wrote:
> > On 8 Aug, 19:10, MoeBlee <jazzm...@hotmail.com> wrote:
> > > On Aug 8, 10:23 am, ju...@diegidio.name wrote:
>
> > > Otherwise, you are free to mention EXACTLY what premises in the
> > > proof or what rule of logic used you disagree with.
>
> > The diagonal argument is broken in its essence, and this comes before
> > your axioms, another problem of yours.
>
> You see. You didn't answer the question. You won't say what axioms or
> rules you disagree with. Okay, fine, so we just leave it at that.
> Since the axioms and rules entail a conclusion you disagree with,
> there is at least one, though unspecified axiom or rule, that you
> don't accept.
Reread: you see? You just don't get it, it's out of your universe of
understanding.
BTW, now you have made a point of denying anything I might be willing
to say, here and elsewhere. I have already given you a formal
definition of my construction in a another thread, along with any of
the uncountable and meanigless clarifications I was asked for, about
all the details you liked to be told about. Result: just reitereted
denial and personal insults. Balthasar is now your friend. And I am
finished with you both.
-LV
Daryl McCullough
>There is no reason for your "moreover". Moreover, the difference in
>question tends to zero, so that the anti-diagonal happens to
>correspond to the limit entry: you have (yet) not addressed that.
No, the anti-diagonal does *not* equal the "limit entry". Why would
you think that? The differences *don't* tend to zero. Look at an
actual example:
0.10000...
0.01000...
0.001000...
0.0001000...
etc.
The anti-diagonal is 0.2222...
That doesn't appear on the list, and it also isn't equal to
the limit of the list.
ju...@diegidio.name
Good one, at least looks like mathematics.
Although your construction is rather itself "broken": not less good
for my argument then it might be for Cantor's.
Shall I point you to some article on the diagonal argument? For the
sake of the discussion.
-LV
Balthasar
wrote:
>
> P.S. It is decidedly NOT constructivist to assert the existence of a
> "limit" without CONSTRUCTING it (and just saying "the limit case" is
> decidedly not a construction), let alone, not even defining what
> possible sense you might mean by a "limit" in such a context.
>
And, btw., even a constructivist/intuitionist would agree that a number
is not in a certain set (or list) if it differs from ALL (i.e. each and
every) elements (or entries) in the set (or list). ;-)
Proof (in NJ + identity):
1 (1) Ax(x e A -> ~(a = x)) A
2 (2) a e A A
1 (3) a e A -> ~(a = a) 1 UE
1,2 (4) ~(a = a) 2,3 ->E
(5) a = a =I
1,2 (6) _|_ 4,5 ~E
1 (7) ~(a e A) 2,6 ~I
Hence:
Ax(x e A -> a =/= x) |- a !e A.
This does even hold in ML (minimal logic) + identity. But obviously id
does not hold in /crank logic/.
Daryl McCullough
>So you cannot add anything significant, you just reiterate your
>insults to my intelligence. Never mind, it was anyway very
>"instructive".
Look, Cantor made a precise claim, and he gave a rigorous proof
of that claim. You made a fuzzy claim (one that didn't actually
contradict what Cantor said), and you gave a false proof of that
fuzzy claim. I guess it's not nice to insult your intelligence,
but you clearly don't know what you are talking about.
MoeBlee
How insulting! You just included the QUOTES of my SUBSTANTIVE comments
and then just SKIPPED all of it to say that all I did was insult your
intelligence. AND, for that matter, in my remarks about you
personally, I NEVER commented on your INTELLIGENCE.
Look, the substantive comments of mine are right there in what you
yourself quoted. At this point, after your skipping thsee points yet
again, and after my nearly BEGGING you to address the substantive
points, I do have to think that indeed you are just trolling for
reactions here and are not interested in the actual mathematics or
even philosophical aspects of this subject.
MoeBlee
ju...@diegidio.name
> On Fri, 8 Aug 2008 15:49:27 -0700 (PDT), MoeBlee <jazzm...@hotmail.com>
> wrote:
>
>
>
> > P.S. It is decidedly NOT constructivist to assert the existence of a
> > "limit" without CONSTRUCTING it (and just saying "the limit case" is
> > decidedly not a construction), let alone, not even defining what
> > possible sense you might mean by a "limit" in such a context.
>
> And, btw., even a constructivist/intuitionist would agree that a number
> is not in a certain set (or list) if it differs from ALL (i.e. each and
> every) elements (or entries) in the set (or list). ;-)
Paralogism. As usual you are assuming what there is to prove, that's
what anyone knowing about logic would say. And in my argument I do NOT
even assume anything like that, I actually conclude the opposite.
Clueless as you can be, can you be sooo clueless?
-LV
MoeBlee
> On 8 Aug, 23:41, MoeBlee <jazzm...@hotmail.com> wrote:
>
> > On Aug 8, 3:09 pm, ju...@diegidio.name wrote:
> > > On 8 Aug, 19:10, MoeBlee <jazzm...@hotmail.com> wrote:
> > > > On Aug 8, 10:23 am, ju...@diegidio.name wrote:
>
> > > > Otherwise, you are free to mention EXACTLY what premises in the
> > > > proof or what rule of logic used you disagree with.
>
> > > The diagonal argument is broken in its essence, and this comes before
> > > your axioms, another problem of yours.
>
> > You see. You didn't answer the question. You won't say what axioms or
> > rules you disagree with. Okay, fine, so we just leave it at that.
> > Since the axioms and rules entail a conclusion you disagree with,
> > there is at least one, though unspecified axiom or rule, that you
> > don't accept.
>
> Reread: you see? You just don't get it, it's out of your universe of
> understanding.
>
> BTW, now you have made a point of denying anything I might be willing
> to say, here and elsewhere.
No, I have not. I disagree with a number of things you post. I don't
have a point to find you wrong on every single thing you've ever
said, let alone MIGHT say.
> I have already given you a formal
> definition of my construction in a another thread,
Please state exactly what you are referring to. Please show me your
definition of 'limit' in the context of this discussion.
> along with any of
> the uncountable and meanigless clarifications I was asked for, about
> all the details you liked to be told about.
Please tell me, for example, where you gave any kind of adequate
response to it having been pointed out to you that you conflated two
different definitions of 'P' in that other thread.
> Result: just reitereted
> denial and personal insults.
No, that is a lie. Not JUST personal insults. Rather, substantive
response, which you keep skipping, plus personal remarks that are not
kind but need to be said, since indeed no discussion with you can make
progress while you are unwilling to learn the basics of the subject
and listen instead of investing yourself in childish recriminations
about how "iditotic" mathematicans are.
> Balthasar is now your friend. And I am
> finished with you both.
How childish. What are posting from the fifth grade class computer
room? "Bobby is not my friend anymore! Bobby and Tommy are friends,
but I'm not their friend!"
MoeBlee
MoeBlee
> On 9 Aug, 00:16, Balthasar <nomail@invalid> wrote:
>
> > On Fri, 8 Aug 2008 15:49:27 -0700 (PDT), MoeBlee <jazzm...@hotmail.com>
> > wrote:
>
> > > P.S. It is decidedly NOT constructivist to assert the existence of a
> > > "limit" without CONSTRUCTING it (and just saying "the limit case" is
> > > decidedly not a construction), let alone, not even defining what
> > > possible sense you might mean by a "limit" in such a context.
>
> > And, btw., even a constructivist/intuitionist would agree that a number
> > is not in a certain set (or list) if it differs from ALL (i.e. each and
> > every) elements (or entries) in the set (or list). ;-)
>
> Paralogism. As usual you are assuming what there is to prove, that's
> what anyone knowing about logic would say. And in my argument I do NOT
> even assume anything like that, I actually conclude the opposite.
> Clueless as you can be, can you be sooo clueless?
Okay, go ahead and keep thinking that...
MoeBlee
Balthasar
McCullough) wrote:
>
> No, the anti-diagonal does *not* equal the "limit entry".
>
It doesn't? So YOU know how the /limit entry/ is defined? Well, at least
*I* don't know how it is defined, hence *I* can't claim that - since I
don't have a proof for this assertion. [...]
>
> Why would you think that?
>
Because he's a troll or a crank?
>
> The differences *don't* tend to zero.
>
Well, here I have to disagree. Actually, they do - in a certain sense.
(Of course: so what?!)
I mean, with the construction of the anti-diagonal you ensure that the
anti-diagonal differs from the n-th entry in the list _at least_ in the
n-th digit. Hence this "guaranteed difference" tends to zero (as n tends
to oo). But so what? We all (non-cranks that is) know that even though
the difference between
1/n and 0
tends to zero (as n tends to oo), 0 still does not occur in the sequence
(1/n). With other words: ~En e IN: 0 = 1/n. (@Crank: 0 is not an entry
in the sequence (1/n).)
ju...@diegidio.name
I will.
You have of course snippned it, but Balthasar had provided it in
formulas.
You lose, badly now.
And I am officially the new "king of the post-cantorians", by your own
appointment.
Cooool.
-LV
>
> MoeBlee
ju...@diegidio.name
And you clearly can only reiterate you spell.
Have fun.
-LV
MoeBlee
> On 9 Aug, 00:31, MoeBlee <jazzm...@hotmail.com> wrote:
> > On Aug 8, 4:23 pm, ju...@diegidio.name wrote:
>
> > > On 9 Aug, 00:16, Balthasar <nomail@invalid> wrote:
>
> > > > On Fri, 8 Aug 2008 15:49:27 -0700 (PDT), MoeBlee <jazzm...@hotmail.com>
> > > > wrote:
>
> > > > > P.S. It is decidedly NOT constructivist to assert the existence of a
> > > > > "limit" without CONSTRUCTING it (and just saying "the limit case" is
> > > > > decidedly not a construction), let alone, not even defining what
> > > > > possible sense you might mean by a "limit" in such a context.
>
> > > > And, btw., even a constructivist/intuitionist would agree that a number
> > > > is not in a certain set (or list) if it differs from ALL (i.e. each and
> > > > every) elements (or entries) in the set (or list). ;-)
>
> > > Paralogism. As usual you are assuming what there is to prove, that's
> > > what anyone knowing about logic would say. And in my argument I do NOT
> > > even assume anything like that, I actually conclude the opposite.
> > > Clueless as you can be, can you be sooo clueless?
>
> > Okay, go ahead and keep thinking that...
>
> I will.
>
> You have of course snippned it, but Balthasar had provided it in
> formulas.
I have no idea what you think I snipped in my last post.
> You lose, badly now.
>
> And I am officially the new "king of the post-cantorians", by your own
> appointment.
>
> Cooool.
Sweet indeed.
MoeBlee
Balthasar
wrote:
>>
>> Balthasar is now your friend. And I am finished with you both.
>>
Oh, how sad! :-(
I'm deeply hurt!
Balthasar
wrote:
>>
>> You lose, badly now.
>>
Drunk, drugs?
>>
>> And I am officially the new "king of the post-cantorians", by your own
>> appointment.
>>
>> Cooool.
>>
> Sweet indeed.
>
Yeah, very cool, indeed! :-)
Balthasar
>>
>> The differences *don't* tend to zero.
>>
> Well, here I have to disagree. [etc.]
>
Well, actually Cantor himself did not consider /real numbers/ (and/or
their decimal expansion) in the original proof (where he introduced the
diagonal argument), hence all this (cranky) talking about "limits" and
"limit entry" and whatnot could not arise.
Balthasar
>>>
>>> The differences *don't* tend to zero.
>>>
>> Well, here I have to disagree. [etc.]
>>
> Well, actually Cantor himself did not consider /real numbers/ (and/or
> their decimal expansion) in the original proof (where he introduced the
> diagonal argument), hence all this (cranky) talking about "limits" and
> "limit entry" and whatnot could not arise.
>
So, for the sake of the argument, let's not consider a list of real
numbers (and/or of their decimal expansions), but a list of infinite
sequences of the two symbols /a/ and /b/. Let's just consider one such
list (to point out the construction of the anti-diagonal):
(1) [a] a b b a a b a ...
(2) a [a] a a a a b b ...
(3) b b [b] b a a b a ...
(4) a b b [b] a b b b ...
: ...
(Note, I put a [] around each symbol of the diagonal.)
In this case we get the anti-diagonal by replacing /a/ with /b/ and vice
versa. Hence we get the sequence
b b a a ...
Now this sequence differs from any sequence in the list by at least one
symbol. (Exercise!)
With other words, it differs from each and any sequence in the list,
i.e. it's not in the list (at least following standard logic).
Chris Menzel
<ju...@diegidio.name> said:
> On 8 Aug, 18:12, Balthasar <nomail@invalid> wrote:
>> On Fri, 8 Aug 2008 09:44:09 -0700 (PDT), MoeBlee
>> <jazzm...@hotmail.com> wrote:
>>
>> >> Below again a simple argument to show that from the very same
>> >> construction we could induce the exact opposite result:
>>
>> >> 1: The diagonal differs from the 1st entry in the 1st place; 2:
>> >> The diagonal differs from the n-th entry in the n-th place;
>>
>> >> It seems straightforward to induce that, at the limit, the
>> >> difference between the diagonal and the limit entry tends to zero.
>>
>> > metric, ordering, or whatever. We don't just use the word "limit"
>> > without the context of the EXACT sense of a limit as it has been
>> > DEFINED.
>>
>> > Moreover, the anti-diagonal differes from every entry in the list.
>> > That's all that is required to show that the anti-diagonal is not
>> > on the list.
>>
>> To make a long story short: we are not interested in the "limit
>> entry" (whatever that may be), but in the fact that the diagonal
>
> Interested or not, you cannot just dismiss it. The "limit" entry makes
> just as much sense as the above (or the below) "[for] every entry in
> the list". Is the list "infinite" or is it not? I am saying, yours is
Let me guess: You also think that an infinite set of numbers must
contain an infinitely large number.
Barb Knox
Chris Menzel <cme...@remove-this.tamu.edu> wrote:
That's a good bet. I guess it's time to repost this:
I am the very model of a modern non-Cantorian,
With insights mathematical as good as any saurian.
I rattle the Establishment's foundations with prodigious ease,
And populate the counting numbers with some new infinities.
I've never studied axioms of sets all theoretical,
But that's just ted'ous detail, whereas MY thoughts are heretical
And cause the so-called experts rather quickly to exasperate,
While I sit back and mentally continue just to ....
--
---------------------------
| 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 |
-----------------------------
Balthasar
<cme...@remove-this.tamu.edu> wrote:
>>>>>
>>>>> Below again a simple argument to show that from the very same
>>>>> construction we could induce the exact opposite result:
>>>>>
>>>>> 1: The diagonal differs from the 1st entry in the 1st place;
>>>>> 2: The diagonal differs from the 2nd entry in the 2nd place;
>>>>> :
>>>>> n: The diagonal differs from the n-th entry in the n-th place;
>>>>> :
>>>>>
>>>>> It seems straightforward to induce that, at the limit, the
>>>>> difference between the diagonal and the limit entry tends to zero.
>>>>>
>>>>> (Crank)
>>>>>
>>>> WHAT limit? You need to DEFINE "limit" in terms of some topology,
>>>> metric, ordering, or whatever. We don't just use the word "limit"
>>>> without the context of the EXACT sense of a limit as it has been
>>>> DEFINED.
>>>>
One might also ask what "limit entry" are you talking about - limit of
what sequence?
>>>>
>>>> Moreover, the anti-diagonal differes from every entry in the list.
>>>> That's all that is required to show that the anti-diagonal is not
>>>> on the list.
>>>>
>>>> (MoeBlee)
>>>>
>>> To make a long story short: we are not interested in the "limit
>>> entry" (whatever that may be), but in the fact that the [anti-]
>>> diagonal differs from each and any entry in the list.
>>>
>>> (Balthasar)
>>>
>> Interested or not, you cannot just dismiss it. The "limit" entry makes
>> just as much sense as the above (or the below) "[for] every entry in
>> the list". Is the list "infinite" or is it not? I am saying, yours is
>>
>> (Crank)
>>
> Let me guess: You also think that an infinite set of [natural] numbers
> must contain an infinitely large number.
>
> (Chris Menzel)
>
Certainly an educated guess. :-)
ju...@diegidio.name
Easy guess. That number is called infinity, or otherwise "omega" ('w',
or even 'oo').
With my construction I don't get higher order infinite ordinals, but
instead I get that 'oo' is representable, as is 'oo-1' and so on. That
is, we can enumerate from zero as well as enumerate back from
infinity. And I mean we can enumerate forwards or backwards the
infinite list of the computable reals, say in [0, 1], where 1 is the
usual diagonal at 0 and viceversa, 0 is the inverse diagonal at 1.
Actually, given an ordering rule over the list, we can enumerate
forwards or backwards at some specific points, but I'll leave the
details out.
Side result is again that the list of the computable reals is in
bijection with the set of the naturals. And, given that its numerosity
is in the order of n! (all the permutations of the digits) we have an
upper bound for the powerset, whose numerosity is in the order of 2^n.
-LV
Barb Knox
<371eb05c-831d-435d...@e39g2000hsf.googlegroups.com>,
ju...@diegidio.name wrote:
So then do you reject mathematical induction? If not, then one can
easily prove that oo < oo, which does not look healthy.
(And there are many other similar difficulties with attempting to add a
limit point to N.)
[snip]
Balthasar
wrote:
>
> Moreover, the anti-diagonal differs from every entry in the list.
> That's all that is required to show that the anti-diagonal is not
> on [or in] the list.
>
In the following I'll give a formal proof for this (the latter) claim.
First some definitions. The /list/ L will be represented as an infinite
sequence: L = (l_n). The l_ns are the /entries/ in the list L = (l_n).
Accordingly we define for any list L = (l_n):
x in L =df En(n e N & x = l_n).
"x is in the list L."
x not in L =df ~(x in L)
"x is not in the list L."
Now we have the assumption:
L = (l_n) & An(n e N -> ~(d = l_n)).
"The anti-diagonal d differs from every entry in the list L."
We want to prove:
d not in L.
"The anti-diagonal d is not in the list L."
Proof (in NJ + identity):
1 (1) L = (l_n) & An(n e N -> ~(d = l_n)) A
2 (2) d in L A
1 (3) L = (l_n) 1 &E
1,2 (4) d in (l_n) 2,3 =E
1,2 (5) En(n e N & d = l_n) 4 Def. "in"
6 (6) a e N & d = l_a A
6 (7) a e N 6 &E
6 (8) d = l_a 6 &E
1 (9) An(n e N -> ~(d = l_n)) 1 &E
1 (10) a e N -> ~(d = l_a) 9 UE
1,6 (11) ~(d = l_a) 7,10 ->E
1,6 (12) _|_ 8,11 ~E
1,2 (13) _|_ 5,6,12 EE
1 (14) ~(d in L) 2,13 ~I
1 (15) d not in L 14 Def. "not in"
Hence we have shown:
L = (l_n) & An(n e N -> ~(d = l_n)) |- d not in L.
qed.
The proof will even go trough in minimal logic + identity.
Though it will fail in some systems of /crank logic/:
"For every line of Cantor's list it is true that this line does not
contain the diagonal number. Nevertheless the diagonal number may
be in the infinite list." (WM)
B.
ju...@diegidio.name
> In article
> <371eb05c-831d-435d-8dea-966887ca4...@e39g2000hsf.googlegroups.com>,
Absolutely not. I rather "double it". Informally speaking, I have two
end-points, zero and its mirror, infinity. Maybe keep in mind there is
no uncomputables in this realm.
> If not, then one can
> easily prove that oo < oo, which does not look healthy.
I'd be interested in seeing it, thanks. Mine is still mostly an
exploration.
-LV
> (And there are many other similar difficulties with attempting to add a
> limit point to N.)
>
> [snip]
> --
> ---------------------------
> | 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 |
> ------------------------------
ju...@diegidio.name
> On Fri, 8 Aug 2008 09:44:09 -0700 (PDT), MoeBlee <jazzm...@hotmail.com>
> wrote:
>
> > Moreover, the anti-diagonal differs from every entry in the list.
> > That's all that is required to show that the anti-diagonal is not
> > on [or in] the list.
>
> In the following I'll give a formal proof for this (the latter) claim.
>
> First some definitions. The /list/ L will be represented as an infinite
> sequence: L = (l_n). The l_ns are the /entries/ in the list L = (l_n).
> Accordingly we define for any list L = (l_n):
>
> x in L =df En(n e N & x = l_n).
> "x is in the list L."
>
> x not in L =df ~(x in L)
> "x is not in the list L."
>
> Now we have the assumption:
>
> L = (l_n) & An(n e N -> ~(d = l_n)).
>
> "The anti-diagonal d differs from every entry in the list L."
And again I'll notice that what you are assuming holds thanks to
Cantor, so that your proof is just irrelevant to the present and
related discussions.
-LV
Balthasar
>>
>> Moreover, the anti-diagonal differs from every entry in the list.
>> That's all that is required to show that the anti-diagonal is not
>> on [or in] the list.
>>
> In the following I'll give a formal proof for this (the latter) claim.
>
> First some definitions. The /list/ L will be represented as an infinite
> sequence: L = (l_n). The l_ns are the /entries/ in the list L = (l_n).
> Accordingly we define for any list L = (l_n):
>
> x in L =df En(n e N & x = l_n).
> "x is in the list L."
>
> x not in L =df ~(x in L)
> "x is not in the list L."
>
> Now we have the assumption:
>
> L = (l_n) & An(n e N -> ~(d = l_n)).
>
> "The anti-diagonal d differs from every entry in the list L."
>
> We want to prove:
>
> d not in L.
>
> "The anti-diagonal d is not in the list L."
>
> Proof (in NJ + identity): [...]
>
Of course there's a simpler method to show this.
From our definition of /x in L/ for a list L = (l_n), we have
d in L <-> En(n e N & d = l_n).
Hence
~(d in L) <-> ~En(n e N & d = l_n).
Hence
d not in L <-> An(n e N -> ~(d = l_n)).
With other words, "d not in L" just "means" that d differs from every
entry in L = (l_n). qed.
Though this result seems to present another difficulty for WM's
position:
"For every line of Cantor's list it is true that this line does not
contain the diagonal number. Nevertheless the diagonal number may
be in the infinite list."
B.
ju...@diegidio.name
The endless ways of the same paralogism.
But, will you ever get it? Infinity, clearly enumerable, here and now.
It extends easily: you are an instance of the class of the failing
machines.
-LV
Balthasar
>>
>> Moreover, the anti-diagonal differs from every entry in the list.
>> That's all that is required to show that the anti-diagonal is not
>> on [or in] the list.
>>
> In the following I'll give a formal proof for this (the latter) claim.
>
Concerning the former claim just some comments (for our crank):
Actually, Cantor himself did not consider /real numbers/ (and/or their
decimal expansion) in his proof where he introduced the diagonal
argument, hence all this (cranky) talking about "limits" and
"limit entry" and whatnot could not arise.
So, for the sake of the argument, let's _not_ consider a list of real
numbers (and/or of their decimal expansions), but a list of infinite
sequences of the two symbols /a/ and /b/. Now let's just consider one
such list (to point out the construction of the anti-diagonal):
(1) [a] a b b a a b a ...
(2) a [a] a a a a b b ...
(3) b b [b] b a a b a ...
(4) a b b [b] a b b b ...
: ...
(Note, I put a [] around each symbol of the diagonal.)
In this case we get the anti-diagonal by replacing /a/ with /b/ and vice
versa. Hence we get the sequence
b b a a ...
Now this sequence differs from any sequence in the list by at least one
symbol. (@Crank: Exercise!)
With other words, it differs from every entry in the list.
---------------------------------------------------------
B.
ju...@diegidio.name
> On Sat, 09 Aug 2008 08:28:00 +0200, Balthasar <nomail@invalid> wrote:
>
> >> Moreover, the anti-diagonal differs from every entry in the list.
> >> That's all that is required to show that the anti-diagonal is not
> >> on [or in] the list.
>
> > In the following I'll give a formal proof for this (the latter) claim.
>
> Concerning the former claim just some comments (for our crank):
So you in panic keep repeating yourself over and over again.
I've just seen in a movie that's the way to recognize a machine masked
as a human.
I'm again impressed by how much wisdom there is in common wisdom.
-LV
David C. Ullrich
>On 9 Aug, 00:06, stevendaryl3...@yahoo.com (Daryl McCullough) wrote:
>> ju...@diegidio.name says...
>>
>> >Below again a simple argument to show that from the very same
>> >construction we could induce the exact opposite result:
>>
>> >1: The diagonal differs from the 1st entry in the 1st place;
>> >2: The diagonal differs from the 2nd entry in the 2nd place;
>> >n: The diagonal differs from the n-th entry in the n-th place;
>>
>> >It seems straightforward to induce that, at the limit, the difference
>> >between the diagonal and the limit entry tends to zero.
>>
>> That's completely false. Let's try an example: Suppose
>> your list is the following:
>>
>> 0.[1]000000....
>> 0.0[1]00000....
>> 0.00[1]0000...
>> 0.000[1]000...
>>
>> etc. (Note, I put a [] around each digit of the diagonal)
>>
>> Now, to diagonalize, we add 1 to each diagonal element. This
>> gives the number
>>
>> 0.22222...
>>
>> That number does not appear on the list, and it is certainly
>> not equal to the limit of the numbers on the sequence.
>>
>> When someone says "The diagonal differs from the 2nd entry in the
>> 2nd place" they don't mean that that is the *only* place they
>> differ. The diagonal may differ from the 2nd entry in many places,
>> but it differs in at least the 2nd place.
>>
>> So, no, your simple argument doesn't show the opposite result.
>
>
>Good one, at least looks like mathematics.
>
>Although your construction is rather itself "broken": not less good
>for my argument then it might be for Cantor's.
Huh? His "argument" is simply a carefully written example
of what might be happening in that diagonal argument.
It shows explicitly why what you said makes no sense,
as everyone's been saying. (You could have saved youself
the trouble of embarassing yourself again by coming
up with "his argument" yourself, by the way - all he did
was go through the proof with an explicit example of
a list of reals.)
It's just an illustration of what's going on in the proof.
How in the world is this "not less good" for the proof?
>Shall I point you to some article on the diagonal argument? For the
>sake of the discussion.
>
>-LV
>
>
>> --
>> Daryl McCullough
>> Ithaca, NY
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.)
ju...@diegidio.name
If that's a carefully written example of what might be happening in
that diagonal argument, hmm... yes, I guess that's what I meant.
Shall I point you too to some article on the diagonal argument?
-LV
Daryl McCullough
>
>On 8 Aug 2008 16:09:48 -0700, stevend...@yahoo.com (Daryl
>McCullough) wrote:
>
>>
>> No, the anti-diagonal does *not* equal the "limit entry".
>>
>It doesn't? So YOU know how the /limit entry/ is defined? Well, at least
>*I* don't know how it is defined, hence *I* can't claim that - since I
>don't have a proof for this assertion. [...]
>
>>
>> Why would you think that?
>>
>Because he's a troll or a crank?
>
>>
>> The differences *don't* tend to zero.
>>
>Well, here I have to disagree. Actually, they do - in a certain sense.
I gave an example where the differences don't tend to zero.
It is *possible* for the differences to tend to zero, but
they are not guaranteed to tend to zero.
elsiemelsi
Diagonalization is a very general tecnique aiming at showing thet a
certain set S does not exist: e.g. a countable set of all reals
(Cantor), a bijection between A and P(A) (Cantor), a recursively
enumerable set of all arithmetical truths (Gödel), an arithmetically
definable set of all arithmetical truths (Tarski), etc
i say
complete rubbish
the australian philospher colin leslie dean has pointed out
http://gamahucherpress.yellowgum.com/books/philosophy/GODEL5.pdf
godel cant tell us what make a mathematical statememt true and neither can
any other
mathematician
quote
GODEL CAN NOT TELL US WHAT MAKES A STATEMENT TRUE
mathematician have so much invested in godels incompleteness theorem
much maths is reliant on it but at the time godel wrote his theorem he had
no idea of what truth was as peter smith the Cambridge expert on Godel
admitts
http://groups.google.com/group/sci.logic/browse_thread/thread/ebde70bc932fc0a7/de566912ee69f0a8?lnk=gst&q=G%C3%B6del+didn%27t+rely+on+the+notion+PETER+smith#de566912ee69f0a8
Quote:
Gödel didn't rely on the notion
of truth
but truth is central to his theorem
as peter smith kindly tellls us
http://assets.cambridge.org/97805218...40_excerpt.pdf
Quote:
Godel did is find a general method that enabled him to take any theory T
strong enough to capture a modest amount of basic arithmetic and
construct a corresponding arithmetical sentence GT which encodes the claim
‘The sentence GT itself is unprovable in theory T’. So G T is true if
and only
if T can’t prove it
If we can locate GT
, a Godel sentence for our favourite nicely ax-
iomatized theory of arithmetic T, and can argue that G T is
true-but-unprovable,
and godels theorem is
http://en.wikipedia.org/wiki/G%C3%B6...s_theorems#Fir...
Quote:
Gödel's first incompleteness theorem, perhaps the single most celebrated
result in mathematical logic, states that:
For any consistent formal, recursively enumerable theory that proves
basic arithmetical truths, an arithmetical statement that is true, but not
provable in the theory, can be constructed.1 That is, any effectively
generated theory capable of expressing elementary arithmetic cannot be
both consistent and complete.
you see godel referes to true statement
but Gödel didn't rely on the notion
of truth
now because Gödel didn't rely on the notion
of truth he cant tell us what true statements are
thus his theorem is meaningless
this puts mathematicians in deep shit because all the modern idea derived
from godels theorem have no epistemological or mathematical worth for we
dont know what true statement are
--
Message posted using http://www.talkaboutscience.com/group/sci.logic/
More information at http://www.talkaboutscience.com/faq.html
Daryl McCullough
No, I showed that *your* argument was broken. You said
something nonsensical and you gave a false proof of it.
>Shall I point you to some article on the diagonal argument?
Shall I point you to some article on what a logical argument is?
>For the sake of the discussion.
If someone tried to have a discussion with you about
whether 2 is an odd number, or whether the square-root
of 10 is an integer, what do you think would come out
of that discussion?
Just take the following:
Claim: If f(i) is a function that takes a natural number i
and returns a real number between 0 and 1, then there is
a real number r between 0 and 1 such that f(i) is never
equal to r.
Proof: Let f(i)[j] be decimal place number j of f(i). We
construct a new real r whose jth decimal place r[j] is
given by:
If f(i)[i] > 4, then r[i] = f(i)[i] + 1.
Otherwise, r[i] = f(i)[i] - 1.
(This guarantees that r[i] is 1,2,3,4,5,6,7, or 8,
avoiding the cases of decimals that end with all 0s
or all 9s)
Then for every natural number i, r is unequal to f(i),
because the ith decimal place of r is 1 different from
the ith decimal place of f(i).
Daryl McCullough
ju...@diegidio.name says...
Yes, these newsgroup consists mostly of reiterations of
the following process:
1. A crank claims to prove that some well-known theorem is false.
2. Multiple non-cranks explain how he is mistaken.
The cycle can't really end, because the crank is either not
willing or not able to understand the explanations, and the
non-cranks are either not willing or not able to just let
someone wallow in his own ignorance.
Every conceivable argument against Cantor's theorem has
already been trotted out, many times before. So yes, it's
all reiteration, including what you are saying and what
people are saying in response to you. Only the players
change...
Daryl McCullough
>Shall I point you too to some article on the diagonal argument?
Uh, *your* the one who doesn't understand it. So people should
be pointing *you* to relevant articles. For example:
http://en.wikipedia.org/wiki/Cantor%27s_diagonal_argument
http://mathworld.wolfram.com/CantorDiagonalMethod.html
http://www.mathpages.com/home/kmath371.htm
Cantor also gave, before his diagonal proof, an alternative
proof of the uncountability of the reals:
http://en.wikipedia.org/wiki/Cantor%27s_first_uncountability_proof
jacko
> I heard someone say recently, "The proof of the Turing
> machine halting problem is an example of diagonalization."
I'm sure i saw a 'proof'' using the set of all programs example..
> I don't see that. As I recall, it's proof by contradiction;
> assume a program which accomplishes the goal, feed
> the code of this program to itself, etc., ad absurdum. QED
>
> Whereas diagonalization consists of constructing a list,
> then constructing a new object not in the list, etc.
This is very logically flawed, because the thing constructed i the
next element of such a lst, therefore it is always possible to
construct something extra which is in the list, as well as show
something is not in the list yet.
order of reals is same as rationals :i.e. z^2.
proof: place all Zintegers in a list. do this again. Then place a
mirror with a little black spot point in fromt of one set.
Now all reals are the sum f an element from one list and an element
from the other. Z*Z = Z^2.
Now this is obvoius, and requires no proof by negation, so the flaws
of such negation proofs discovered via godel can not be seen in it.
In relation to turing halting. I can say no more than DO'T use
diagonalization and proof by negation if there are oher options.
cheers
jacko
jacko
proof: cos pi is defined as an infinite summation of rationals.
summing rationals ALWAYS produces a rational.
Ben Bacarisse
<snip>
> With my construction I don't get higher order infinite ordinals, but
> instead I get that 'oo' is representable, as is 'oo-1' and so on. That
> is, we can enumerate from zero as well as enumerate back from
> infinity. And I mean we can enumerate forwards or backwards the
> infinite list of the computable reals, say in [0, 1], where 1 is the
> usual diagonal at 0 and viceversa, 0 is the inverse diagonal at 1.
> Actually, given an ordering rule over the list, we can enumerate
> forwards or backwards at some specific points, but I'll leave the
> details out.
So order the list of "computable reals" in [0, 1] (I use quotes
because I am quoting you -- I don't know what these things are yet) to
get r1, r2, r3... and consider the list of numbers r(n):
r1+(r2-r1)/2, r1+(r2-r1)/3, r1+(r2-r1)/4,... r1+(r2-r1)/(n+1),...
All of these look computable to me so this list is simply a
permutation of r1, r2, r3... Which one is equal to r1 and which one
is equal to r2? What follows from r(x) = r1 and/or r(y) = r2?
--
Ben.
cplx...@gmail.com
> nd just for the record pi is an infinite rational.
>
> proof: cos pi is defined as an infinite summation of rationals.
> summing rationals ALWAYS produces a rational.
Pi is irrational. A finite sum of rationals is rational, but an
infinite sum need not be. How would you express pi as the quotient of
two integers (the definition of a rational)?
Balthasar
McCullough) wrote:
>>
>> Well, here I have to disagree. Actually, they do - in a certain sense.
>>
> I gave an example where the differences don't tend to zero.
>
Right. I guess it would be better to be more specific (for our crank) in
this case: the "guaranteed differences" (i.e. the differences in the
"worst case") tend to zero.
>
> It is *possible* for the differences to tend to zero, but
> they [do not necessarily] tend to zero.
>
Right.
B.
--
"For every line of Cantor's list it is true that this line does not
contain the diagonal number. Nevertheless the diagonal number may
be in the infinite list." (WM, sci.logic)
Ben Bacarisse
I now see that "permutation" is not correct. In fact, in trying to
repair this argument, I now suspect that you define "computable" so
you are actually enumerating the rationals in [0, 1] (or at least some
other countable subset of the reals). It would be best for me to say
no more unless you define "computable real" and the ordering rule. A
reference would be fine.
--
Ben.
herbzet
ju...@diegidio.name wrote:
> Below again a simple argument to show that from the very same
> construction we could induce the exact opposite result:
>
> 1: The diagonal differs from the 1st entry in the 1st place;
> 2: The diagonal differs from the 2nd entry in the 2nd place;
> ...
> n: The diagonal differs from the n-th entry in the n-th place;
>
> It seems straightforward to induce that, at the limit, the difference
> between the diagonal and the limit entry tends to zero.
One problem here is that there may not be a unique limit point to
the sequence enumerated by the list.
Example: Enumerate in some fashion the rational numbers in [0, 1]:
q1, q2, q3, ...
Then each rational qi is a limit point of the sequence, as is
each irrational number in [0, 1]. (A Cantorian might remark
that there are more limit points than entries in the list ...)
Certainly in this case the diagonal number will be a limit
point of the sequence, though different from (unequal to)
every member of the sequence.
(It is of course a theorem of analysis that a bounded sequence
of real numbers will have a limit point.)
--
hz
Barb Knox
<7c07f984-0a79-4248...@c58g2000hsc.googlegroups.com>,
ju...@diegidio.name wrote:
> On 9 Aug, 07:20, Barb Knox <s...@sig.below> wrote:
> > In article
> > <371eb05c-831d-435d-8dea-966887ca4...@e39g2000hsf.googlegroups.com>,
> > ju...@diegidio.name wrote:
> > > On 8 Aug, 19:00, Chris Menzel <cmen...@remove-this.tamu.edu> wrote:
[snip]
> > > > Let me guess: You also think that an infinite set of numbers must
> > > > contain an infinitely large number.
> >
> > > Easy guess. That number is called infinity, or otherwise "omega" ('w',
> > > or even 'oo').
> >
> > > With my construction I don't get higher order infinite ordinals, but
> > > instead I get that 'oo' is representable, as is 'oo-1' and so on. That
> > > is, we can enumerate from zero as well as enumerate back from
> > > infinity.
> >
> > So then do you reject mathematical induction?
>
> Absolutely not. I rather "double it". Informally speaking, I have two
> end-points, zero and its mirror, infinity. Maybe keep in mind there is
> no uncomputables in this realm.
>
> > If not, then one can
> > easily prove that oo < oo, which does not look healthy.
>
> I'd be interested in seeing it, thanks. Mine is still mostly an
> exploration.
OK, I'll bite, since "exploration" does imply that you might under some
circumstances reconsider your current position.
Here's a mathematical induction proof that oo < oo, using simple
induction on N* (which is hereby defined as N augmented by the single
limit point "oo").
Lemma: For all n in N*, n < oo.
Base case: clearly 0 < oo.
Induction step: Assume k < oo. Then clearly k+1 < oo also.
Applying the lemma to n = oo, we get oo < oo.
QED.
Thus mathematical induction does not work for N*.
(Note: There is a form of induction that DOES work for "transfinite
ordinals" -- see for example
<http://en.wikipedia.org/wiki/Transfinite_induction>.)
ju...@diegidio.name
> In article
Very well appreciated.
> Here's a mathematical induction proof that oo < oo, using simple
> induction on N* (which is hereby defined as N augmented by the single
> limit point "oo").
>
> Lemma: For all n in N*, n < oo.
> Base case: clearly 0 < oo.
> Induction step: Assume k < oo. Then clearly k+1 < oo also.
>
> Applying the lemma to n = oo, we get oo < oo.
> QED.
>
> Thus mathematical induction does not work for N*.
>
> (Note: There is a form of induction that DOES work for "transfinite
> ordinals" -- see for example
> <http://en.wikipedia.org/wiki/Transfinite_induction>.)
Indeed, I have been using transfinite induction explicitly in my
recent posts on the argument. Here I have dropped it, first because my
account was very fast and very informal, second because mentioning the
"transfinite" just led me reiterated accusations of being pompous with
no content and no understanding. So I thank you for bringing this up.
Is now my argument safe? To be true: I think so, as I have in the
meantime discovered the "subcountables", so that I cannot be that off-
road after all...
-LV
> --
> ---------------------------
> | 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 |
> ------------------------------
ju...@diegidio.name
> ju...@diegidio.name wrote:
> > Below again a simple argument to show that from the very same
> > construction we could induce the exact opposite result:
>
> > 1: The diagonal differs from the 1st entry in the 1st place;
> > 2: The diagonal differs from the 2nd entry in the 2nd place;
> > ...
> > n: The diagonal differs from the n-th entry in the n-th place;
>
> > It seems straightforward to induce that, at the limit, the difference
> > between the diagonal and the limit entry tends to zero.
>
> One problem here is that there may not be a unique limit point to
> the sequence enumerated by the list.
Sorry, I don't get it. Could you be more specific?
I also suppose this is the same objection as Balthasar's and Mr
McCullough's. But I don't know what you are hinting at here.
> Example: Enumerate in some fashion the rational numbers in [0, 1]:
>
> q1, q2, q3, ...
>
> Then each rational qi is a limit point of the sequence, as is
> each irrational number in [0, 1]. (A Cantorian might remark
> that there are more limit points than entries in the list ...)
I don't know what that means, for each qi to be a limit point of the
sequence.
-LV
ju...@diegidio.name
> Ben Bacarisse <ben.use...@bsb.me.uk> writes:
> > ju...@diegidio.name writes:
> > <snip>
> >> With my construction I don't get higher order infinite ordinals, but
> >> instead I get that 'oo' is representable, as is 'oo-1' and so on. That
> >> is, we can enumerate from zero as well as enumerate back from
> >> infinity. And I mean we can enumerate forwards or backwards the
> >> infinite list of the computable reals, say in [0, 1], where 1 is the
> >> usual diagonal at 0 and viceversa, 0 is the inverse diagonal at 1.
> >> Actually, given an ordering rule over the list, we can enumerate
> >> forwards or backwards at some specific points, but I'll leave the
> >> details out.
>
> > So order the list of "computable reals" in [0, 1] (I use quotes
> > because I am quoting you -- I don't know what these things are yet) to
> > get r1, r2, r3... and consider the list of numbers r(n):
>
> > r1+(r2-r1)/2, r1+(r2-r1)/3, r1+(r2-r1)/4,... r1+(r2-r1)/(n+1),...
>
> > All of these look computable to me so this list is simply a
> > permutation of r1, r2, r3... Which one is equal to r1 and which one
> > is equal to r2? What follows from r(x) = r1 and/or r(y) = r2?
>
> I now see that "permutation" is not correct. In fact, in trying to
> repair this argument, I now suspect that you define "computable" so
> you are actually enumerating the rationals in [0, 1] (or at least some
> other countable subset of the reals).
Yes, I am definitely enumerating a computable set, what I have called
"the computable reals".
> It would be best for me to say
> no more unless you define "computable real" and the ordering rule.
As I can see it, all ordering rules are equivalent modulo the
appropriate mapping. The "natural ordering" here I'd say is the usual
ordering for the permutations of the digits. With the period after the
diagonal element, just for reading purposes:
0:0(0)
1:10(0)
2:010(0)
3:1100(0)
4:00100(0)
...
Given, if I am not mistaken, that all ordering rules are equivalent
modulo mapping, interesting results follow, trivially. For instance,
the anti-diagonal here is simply the sequence: oo:(1).
And we can enumerate backwards (again with the period after the
diagonal element):
oo :1(1)
oo-1:01(1)
oo-2:101(1)
oo-3:0011(1)
oo-4:11011(1)
And, simmetrically, the "inverse" anti-diagonal we get is: 0:(0).
-LV
ju...@diegidio.name
That is actually an enumeration of all the computable reals in:
[0.(0), 1.(1)]
ju...@diegidio.name
> That is actually an enumeration of all the computable reals in:
>
> [0.(0), 1.(1)]
Sorry, should read:
[0.(0), 0.(1)]
-LV
ju...@diegidio.name
> On 9 Aug, 21:27, herbzet <herb...@gmail.com> wrote:
>
> > ju...@diegidio.name wrote:
> > > Below again a simple argument to show that from the very same
> > > construction we could induce the exact opposite result:
>
> > > 1: The diagonal differs from the 1st entry in the 1st place;
> > > 2: The diagonal differs from the 2nd entry in the 2nd place;
> > > ...
> > > n: The diagonal differs from the n-th entry in the n-th place;
>
> > > It seems straightforward to induce that, at the limit, the difference
> > > between the diagonal and the limit entry tends to zero.
>
> > One problem here is that there may not be a unique limit point to
> > the sequence enumerated by the list.
>
> Sorry, I don't get it. Could you be more specific?
>
> I also suppose this is the same objection as Balthasar's and Mr
> McCullough's. But I don't know what you are hinting at here.
>
> > Example: Enumerate in some fashion the rational numbers in [0, 1]:
>
> > q1, q2, q3, ...
>
> > Then each rational qi is a limit point of the sequence, as is
> > each irrational number in [0, 1]. (A Cantorian might remark
> > that there are more limit points than entries in the list ...)
>
> I don't know what that means, for each qi to be a limit point of the
> sequence.
Hmm, maybe I get it. It's that I am a "post-cantorian
constructivist" ;)
That there are more reals than naturals is not a fact, but a
consequence of the "cantorian" line of reasoning via the diagonal
argument. That very argument is in question, then the rest is a
consequence, just as true as its premise.
Indeed, from the naturals and (transf.) induction only, I quite don't
get anything like that, and *that* is the toolset you are supposed to
start from.
-LV
Balthasar
McCullough) wrote: [...]
Actually, Cantor himself did not consider /real numbers/ (and/or their
decimal expansion) in his proof where he introduced the diagonal
argument, hence all this (cranky) talking about "limits" and
"limit entry" and whatnot could not arise.
So, for the sake of the argument, let's _not_ consider a list of real
numbers (and/or a list of their decimal expansions), but a list of
infinite sequences of the two symbols /a/ and /b/. Now let's just
consider one such list (to point out the construction of the anti-
diagonal):
(1) [a] a b b a a b a ...
(2) a [a] a a a a b b ...
(3) b b [b] b a a b a ...
(4) a b b [b] a b b b ...
: ...
(Note, I put a [] around each symbol of the diagonal.)
In this case we get the anti-diagonal by replacing /a/ with /b/ and vice
versa. Hence we get the sequence
b b a a ...
Now this sequence differs from any sequence in the list by at least one
symbol. (See below.) With other words, it differs from every entry in
the list.
Slightly more formal approach:
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Claim: If (l_i) is an infinite sequence such that its members l_i are
infinite sequences of the symbols /a/ and /b/, then there is an infinite
sequence d (of the symbols /a/ and /b/) such that d is not a member of
(l_i) (i.e. for all n e N: d =/= l_n).
Proof: Let [l_i]_j be the j-th members of the sequence l_i. We define a
sequence d = (d_i) with:
/ /a/ if [l_i]_i = /b/
d_i = {
\ /b/ if [l_i]_i = /a/ .
Then for every natural number n: d =/= l_n, because for any natural
number n, the n-th member of d differs from the n-th member of l_n.
ju...@diegidio.name
> On 9 Aug 2008 04:50:50 -0700, stevendaryl3...@yahoo.com (Daryl
>
> McCullough) wrote: [...]
>
> Actually, Cantor himself did not consider /real numbers/ (and/or their
> decimal expansion) in his proof where he introduced the diagonal
> argument, hence all this (cranky) talking about "limits" and
> "limit entry" and whatnot could not arise.
>
> So, for the sake of the argument, let's _not_ consider a list of real
> numbers (and/or a list of their decimal expansions), but a list of
> infinite sequences of the two symbols /a/ and /b/. Now let's just
> consider one such list (to point out the construction of the anti-
> diagonal):
>
> (1) [a] a b b a a b a ...
> (2) a [a] a a a a b b ...
> (3) b b [b] b a a b a ...
> (4) a b b [b] a b b b ...
> : ...
>
> (Note, I put a [] around each symbol of the diagonal.)
>
> In this case we get the anti-diagonal by replacing /a/ with /b/ and vice
> versa. Hence we get the sequence
>
> b b a a ...
>
> Now this sequence differs from any sequence in the list by at least one
> symbol. (See below.) With other words, it differs from every entry in
> the list.
That is Cantor thesis, and you just make it the usual non-sequitur.
__It just does not hold as such for infinite sequences, unless one
proves otherwise.__
> Slightly more formal approach:
> ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
>
> Claim: If (l_i) is an infinite sequence such that its members l_i are
> infinite sequences of the symbols /a/ and /b/, then there is an infinite
> sequence d (of the symbols /a/ and /b/) such that d is not a member of
> (l_i) (i.e. for all n e N: d =/= l_n).
>
> Proof: Let [l_i]_j be the j-th members of the sequence l_i. We define a
> sequence d = (d_i) with:
>
> / /a/ if [l_i]_i = /b/
> d_i = {
> \ /b/ if [l_i]_i = /a/ .
>
> Then for every natural number n: d =/= l_n, because for any natural
> number n, the n-th member of d differs from the n-th member of l_n.
Ditto: we are talking about infinite sequences, and that is at best a
non sequitur...
In fact, you keep "proving Cantor with Cantor". Over and over.
-LV
Ben Bacarisse
> On 9 Aug, 16:53, Ben Bacarisse <ben.use...@bsb.me.uk> wrote:
<snip>
>> It would be best for me to say
>> no more unless you define "computable real" and the ordering rule.
>
>
> As I can see it, all ordering rules are equivalent modulo the
> appropriate mapping. The "natural ordering" here I'd say is the usual
> ordering for the permutations of the digits. With the period after the
> diagonal element, just for reading purposes:
>
> 0:0(0)
> 1:10(0)
> 2:010(0)
> 3:1100(0)
> 4:00100(0)
> ...
>
> Given, if I am not mistaken, that all ordering rules are equivalent
> modulo mapping, interesting results follow, trivially. For instance,
> the anti-diagonal here is simply the sequence: oo:(1).
>
> And we can enumerate backwards (again with the period after the
> diagonal element):
>
> oo :1(1)
> oo-1:01(1)
> oo-2:101(1)
> oo-3:0011(1)
> oo-4:11011(1)
> And, simmetrically, the "inverse" anti-diagonal we get is: 0:(0).
Well I see what you are doing, but i don't see why you think it is
interesting. You have a representation where every number can be
written two ways (take the final 1 and replace with 01(1)). With such
a representation the anti-diagonal can only be constructed if both
representations are present.
For example, if you alternate elements from your two lists the
anti-diagonal is 0.101010101 = 2/3. It illustrates one of a vast
family of rationals that are not on ether list: 1/3, 1/5, 1/6... Of
course pi-3 is missing too, along with all the other transcendentals
and irrationals in [0, 1].
Where does defining this countable subset of the rationals get you?
--
Ben.
Ben Bacarisse
You can call it a thesis and claim it does not follow, but to make any
headway you have to point out the flaw to all of us dumb sheep who
find the proof convincing. Do you reject proof by contradiction? Do
you reject idea of defining a sequence as a rule using data from all the
elements of the list? Do you reject that the sequence so defined is
in fact distinct? Something else?
<snip>
> In fact, you keep "proving Cantor with Cantor". Over and over.
I have not see anyone make a proof that starts by assuming that the
set is uncountable or even that uncountable sets exist. I certainly
have not seen anything from you to explain the circularity you claim
to see.
--
Ben.
herbzet
ju...@diegidio.name wrote:
> herbzet wrote:
> > ju...@diegidio.name wrote:
> >
> > > Below again a simple argument to show that from the very same
> > > construction we could induce the exact opposite result:
> >
> > > 1: The diagonal differs from the 1st entry in the 1st place;
> > > 2: The diagonal differs from the 2nd entry in the 2nd place;
> > > ...
> > > n: The diagonal differs from the n-th entry in the n-th place;
> >
> > > It seems straightforward to induce that, at the limit, the difference
> > > between the diagonal and the limit entry tends to zero.
> >
> > One problem here is that there may not be a unique limit point to
> > the sequence enumerated by the list.
>
> Sorry, I don't get it. Could you be more specific?
You say that the difference between the diagonal and "the limit entry"
tends to zero. I'm saying that it's possible that "the limit entry"
(whatever you mean by that) may not be unique: there may be more than
one "limit entry".
An infinite list of numbers from the interval [0, 1] will certainly
have a /limit point/, as I mentioned at the end of my previous post.
The problem is that for some lists (sequences) there is more than
one /limit point/.
> I also suppose this is the same objection as Balthasar's and Mr
> McCullough's.
Not quite.
> But I don't know what you are hinting at here.
I don't know what you mean by "the limit entry". I'm supposing that
you might mean "the limit point". But a sequence (list) might have
more than one limit point.
A number L is a limit point of a sequence if for every interval
[L + x, L - x] there is a member of the sequence (other than L)
in that interval.
In other words, a number L is a limit point of a sequence if there
are numbers in the sequence arbitrarily close to L. Is this what
what you mean by "the limit entry"?
> > Example: Enumerate in some fashion the rational numbers in [0, 1]:
> >
> > q1, q2, q3, ...
> >
> > Then each rational qi is a limit point of the sequence, as is
> > each irrational number in [0, 1]. (A Cantorian might remark
> > that there are more limit points than entries in the list ...)
>
> I don't know what that means, for each qi to be a limit point of the
> sequence.
It means that every rational number q1, q2, q3, ... in [0, 1] has
other rational numbers arbitrarily close to it.
(It is also the case that any irrational number in [0, 1] has rational
numbers arbitrarily close to it.)
> > Certainly in this case the diagonal number will be a limit
> > point of the sequence, though different from (unequal to)
> > every member of the sequence.
> >
> > (It is of course a theorem of analysis that a bounded sequence
> > of real numbers will have a limit point.)
When you say the difference of the diagonal and the limit entry
tends to zero, I ask, /which/ limit entry (if there's more than
one)?
--
hz
ju...@diegidio.name
I don't know what taking such expansions as -- say -- 0.(9) and 1.(0)
to be equal brings to this argument, and actually if it is pertinent
at all.
The point remains: the list is indeed and already _complete_. It is
the infinite list of all the permutations of the digits in the
infinite decimal expansion.
> For example, if you alternate elements from your two lists the
> anti-diagonal is 0.101010101 = 2/3. It illustrates one of a vast
> family of rationals that are not on ether list
No, you have just given another enumeration order, and again the list
is complete and the anti-diagonal corresponds to the oo-th entry, etc.
etc. Namely, in your example, 2/3, the anti-diagonal, is the oo-th
entry. And we can again enumerate back. The list is still the same and
complete: you have just changed the order. (The actual construction is
maybe slightly subtler, in that for different enumeration rules
(orders) and for each base of representation, there is a *class* (in
the generic sense) of anti-diagonal sequences.)
> : 1/3, 1/5, 1/6... Of
> course pi-3 is missing too, along with all the other transcendentals
> and irrationals in [0, 1].
>
> Where does defining this countable subset of the rationals get you?
It's meant to be the set of (all) the computable reals, surely a
superset of the rationals. Actually a very significant set because of
the importance of computability.
-LV
> --
> Ben.
herbzet
Right! ;)
> That there are more reals than naturals is not a fact, but a
> consequence of the "cantorian" line of reasoning via the diagonal
> argument. That very argument is in question, then the rest is a
> consequence, just as true as its premise.
Sure.
> Indeed, from the naturals and (transf.) induction only, I quite don't
> get anything like that, and *that* is the toolset you are supposed to
> start from.
I'm just trying to figure out what you mean when you assert "the
difference between the diagonal and the limit entry tends to zero".
How do you know there's just one limit entry?
The sequence (the list) may tend to many limit points.
Example #2:
1/4, 3/8, 7/16, 15/32, ...
This list of numbers tends to 1/2.
3/4, 7/8, 15/16, 31/32, ...
This list of numbers tends to 1.
I combine the two lists into one list:
1/4, 3/4, 3/8, 7/8, 7/16, 15/16, ...
This list tends to both 1/2 and to 1.
--
hz
ju...@diegidio.name
That is my point. You are talking "analysis", but that's way beyond
the diagonal argument. Here you have sequences of naturals and
induction, that's it.
> In other words, a number L is a limit point of a sequence if there
> are numbers in the sequence arbitrarily close to L. Is this what
> what you mean by "the limit entry"?
>
> > > Example: Enumerate in some fashion the rational numbers in [0, 1]:
>
> > > q1, q2, q3, ...
>
> > > Then each rational qi is a limit point of the sequence, as is
> > > each irrational number in [0, 1]. (A Cantorian might remark
> > > that there are more limit points than entries in the list ...)
>
> > I don't know what that means, for each qi to be a limit point of the
> > sequence.
>
> It means that every rational number q1, q2, q3, ... in [0, 1] has
> other rational numbers arbitrarily close to it.
>
> (It is also the case that any irrational number in [0, 1] has rational
> numbers arbitrarily close to it.)
>
> > > Certainly in this case the diagonal number will be a limit
> > > point of the sequence, though different from (unequal to)
> > > every member of the sequence.
>
> > > (It is of course a theorem of analysis that a bounded sequence
> > > of real numbers will have a limit point.)
>
> When you say the difference of the diagonal and the limit entry
> tends to zero, I ask, /which/ limit entry (if there's more than
> one)?
The answer: "limit" there is informal. The formal definition and the
construction is by (transf.) induction over the naturals. In that
context, I say the "limit" sequence to mean the "oo-th" sequence and
equivalent labels. That sequence, the limit or oo-th sequence, not
only exists in general, by transf. induction over the (extended)
naturals, but we can even actually from it. That is, formally, all
that has got a precise (I mean, in the limits of my possibilities),
elementar, and unambiguous meaning, just look at the construction.
-LV
> --
> hz
ju...@diegidio.name
You might be confused between my objections to Balthasar and my
objections to Cantor's argument.
This one is simply what it is, a non-sequitur.
> Now this sequence differs from any sequence in the list by at least one
> symbol. (See below.) With other words, it differs from every entry in
> the list.
And the one below too:
> Then for every natural number n: d =/= l_n, because for any natural
> number n, the n-th member of d differs from the n-th member of l_n.
Of course it's proven by Cantor. The culprit is on the free usage of
"all/any".
That's not Cantor's fault.
-LV
> --
> Ben.
ju...@diegidio.name
No no, no limits of ratios and similar stuff involved.
I were just hinting at the common notion of n->oo over a sequence.
That is the kind of "limit" I was hinting at, and, again, talking
about such limit and the limit of a difference was informal and mostly
analogical. The formal construction is based on the naturals and
(transf.) induction.
-LV
> --
> hz
herbzet
It's just a definition. That's what "limit point" means. Is
that something different from "the limit entry"?
> elementary, and unambiguous meaning, just look at the construction.
I think you need some sleep! ;)
--
hz
ju...@diegidio.name
> It's just a definition. That's what "limit point" means. Is
> that something different from "the limit entry"?
Yes, is the answer still unclear?
> > that has got a precise (I mean, in the limits of my possibilities),
> > elementary, and unambiguous meaning, just look at the construction.
>
> I think you need some sleep! ;)
What does that mean? Are you bored by getting answeres to request of
clarifications?
-LV
> --
> hz
herbzet
Ah, I get it. You were just saying that "The farther out we go in
constructing the diagonal from the list, then [something]". It's
just a way of speaking.
You wrote:
" 1: The diagonal differs from the 1st entry in the 1st place;
2: The diagonal differs from the 2nd entry in the 2nd place;
...
n: The diagonal differs from the n-th entry in the n-th place;
It seems straightforward to induce that, at the limit, the difference
between the diagonal and the limit entry tends to zero."
I still don't understand the conclusion, since I don't know
what "the limit entry" means.
Try me tomorrow.
> The formal construction is based on the naturals and
> (transf.) induction.
Well, now you know what a limit point of a sequence is. Sometimes
the diagonal number will be a limit point, sometimes not.
--
hz
ju...@diegidio.name
No, I'd say it's the meaning of "induce" that you are missing.
> Try me tomorrow.
So it's you who need a sleep... ;)
> > The formal construction is based on the naturals and
> > (transf.) induction.
>
> Well, now you know what a limit point of a sequence is. Sometimes
> the diagonal number will be a limit point, sometimes not.
And, as I have told you, that notion of limit is just irrelevant to
the diagonal argument.
Anyway, have good dreams for now.
-LV
> --
> hz
David C. Ullrich
No, you haven't. You may think that's what you've been
doing, but in fact you argument has been based on _exactly_
the sort of incorrect quasi-induction as in Barb's example.
>Here I have dropped it, first because my
>account was very fast and very informal, second because mentioning the
>"transfinite" just led me reiterated accusations of being pompous with
>no content and no understanding.
Here's a hint: Any time you claim that you can show that R is
countable or that there is an error in the standard proof of
the uncountability of R people will conclude you have
no understanding. Exactly as if you claimed to have a proof
that 2 + 2 is not 4; then people would _correctly_ claim
you didn't understand arithmetic.
>So I thank you for bringing this up.
>
>Is now my argument safe? To be true: I think so, as I have in the
>meantime discovered the "subcountables", so that I cannot be that off-
>road after all...
>
>-LV
>
>
>> --
>> ---------------------------
>> | 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 |
>> ------------------------------
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.)
ju...@diegidio.name
That is? What are you babbling about?
> >Here I have dropped it, first because my
> >account was very fast and very informal, second because mentioning the
> >"transfinite" just led me reiterated accusations of being pompous with
> >no content and no understanding.
>
> Here's a hint: Any time you claim that you can show that R is
> countable or that there is an error in the standard proof of
> the uncountability of R people will conclude you have
> no understanding. Exactly as if you claimed to have a proof
> that 2 + 2 is not 4; then people would _correctly_ claim
> you didn't understand arithmetic.
The usual hint, the usual analogy, the usual reitereted ad hominem
nonsense.
Will you ever give any contribution but noise and denial?
Never mind.
-LV
Daryl McCullough
>No no, no limits of ratios and similar stuff involved.
>
>I were just hinting at the common notion of n->oo over a sequence.
>
>That is the kind of "limit" I was hinting at, and, again, talking
>about such limit and the limit of a difference was informal and mostly
>analogical
Well, for something to be actual mathematics, as opposed to
idle chatter, you have to be able to go beyond "informal and
mostly analogical" reasoning. Of course, idle chatter can be
fun, too, but it's not mathematics.
--
Daryl McCullough
Ithaca, NY
Daryl McCullough
>> (1) [a] a b b a a b a ...
>> (2) a [a] a a a a b b ...
>> (3) b b [b] b a a b a ...
>> (4) a b b [b] a b b b ...
>> : ...
>>
>> (Note, I put a [] around each symbol of the diagonal.)
>>
>> In this case we get the anti-diagonal by replacing /a/ with /b/ and vice
>> versa. Hence we get the sequence
>>
>> b b a a ...
>>
>> Now this sequence differs from any sequence in the list by at least one
>> symbol. (See below.) With other words, it differs from every entry in
>> the list.
>
>
>That is Cantor thesis, and you just make it the usual non-sequitur.
>
>__It just does not hold as such for infinite sequences, unless one
>proves otherwise.__
I am not convinced that you know what a "non-sequiter" is,
nor what an "infinite sequence" is, nor what it means to
prove a mathematical statement.
It appears to me that you are just engaging in idle chatter, not
mathematics.
--
Daryl McCullough
Ithaca, NY
>> Slightly more formal approach: