Why can no one in sci.math understand my simple point?
in [Logic]
|
From: Peter Webb on 27 Jun 2010 22:59 "Owen Jacobson" <angrybaldguy(a)gmail.com> wrote in message news:2010062722302771524-angrybaldguy(a)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". I provided a definition. Others want to define it differently. > 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". 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. 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. > You're free to involve recursive enumerability in your definition if you > like, but be prepared for misunderstandings. You are addressing your criticism to the wrong person. "Listable" is not (AFAIK) a technical term with a well defined meaning. I provided a meaning. It is other people who want to redefine the term to simply mean "countable". They should use the term "countable" if they mean "countable". My definition of "listable" is not the same as countable. They are different concepts. For example, computable Reals are countable but not listable. Re-defining a term to mean something different is clearly going to cause problems. > > -o > > [0] See for example <2010062122134453246-angrybaldguy(a)gmailcom>. >
From: Owen Jacobson on 28 Jun 2010 00:14 On 2010-06-27 22:59:12 -0400, Peter Webb said: > "Owen Jacobson" <angrybaldguy(a)gmail.com> wrote in message > news:2010062722302771524-angrybaldguy(a)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.)
From: Virgil on 28 Jun 2010 00:50 In article <4c281047$0$24370$afc38c87(a)news.optusnet.com.au>, "Peter Webb" <webbfamily(a)DIESPAMDIEoptusnet.com.au> wrote: > "Owen Jacobson" <angrybaldguy(a)gmail.com> wrote in message > news:2010062722302771524-angrybaldguy(a)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". > > I provided a definition. Others want to define it differently. > > > > 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". > > 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. > > 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. Since we already have "recursively ennumerable" to mean "recursively ennumerable", just as we already have "countable" to mean "countable", there is certainly no more point in having "listable" mean "recursively ennumerable" than in having it mean "countable". Therefore I shall continue to regard "listable" and "countable" as synonymous.
From: Peter Webb on 28 Jun 2010 02:16 "Owen Jacobson" <angrybaldguy(a)gmail.com> wrote in message news:2010062800145641786-angrybaldguy(a)gmailcom... > On 2010-06-27 22:59:12 -0400, Peter Webb said: > >> "Owen Jacobson" <angrybaldguy(a)gmail.com> wrote in message >> news:2010062722302771524-angrybaldguy(a)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? > Hmmm. This proof assumes that the function L is in fact computable, and that the function can be explicitly defined. This occurs in step 4. You state we can "identify an element d of S that is on the diagonal". Unless the list is explicitly defined, you can't "identify" the digit in position x. (Actually, its slightly weaker; you only need to know the xth digit of every term, not all digits, but this doesn't alter the substance of my argument). However, in answer to your question, I would insert the word "computable" before the word "function" in step 2. > -o > > (Of course, if you *really* want to be picky, we can dig up Georg's own > paper on the subject.) > As I have stated on several occasions, I have no problem with the uncountability of the Reals. The powerset of a non-empty set has larger cardinality than the set itself; so card(P(N))>card(N). The problem I have is with the standard/common presentation of Cantor's diagonal proof using digits. This starts with a purported "list", and explicitly uses the values of each item in the list. It then proves no such list can exist. This does not prove uncountability, it proves you cannot explicitly form a list. This may be because the set is uncountable, or it may be because the set is countable but not recursively enumerable, as is the case with computable numbers.
From: Virgil on 28 Jun 2010 02:29
In article <4c283e85$0$14086$afc38c87(a)news.optusnet.com.au>, "Peter Webb" <webbfamily(a)DIESPAMDIEoptusnet.com.au> wrote: > "Owen Jacobson" <angrybaldguy(a)gmail.com> wrote in message > news:2010062800145641786-angrybaldguy(a)gmailcom... > > On 2010-06-27 22:59:12 -0400, Peter Webb said: > > > >> "Owen Jacobson" <angrybaldguy(a)gmail.com> wrote in message > >> news:2010062722302771524-angrybaldguy(a)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. |