> "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. Just because you can enumerate all items sold > in a supermarket does not neccesarily mean you can form a shopping > list; a shopping list is not just a list every item sold in > supermarkets, it is a specific list of exactly those items you need.
Fine, but changing the definitions of informal terms does not preserve the validity of an informal proof that uses those terms. You may not have intended to change the definition, but to anyone familiar with Cantor's diagonal argument it's usually apparent that "list" means "arbitrary function from N to ...".
> Thirdly, I already provided a definition of "listable" which is > equivalent to being recursively enumerable. If people try and redefine > terms to mean something different, then there are going to be > misunderstandings.
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?
-o
(Of course, if you *really* want to be picky, we can dig up Georg's own paper on the subject.)
