halting problem proof, via diagonalization?
in [Theory]
|
Prev: Integer factorization reduction to SAT
Next: Solutions manual to Microeconomic Theory Solution Manual - Mas-Colell
From: Ben Bacarisse on 10 Aug 2008 12:46 julio(a)diegidio.name writes: > On 10 Aug, 05:42, Ben Bacarisse <ben.use...(a)bsb.me.uk> wrote: >> ju...(a)diegidio.name writes: >> > On 10 Aug, 04:48, Balthasar <nomail(a)invalid> wrote: >> >> On 9 Aug 2008 04:50:50 -0700, stevendaryl3...(a)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. >> >> 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. > > You might be confused between my objections to Balthasar and my > objections to Cantor's argument. I may well be. I was hoping you'd address the questions I asked seeking clarification. Something, somewhere, in that chain of reasoning leading to the cardinality of the power set is something that you do not accept. Suggesting that the argument is circular means I should be looking for the conclusion as one of the premises, but I don't see it there. > 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. [BTW, I did not write this (nor the quote below) as I did the other texts with the same number of quote indentations. When you add text from a third source, I think it helps to mark it with some new quote character. I use |.] > 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". I don't see the problem, but equally I don't see the point in batting this back and forth in a plain text medium. If you have an alternate axiom set you prefer, maybe you could just point me at it? If you have a favourite paper or book with a formal exposition of Cantor's result to which you can say: "line 523 is the one that does not follow" then we can take is further. Otherwise, you'll just be saying you find some informal argument unacceptable where to me it seems fine. A more formal notation is the only way forward. -- Ben.
From: Balthasar on 10 Aug 2008 12:58 On 10 Aug 2008 19:22:16 +0300, Aatu Koskensilta <aatu.koskensilta(a)uta.fi> wrote: >> >> No, it doesn't hold for finite as well as infinite index sets. That >> is Cantor's result, not a premise. >> > Quite so. Cantor won the Fields Medal in 1987 for his revolutionary > proof of what is now known as Cantor's theorem > > Given two infinite sequences I: N --> O and J: N --> O, I =/= J iff > there is an n [in N] such that I(n) =/= J(n). > In the other hand, one might doubt that this result is THAT revolutionary, after all we might formulate the following as a PRINCIPLE (i.e. so,e sort of axiom): for any two functions f, g with domain D: f = g iff for all x in D: f(x) = g(x). Then we would immediately (from classical logic) get f =/= g iff there is an x in D: f(x) =/= g(x). Then we just might consider (i.e. define) /infinite sequences/ to be functions with domain D = N. From this Cantor's result (thesis) would follow! So we (would) have to question the principle: For any two functions f, g with domain D: f = g iff for all x in D: f(x) = g(x). 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)
From: tchow on 10 Aug 2008 13:24 In article <489DFDBD.FD904378(a)gmail.com>, herbzet <herbzet(a)cox.net> wrote: >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]. Yes, in fact something stronger can be said: For any real number r in [0,1], there is a subsequence q_{i_1}, q_{i_2}, q_{i_3}, ... that converges to r and such that each q_{i_j} agrees with r to more places than q_{i_{j-1}}. So if a number can be "in" a list even if no line of the list contains it, as long as some subsequence converges to it, then indeed every real number is "in" every list of all the rationals. -- 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
From: Balthasar on 10 Aug 2008 13:24 On Sun, 10 Aug 2008 17:46:31 +0100, Ben Bacarisse <ben.usenet(a)bsb.me.uk> wrote: >>> >>> 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". [Crank] >> > I don't see the problem, but equally I don't see the point in batting > this back and forth in a plain text medium. If you have an alternate > axiom set you prefer, maybe you could just point me at it? If you have > a favourite paper or book with a formal exposition of Cantor's result > to which you can say: "line 523 is the one that does not follow" then > we can take is further. Otherwise, you'll just be saying you find > some informal argument unacceptable where to me it seems fine. A more > formal notation is the only way forward. > Actually, a slightly more formal approach has already been delivered: 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. ------------------------ So what is missing is the a formal proof of the last sentence (referring to the notions just introduced above it). Left as an exercise to the reader. But it seems that we have already (finally) isolated the "problem": >>> >>> If A = (a_i) and B = (b_i) are two sequences with index set I, then >>> >>> A = B iff for all i e I: a_i = b_i. (*) >>> >>> This means >>> >>> A =/= B iff there is an i e I: a_i =/= b_i. (**) >>> >>> With other words, sequences differ from each other iff they have different >>> members for at least one index. (Note that in our case I = IN.) >>> >>> This holds for finite index sets as well as for infinite index sets >>> (i.e. for finite sequences as well as for infinite sequences). >>> >> No, it doesn't hold for finite as well as infinite index sets. [Crank] >> Well... My only (somewhat helpless) reaction to this is: --------------------------- So it seems he must object against extensionality too: If A and B are two sets, then A = B iff for all x: x in A iff x in B. Which in turn means A =/= B iff there is an x: x in A, but x not in B or x in B, but x not in A. @Crank: Note that this holds for finite sets as well as for infinite sets. Oh right, we ARE arguing in the context (i.e. framework) of set theory. Something invented/introduced by CANTOR - to be able to deal with finite as well as _infinite_ sets. 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)
From: Balthasar on 10 Aug 2008 13:28
On 10 Aug 2008 17:24:30 GMT, tchow(a)lsa.umich.edu wrote: >> >> 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]. >> > Yes, in fact something stronger can be said: For any real number r in [0,1], > there is a subsequence q_{i_1}, q_{i_2}, q_{i_3}, ... that converges to r > and such that each q_{i_j} agrees with r to more places than q_{i_{j-1}}. > > So if a number can be "in" a list even if no line of the list contains it, > as long as some subsequence converges to it, then indeed every real number > is "in" every list of all the rationals. > And this is indeed what is meant with the saying: Reading between the lines. :-) 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) |