halting problem proof, via diagonalization?
in [Theory]
|
Prev: Integer factorization reduction to SAT
Next: Solutions manual to Microeconomic Theory Solution Manual - Mas-Colell
From: Balthasar on 10 Aug 2008 13:46 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. > Right. Hence it's important to _define_ the used notions. I'll just repost one of my recent pots, if you don't mind. ------------------------------------------------------------ "[...] 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." (MoeBee) 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.
From: Ben Bacarisse on 10 Aug 2008 13:46 Balthasar <nomail(a)invalid> writes: > 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: Yes, I has seen you sterling work trying to pin the problem down, but because of what followed, I though it had become a dead end... > 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: I am at a loss to know what is missing but I have a suspicion from another sub-thread. The binary digits example he posted has a problem: the conventional anti-diagonal construction (by symbol manipulation only) yields a string with value already on the list (because values on the list have duplicate representations as finite binary strings). I suspect he has been thrown by this apparently miraculous "hole" in the conventional construction. Of course, it is not a hole, and it certainly does not apply to your example that uses symbol strings with no numerical value attached, but that is the only place I can see as a source of confusion. I doubt that objecting to extensionality is the issue. > 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. [...] -- Ben.
From: Balthasar on 10 Aug 2008 13:48 On Sun, 10 Aug 2008 19:46:09 +0200, Balthasar <nomail(a)invalid> wrote: > > 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.
From: Balthasar on 10 Aug 2008 14:01 On Sun, 10 Aug 2008 18:46:32 +0100, Ben Bacarisse <ben.usenet(a)bsb.me.uk> wrote: > > [...] but that is the only place I can see as a source of confusion. > Oh..., it seems that you aren't very familiar with the psychology of canks, are you? :-) 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 14:20
On Sun, 10 Aug 2008 20:01:16 +0200, Balthasar <nomail(a)invalid> wrote: >> >> [...] but that is the only place I can see as a source of confusion. >> > Oh..., it seems that you aren't very familiar with the psychology of > canks, are you? :-) > Here comments like "The culprit is on the free usage of 'all/any'." (Crank) are telltaling. 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) |