Why can no one in sci.math understand my simple point?
in [Logic]
|
From: Tim Little on 18 Jun 2010 21:19 On 2010-06-18, Virgil <Virgil(a)home.esc> wrote: > Given the axiom of choice, as in ZFC, any countable set must be, at > least theoretically, listable, though such a listing need not be > computable. The definition of countability is the existence of a bijection with a subset of N. Since N can be well-ordered even in ZF, the theorem (countable -> listable) is easily proven without AC. - Tim
From: Peter Webb on 18 Jun 2010 21:25 "Virgil" <Virgil(a)home.esc> wrote in message news:Virgil-D224DB.13324818062010(a)bignews.usenetmonster.com... > In article <4c1b2c8e$0$1025$afc38c87(a)news.optusnet.com.au>, > "Peter Webb" <webbfamily(a)DIESPAMDIEoptusnet.com.au> wrote: > >> "Tim Little" <tim(a)little-possums.net> wrote in message >> news:slrni1m63n.jrj.tim(a)soprano.little-possums.net... >> > On 2010-06-18, Peter Webb <webbfamily(a)DIESPAMDIEoptusnet.com.au> wrote: >> >> I made no premise. >> > >> > Sure you did: you assumed that no list of computable numbers can >> > exist. You also assumed an incorrect definition of "computable". >> > >> >> No, I assumed that a list of all computable numbers can exist. Then I >> gave a >> simple algorithm which forms a computable number which is not on the >> list. I >> therefore proved that no list of all computable numbers can exist. >> >> It is *exactly* the same as Cantor's proof that the Reals cannot be >> listed. >> >> It is of interest because it is known that the computable numbers are >> countable. Therefore the property "cannot be listed" is *not* the same as >> the property "is uncountable". >> >> Cantor's diagonal proof does *not* show the Reals are uncountable; it >> just >> proves the much weaker statement that "the Reals cannot be listed". > > Given the axiom of choice, as in ZFC, any countable set must be, at > least theoretically, listable, though such a listing need not be > computable. No. The AxC will allow you to always pick another Real to add to your list, but not to biject the Reals with N which is what a list requires. You can AxC a countably infinite number of times to form a countable list, but it will not include all Reals. > > And if countable, for infinite sets, does not mean bijectable with N > (or listable), what does it mean? Bijectable with N and "listable" are not the same. To be "listable" the set must be countable and recursively enumerable.
From: K_h on 18 Jun 2010 21:35 "Peter Webb" <webbfamily(a)DIESPAMDIEoptusnet.com.au> wrote in message news:4c1b24ce$0$17177$afc38c87(a)news.optusnet.com.au... > > "Tim Little" <tim(a)little-possums.net> wrote in message > news:slrni1m2q9.jrj.tim(a)soprano.little-possums.net... >> On 2010-06-18, Peter Webb >> <webbfamily(a)DIESPAMDIEoptusnet.com.au> wrote: >>> "Tim Little" <tim(a)little-possums.net> wrote in message >>>> Cantor's construction applied directly to lists of >>>> computable numbers >>>> shows almost nothing. Given any list of computable >>>> reals, you can >>>> produce an antidiagonal real not on the list. >>>> Unfortunately the >>>> construction says nothing about whether the >>>> antidiagonal is computable >>>> or not. >>> >>> Of course its computable. It is a trivial programming >>> exercise to form a >>> computable number not on the list, by simply doing digit >>> substitutions. >> >> Only if the list itself is a computable function. >> Cantor's proof does >> not depend on any such assumption. >> > > If you give me a purported list of all computable numbers, > I can explicitly QUESTION 1: But ask yourself: is the list of all computable real numbers itself computable? Each real in such a list is computable but can you find a computable function that says which computable real is mapped to 0, which computable real is mapped to 1, which computable real is mapped to 2, and so on? > construct a Real not on the list. Of course this number is > computable; there is a simple algorithm to compute it. But ask yourself: since the algorithm you use to compute it calls on the "algorithm" I asked you about in QUESTION 1, is your algorithm depending on another "algorithm" that is non-computable? >>> Cantor's proof provides an explicit and simple algorithm >>> to form >>> such a number, and it is extremely easy to compute. >> >> If there exists no algorithm for computing the original >> list, how do >> you propose to use Cantor's proof to make an algorithm >> for the >> antidiagonal of that list? > > Cantor's proof just requires a list of numbers. > If you give me a purported list of all computable numbers, > I can produce a computable number not on the list. But ask yourself QUESTION 1 http://en.wikipedia.org/wiki/Computable_number >>>> It takes quite a bit of extra work (not part of >>>> Cantor's proof) to >>>> deduce that there is no computable list of all >>>> computable reals. >>> >>> Cantor's proof applied to computable numbers proves it >>> immediately and >>> simply. >> >> First you have to define the notion of "computable list", >> and set up >> the theorems proving properties about how computable >> lists and >> computable numbers relate. >> > > > No I don't, any more than Cantor had to that for all > Reals. > > You cannot produce a list of all computable Reals. Just as > you can't produce a list of all Reals. But ask yourself: since there is no computable way to generate a list of all computable reals does that mean that there is no non-computable ways of getting such a list? > This does not however prove that either is an uncountable > set; in fact the set of all computable numbers is > countable. > > >> >>>> I agree. It was Herc's deranged ramblings that brought >>>> computability >>>> into this discussion in the first place, when they >>>> really are >>>> completely irrelevant to Cantor's proof. >>>> >>> >> >>> Well, they are relevant if you try and make the mental >>> jump from >>> "cannot be listed" to "are therefore uncountable". This >>> simply does >>> not follow. >> >> It follows immediately from the definitions. You appear >> to have some >> bizarre definition of "list" that Cantor never used, >> employing >> concepts not developed until many decades later. >> > > No. And in fact Cantor's diagonal proof does not prove the > Reals are uncountable, just that they cannot be listed. > Which is all he claimed. No, because Cantor's diagonal argument applies to lists that are not computable as well as to lists that are computable. > In fact the computable Reals can't be listed either, using > exactly the same diagonal proof, but they are countable. No, computable reals can be listed but there is no computable algorithm that can generate such a list. But if you were given such a list then you could create an anti-diagonal number not on the list. That anti-diagonal, though, is non-computable since it is generated from a non-computable list. <-- But note, what I just wrote there applies to the algorithm in QUESTION 1, not the algorithm you use to generate the anti-diagonal. That is, the anti-diagonal algorithm, in the sense of which digits are changed on the diagonal (e.g. 9-->0, 1-->2, etc), is obviously computable. Please read: http://en.wikipedia.org/wiki/Computable_number >>> The computable Reals cannot be listed either, but they >>> are >>> definitely countable. >> >> The computable reals can be listed and are countable. >> >> >>> A Cantor construction applied to a purported list of all >>> computable >>> Reals will identify a computable Real not on the list. >> >> No, it will not. >> > > Yes, it will. > > Give me any list of computable numbers and I will produce > a computable number not on the list. All I have to do is > constrruct the diagonal number; this is clearly computable > (as the diagonal construction "computes" it), and its not > on the list. > > Go on, try it. If you think you have an explicit list of > all computable Reals, produce it for me. "Computing" the > anti-diagonal is easy. Yes it is, but there is no finite way of getting such a list (although each real in the list is generated by a finite algorithm). >>> The diagonal is explicitly constructible given the list. >> >> The definition of computable number does not include any >> presupposition of being supplied with infinite lists of >> infinite digit >> sequences. To be computable, a number must be >> constructible by a >> finite algorithm *without* being given the list. Don't >> take my word >> for it, look up the definition yourself. >> > > We are assuming every number on the list is computable; > that is the premise. > > You give me that list. Yes, every real in the list is computable. But ask yourself: is the function that maps each natural to each of these reals itself computable? _
From: Peter Webb on 18 Jun 2010 21:36 "Daryl McCullough" <stevendaryl3016(a)yahoo.com> wrote in message news:hvgk6k02j89(a)drn.newsguy.com... > Peter Webb says... > >>Cantor's diagonal proof does *not* show the Reals are uncountable; it just >>proves the much weaker statement that "the Reals cannot be listed". > > Those two statements mean the *same* thing! > > A "list" of objects is just a function that maps each natural number > to an object. To say that a set is listable is just to say that there > exists a list that contains all objects in the set. And that's exactly > what it means to say that a set is countable. > > -- > Daryl McCullough > Ithaca, NY > OK. The set of computable Reals. These are countable but cannot be listed. How does your definition handle that situation? It seems to me that the "problem" with computable Reals is that the set of computable Reals is not recursively enumerable. This means we cannot form a list that includes exactly the computable Reals, or that list would be an enumeration. Even though they are countable. That, BTW, is my own interpretation of what is happening. Whether you accept this or not, the simple fact is that Cantor's proof can be applied to any purported list of all computable Reals and used to generate a computable Real not on the list, but this does not prove that the computable Reals are uncountable; they are not. Similarly, you can't assume that just because you can't form a list of all Reals, they are uncountable. I suspect that Cantor's diagonal proof actually proves the set of Reals is either "not recursively enumerable" or "uncountable"; this would be consistent with the results of applying a diagonal proof to computable Reals.
From: Peter Webb on 18 Jun 2010 21:40
"Tim Little" <tim(a)little-possums.net> wrote in message news:slrni1o664.jrj.tim(a)soprano.little-possums.net... > On 2010-06-18, Peter Webb <webbfamily(a)DIESPAMDIEoptusnet.com.au> wrote: >> Now take the 3rd digit of the 3rd number ... its a "8", so the third >> digit >> of the diagonal number is a "1". >> >> Continue in this fashion. >> >> The number that is produced is clearly "computable", because we have >> computed it. > > I see you still haven't consulted a definition of "computable number". > No worries, let me know when you have. > > > - Tim I see that you have stopped responding to my arguments, and have employed the rather lame tactic of suggesting I look at definitions on the web. In the mean time, how about answering two questions for me: 1. Do you believe it is possible to create a list of all computable Reals? 2. Do you believe the computable Reals are countable? That at least will tell me what your problem is with my argument. |