In article <4c283e85$0$14086$afc38c87@news.optusnet.com.au>, "Peter Webb" <webbfamily@DIESPAMDIEoptusnet.com.au> wrote:
> "Owen Jacobson" <angrybaldguy@gmail.com> wrote in message > news:2010062800145641786-angrybaldguy@gmailcom... > > On 2010-06-27 22:59:12 -0400, Peter Webb said: > > > >> "Owen Jacobson" <angrybaldguy@gmail.com> wrote in message > >> news:2010062722302771524-angrybaldguy@gmailcom... > >>> On 2010-06-27 08:24:15 -0400, Peter Webb said: > >>> > >>>> AFAIK, "listable" is not a formally defined mathematical term. > >>> > >>> This could be because every time someone presents you with a clear, > >>> concise definition you don't happen to like, you stop replying to > >>> them[0]. > >>> > >> > >> As I have said before, AFAIK there is no accepted definition of > >> "listable". > > > > Perhaps not, but as you're trying to make a point about Cantor's diagonal > > proof, you should use a definition that's compatible with the actual > > proof. "List" is a bit of verbal shorthand for "function from N to some > > set" in most presentations of his proof. In a completely formal > > presentation, it would either be defined in the proof, have a definition > > referenced from elsewhere, or avoided entirely for exactly this reason. > > > >>> The definitions you've been presented with numerous times *just in this > >>> thread* are all variations on "a list of elements of some set S is a > >>> surjective function L from N (the natural numbers) to S." > >> > >> The definitions I have seen are all equivalent to "countable". These are > >> not good definitions for three reasons. > >> > >> Firstly, we already have a perfectly good word which means "there exists > >> a surjection from N to the set" which everybody knows, and it is > >> "countable". > > > > "Countable" only says that a mapping from N to S exists. "A list" in this > > sense is a specific (but arbitrary) mapping from N to S; we can talk about > > a specific list, or all lists, or we can prove that no complete list > > (surjective mapping) exists. It's shorter than writing out "a mapping from > > the natural numbers to S" every single time. > > > >> Secondly, the definition I proposed for "listable" is far more in accord > >> with common usage.
Only in your own opinion, not in mine!
> >> Thirdly, I already provided a definition of "listable" which is > >> equivalent to being recursively enumerable.
If one already has a definition for "recursively enumerable", what is the point? > > > > Then let's do away with the word entirely, for the sake of understanding. > > > > To recap: I believe your point to be that we can add the word "computable" > > to "real" in Cantor's diagonal argument and arrive at the conclusion that > > the computable reals are either uncountable or not recursively enumerable > > (it's unclear which). To do this, you use an informal presentation of > > Cantor's diagonal argument which uses the word "list". So, here is an > > informal presentation of Cantor's diagonal argument that avoids the word > > "list" (as well as a few other common verbal shortcuts): > > > > 1. Let S be the set {0, 1}^N. > > 2. For any function L from N to S, we can identify an element of S not in > > the image of L. > > 3. To do so, we identify an element d of S that is the diagonal of L: for > > every natural number x, the x'th element of d is equal to the x'th element > > of L(x). > > 4. Given d, we can identify an element d' of S that is the anti-diagonal > > of L: for every natural number x, the x'th element of d' is 1 if the x'th > > element of d is 0 and is 0 if the x'th element of d is 1. > > 5. Since for every natural number x, L(x) differs from d' at the x'th > > place, d' is not in the image of L. > > 6. Therefore no function from N to S is surjective. > > > > Where should we insert the word "computable" (or the term "recursively > > enumerable") to arrive at your argument? > > > > Hmmm. This proof assumes that the function L is in fact computable, and that > the function can be explicitly defined.
Not at all. One can give a rule which applies to an arbitrary list regardless of the particular items being listed. This is, in fact, done in Cantor's original diagonal proof (with binary strings from {m,w} rather than decimals.
It does not require that any element in the listing be known, but correctly tells what to do for any listing, computable or not.
