Why can no one in sci.math understand my simple point?
in [Logic]
|
From: Mike Terry on 21 Jun 2010 20:29 "Peter Webb" <webbfamily(a)DIESPAMDIEoptusnet.com.au> wrote in message news:4c1f0213$0$17174$afc38c87(a)news.optusnet.com.au... > > "Tim Little" <tim(a)little-possums.net> wrote in message > news:slrni1tkli.jrj.tim(a)soprano.little-possums.net... > > On 2010-06-21, Peter Webb <webbfamily(a)DIESPAMDIEoptusnet.com.au> wrote: > >> "Tim Little" <tim(a)little-possums.net> wrote in message > >> I do understand that. But I don't actually ask for a "finite algorithm" > >> in > >> my proof, I only require that I am provided a purported list of all > >> comptuable Reals. > > > > Later in the proof, you claim that the antidiagonal real is > > computable. In other words, that there exists a finite algorithm for > > computing it. > > > > > >> Yes, in practice, this means that each item is specified by a finite > >> algorithm, but so what? I ask for a purported list of all computable > >> Reals > >> and show there is at least one missing. > > > > At least one *what* missing? A real? Fine - Cantor's proof shows > > that there is a missing real. > > And if the nth digit of the nth term is computable, then so is the nth term > of the anti-diagonal, as there is an explicit construction of the nth digit > of the anti-diagonal based upon the nth digit of the nth term. This is an easy mistake to make, and I imagine one of the standard "common mistakes students fall into". I've explained it elsewhere but briefly: 1. you know that for each n, the n'th real in the list is computable 2. i.e. for each n there is a (likely different) TM_n which computes the digit function for the n'th real 3. the problem is you want a new "subsuming" TM, TM_ALL which can take as input n, and return the n'th digit of the n'th real. 4. So, naively you want to "code" TM_ALL to say: get me TM_n(n). 5. But this isn't legal, because: - TM_n is a completely different TM - And you can't "embed" each of the (infinitely many) TM_n into the single TM_ALL because that wouldn't be a finite algorithm any more. - TM_n has a "Godel number" G_n that describes it, and IF you could compute that, you could then emulate TM_n to determine TM_n(n). The problem here is THE MAPPING n--->G_n ISN'T NECCESSARILY A COMPUTABLE FUNCTION! Now for SOME lists it obviously CAN be the case that the function (m,n) ---> the n'th digit of the m'th real IS computable. It's easy to deliberately construct such lists. In this case, TM_ALL can obviously use this function to get TM_n(n) so the antidiagonal in this case IS a computable number. But this doesn't work in general. Regards, Mike. ps. don't worry, this is the last time I'll mention this point unless you have specific questions about it.
From: Sylvia Else on 21 Jun 2010 20:44 On 15/06/2010 2:13 PM, |-|ercules wrote: > Consider the list of increasing lengths of finite prefixes of pi > > 3 > 31 > 314 > 3141 > .... > > Everyone agrees that: > this list contains every digit of pi (1) > > as pi is an infinite digit sequence, this means > > this list contains every digit of an infinite digit sequence (2) > > similarly, as computable digit sequences contain increasing lengths of > ALL possible finite prefixes > > the list of computable reals contain every digit of ALL possible > infinite sequences (3) The discussion on permutations of lists of computable reals to construct diagonals showed that it is possible to construct diagonals that have any finite prefix. However, you were quick to point out that as the computable reals contain numbers like 0.111111...., diagonals not containing a 1 are impossible. That is to say, there is a set of reals which contains all possible finite prefixes, but which does not contain all possible infinite sequences. Since that contradicts the reasoning used to conclude your proposition (3), you'd have to prove it some other way. Sylvia.
From: Owen Jacobson on 21 Jun 2010 22:13 On 2010-06-21 02:33:50 -0400, Peter Webb said: > "Owen Jacobson" <angrybaldguy(a)gmail.com> wrote in message > news:2010062100324493978-angrybaldguy(a)gmailcom... >> On 2010-06-19 22:31:56 -0400, Peter Webb said: >> >>> Cantor's original proof requires the list to be provided in advance >> >> No, it does not. It's an existence proof showing that: >> >> IF a list of reals L(x) (where L : N -> R) exists, THEN a real A_L >> exists such that for every natural number n, L(n) ≠ A_L. >> >> Or, equivalently, showing that: >> >> For every function L from N to R, there exists a real r not in the image of L. >> >> Being a constructive proof, it's usually *presented* as if it were an >> algorithm or a procedure, but it's only for ease of comprehension. > > Umm, I am talking about Cantor's proof as it is generally presented, > and in that case it is an explicit algorithm. > > >> Unfortunately, that seems to have backfired on you. >> > > So you are saying that Cantor's proof in its usual form is incorrect, > as it pretends to include an algorithmic process for computing the > anti-diagonal? I am saying that interpreting it as an algorithm is less useful as a mental model than interpreting it as a description of the properties of some real number (well, actually, some infinte sequence of zeroes and ones) that must exist for any list of reals (of infinite sequences of zeroes and ones, likewise). The phrase "for each" is a verbalism for the universal quantifier, not an instruction to perform some operation. In fact, considering your unusual definition of "list" (discussed further below), I'd like to clarify that even further and avoid the word "list" entirely: Cantor's proof demonstrates that, for every function L from N to {0, 1}^N, there exists an element of {0, 1}^N that is not in the image of L. Since this directly implies that no function from N to {0, 1}^N can be surjective, it proves that the set {0, 1}^N is uncountable. There is a bijection between the set {0, 1}^N and the power set of N, and there is are bijections between either of those sets and the set of real numbers, so those two sets are also uncountable. >> Incidentally, "countable" and "listable" mean the same thing in >> conventional set theories: an infinite set S is countable if and only >> if there exists an surjective function f from N to S. Since a "list" of >> elements of S is most easily formalized as a surjective function from N >> to S, denying that S is listable is equivalent to denying that it is >> countable. >> > > The existence of a surjective function from N to S proves it is countable. > > The ability to prepare a list of exactly the elements proves the list > is recursively enumerable. If that's what you mean by list, then this whole subthread may well be a simple misunderstanding. "A recursive enumeration" is not what anyone else in the thread means by "a list": we're all talking about totally arbitrary functions from N to some set, without any regard to computability. However, it's fairly well established that the set of computable reals is not recursively enumerable. Just so that I'm clear, do you agree that there exists a surjective function from N to the computable reals? -o
From: Newberry on 22 Jun 2010 00:02 On Jun 21, 3:36 pm, "Jesse F. Hughes" <je...(a)phiwumbda.org> wrote: > Transfer Principle <lwal...(a)lausd.net> writes: > > On Jun 21, 5:46 am, "Jesse F. Hughes" <je...(a)phiwumbda.org> wrote: > >> Newberry <newberr...(a)gmail.com> writes: > >> > What I had in mind is that if you drop the axiom of extent you can > >> > either conclude that there is no such list or that the anti-diagonal > >> > does not exist analogously to the conclusion that the set R = {x | ~(x > >> > in x} does not exist. > >> I'm not sure what the axiom of extent is. > > > It should be evident to Hughes that "Axiom of Extent" refers to > > the "Axiom of Extensionality," as "extensionality" is related to > > the English word "extent." A quick Google search -- which > > Hughes could have done himself in seconds -- reveals sources > > using the name "Axiom of Extent" that even Hughes should > > consider respectable, including papers written by mathematicians, > > textbooks (via Google books), and the class websites of some > > university math classes. > > Do you suppose I feigned ignorance for some nefarious reason? > > I did indeed consider the possibility that Newberry meant > extensionality, but I didn't see how it could be relevant. I still > don't. Maybe Newberry can confirm that's the axiom he meant and also > explain its relevance. Sorry, I meant the axiom of separation.
From: Newberry on 22 Jun 2010 00:10
On Jun 21, 6:11 am, Sylvia Else <syl...(a)not.here.invalid> wrote: > On 21/06/2010 1:39 PM, Newberry wrote: > > > > > Not sure why you think you had to tell us how the anti-diagonal is > > defined. You claimed you could CONSTRUCT it. Please go ahead and do > > so. > > I'm sure he will - right after you provide the list of reals. > > Sylvia. Dear Sylvia, I did not claim that I could construct a list of reals, but Virgil claimed he could construct an anti-diagonal. |