Why can no one in sci.math understand my simple point?
in [Logic]
|
From: Peter Webb on 1 Jul 2010 00:21 "Owen Jacobson" <angrybaldguy(a)gmail.com> wrote in message news:2010063022395694615-angrybaldguy(a)gmailcom... > On 2010-06-29 04:33:09 -0400, Peter Webb said: > >> "Owen Jacobson" <angrybaldguy(a)gmail.com> wrote in message >> news:2010062819564372407-angrybaldguy(a)gmailcom... >>> On 2010-06-28 02:16:28 -0400, Peter Webb said: >>> >>>> "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: >>>>>> 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". >>> >>> Here is a revised version with that error corrected: >>> >>> 1. Let S be the set {0, 1}^N. >>> 2. For any function L from N to S, there exists an element of S not in >>> the image of L. >>> 3. There exists an element d of S with the following property: for every >>> natural number x, the x'th element of d is equal to the x'th element of >>> L(x). >>> 4. Since d exists, there also exists an element d' of S with the >>> following property: 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? >> >> The proof as you have revised it is the proof that the cardinality of a >> powerset exceeds that of the set itself, for the special case where the >> set is N. > > That's all that Cantor's diagonalization proof demonstrates. > >> As I have already said several times, I have no problem with that proof, >> and no problem with card(P(N)) > card(N), from which the uncountability >> of the Reals follows immediately. My problem is with the standard >> presentation of Cantor's diagonal argument applied to decimal expansions. > > Ah. So, if we do away with informal wordings[0], your proposition > regarding computable reals also disappears? What proposition are you referring to? > Then I won't think about it any further, as it's obviously not a formal > mathematical argument. I'm still interested in the failure of > comprehension that lead to your proposition, though. Without you saying what the proposition was, obviously I can't respond. > >> This rather unfortunately starts off with a purported "list", and then >> proves no such list can exist. However, there are countable subsets of R >> which cannot be formed into an explicit list either. Proving that no >> explicit list can exist is not the same as proving uncountability. > > Various presentations have varying degrees of formality, and some of them > are informal enough to use the term "list" without first defining it, or > are taken out of context and given without definitions. Invariably[1], the > implied or omitted definition of "list of reals" is along the lines of "a > function from N to R", without regard to computability or any other notion > of being finitely describable. > Excepting that the standard presentation of Cantor's proof - and indeed your first attempt at reformulating it - does assume the list is known in advance sufficiently well that we can explicitly identify the nth digit of the nth item. >> I think that you have rather proved my point. You admit that your proof >> contains an error > > No, I admit that my presentation of it contained an error: specifically, I > was not formal enough to avoid specific misunderstandings. What is the difference between a "proof" and a "presentation of a proof" ? Do proofs have some kind of fixed existence independent of their presentation? > I made no changes to the structure of the proof; I only replaced wordings > like "we can identify" with more formal phrasings like "there exists". > Indeed, you changed your proof (or your presentation of the proof, if that is somehow a different thing) to eliminate exactly the problem I identified with the standard presentation of Cantor's proof. Given that you made and acknowledged exactly the same error as I identified in other presentations of Cantor's proof, it seems bizarre that you would attempt to claim the error doesn't occur - you yourself made the error, admitted it was an error, and posted a new version without the error. >> and you needed to change your proof to remove the explicit use of the nth >> digit of the nth decimal. > > I deny making any such change. You have interpreted my original wording in > a way that is incompatible with the corrected wording; however, the change > was only to remove this source of confusion. Others (thanks, Tim!) in this > thread would likely agree that both forms present the same argument, only > differing in pedanticness and formality. > > Note that the corrected version also explicitly mentions the well, x'th > element of L(x) when giving the properties of d. Why does the phrasing > > "There exists an element d of S with the following property: for every > natural number x, the x'th element of d is equal to the x'th element of > L(x)." > > not cause you to object, while the phrasing > > "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)." > > does? > >> In its common form, it proves that you cannot from an explicit list of >> Reals. This does not immediately mean that the Reals are uncountable; >> merely that they are not recursively enumerable. > > I don't understand how, given an argument that uses an undefined term > ("list"), you would reach the conclusion that it says anything about > recursive enumerability. Gee, as if I hadn't explained the connection a thousand times already. And you yourself made exactly the same error. Cantor's digit proof in its standard form: 1. Explicitly uses the value of the nth digit of the nth element, as you yourself did in your first go. 2. Proves that nobody can generate a list of all Reals. This does not prove uncountability; it proves that the Reals cannot be recursively enumerated. You can't form a list of all uncomputable Reals either, but they are countable. > Surely the strongest conclusion you can reach from such an argument is > "Therefore, no list contains every real... but what's a list?" > Well, we know what a "list" is Cantor's standard proof, because of the properties that are assumed for the list. A list is a mapping from N -> R such that the nth digit of the nth item is known. > Cheers, > > -o >
From: Aatu Koskensilta on 1 Jul 2010 00:27 "Peter Webb" <webbfamily(a)DIESPAMDIEoptusnet.com.au> writes: > Excepting that the standard presentation of Cantor's proof - and > indeed your first attempt at reformulating it - does assume the list > is known in advance sufficiently well that we can explicitly identify > the nth digit of the nth item. This is an example of the special mathematical use of "we can". Similar expressions abound -- "we now construct, using the axiom of choice...", "next we take the principal ultrafilter and..." and so on. When we say in mathematics that we can explicitly define or identify an object B given an object A we simply mean that we can give an explicit mathematical description of B in terms of A, with A as a parameter. There's no suggestion that we in fact could be given the object A, e.g. an infinite list, in any literal sense, or that would in any literal sense be able to produce B or an explicit description or definition of B. -- Aatu Koskensilta (aatu.koskensilta(a)uta.fi) "Wovon man nicht sprechan kann, dar�ber muss man schweigen" - Ludwig Wittgenstein, Tractatus Logico-Philosophicus
From: Peter Webb on 1 Jul 2010 01:03 "Aatu Koskensilta" <aatu.koskensilta(a)uta.fi> wrote in message news:87wrtfhln8.fsf(a)dialatheia.truth.invalid... > "Peter Webb" <webbfamily(a)DIESPAMDIEoptusnet.com.au> writes: > >> Excepting that the standard presentation of Cantor's proof - and >> indeed your first attempt at reformulating it - does assume the list >> is known in advance sufficiently well that we can explicitly identify >> the nth digit of the nth item. > > This is an example of the special mathematical use of "we can". Similar > expressions abound -- "we now construct, using the axiom of choice...", > "next we take the principal ultrafilter and..." and so on. When we say > in mathematics that we can explicitly define or identify an object B > given an object A we simply mean that we can give an explicit > mathematical description of B in terms of A, Except that the naive treatment of Cantor's diagonal proof - and indeed the reformulation I am criticising - the proof explicitly uses the nth digit of the nth item. > with A as a > parameter. There's no suggestion that we in fact could be given the > object A, e.g. an infinite list, in any literal sense, or that would in > any literal sense be able to produce B or an explicit description or > definition of B. > Well, it uses B's decimal expansion. Sounds pretty explicit to me. > -- > Aatu Koskensilta (aatu.koskensilta(a)uta.fi) > > "Wovon man nicht sprechan kann, dar�ber muss man schweigen" > - Ludwig Wittgenstein, Tractatus Logico-Philosophicus
From: Aatu Koskensilta on 1 Jul 2010 01:15 "Peter Webb" <webbfamily(a)DIESPAMDIEoptusnet.com.au> writes: > Except that the naive treatment of Cantor's diagonal proof - and > indeed the reformulation I am criticising - the proof explicitly uses > the nth digit of the nth item. There's nothing to criticize in the treatment in this respect. The statement you seem to object is Given a list A of reals we can explicitly define a real B not listed in A. where B is defined with reference to the decimal expansion of the reals in A. The definition of B is explicit in the sense that we can write down a formula for B in which A occurs as a parameter. But there is no suggestion that we could in general be given A in any literal sense, e.g. by means of a specific algorithm or explicit (parameter-free) definition, and consequently no suggestion the definition of B is in any literal sense explicit, or yields an algorithm. -- Aatu Koskensilta (aatu.koskensilta(a)uta.fi) "Wovon man nicht sprechan kann, dar�ber muss man schweigen" - Ludwig Wittgenstein, Tractatus Logico-Philosophicus
From: Ross A. Finlayson on 12 Jul 2010 05:07
On Jun 20, 1:57 am, "Ross A. Finlayson" <ross.finlay...(a)gmail.com> wrote: > On Jun 17, 10:30 pm, Tim Little <t...(a)little-possums.net> wrote: > > > > > On 2010-06-18, Ross A. Finlayson <ross.finlay...(a)gmail.com> wrote: > > > > The rationals are well known to be countable, and things aren't both > > > countable and uncountable, so to have a reason to think that > > > arguments about the real numbers that are used to establish that > > > they are uncountable apply also to the rationals, the integer > > > fractions, has for an example in Cantor's first argument, about the > > > nested intervals, that the rationals are dense in the reals, so even > > > though they aren't gapless or complete, they are no- where > > > non-dense, they are everywhere dense on the real number line. > > > As your sentence is less than coherent, I will merely point out that > > it is generally poor form to use 9 commas in a single sentence except > > when listing items. I will grant that parody often benefits from > > abuses of ordinary sentence structure, such as, for example, and not > > in any way showing that these are the only possible forms, sentences, > > like this one, which are convoluted to exhibit, by way of meandering, > > that they imply that mental processes, of the original writer, that > > is, which may be, perhaps, less than clear, and so in some way, to > > some readers, humourous. > > > - Tim > > Some I go back and add later. > > Too bad no one can read it but me. > > No seriously still it's clear in lots of ways, I can rewrite those > paragraphs as much longer. > > Sorry that was a bad joke. Collected, I'm very happy with the > output. Each one, in its own way, has some content. > > You don't agree with the rationals are dense on the line? > > The rationals are well known to be countable, and things aren't both > countable and uncountable, > so to have a reason to think that arguments about the real numbers > that are used to establish that they are uncountable apply also to the > rationals, the integer fractions, > has for an example in Cantor's first argument, about the nested > intervals, > that the rationals are dense in the reals, > so even though they aren't gapless or complete, > they are no- where non-dense, they are everywhere dense on the real > number line. > > The rationals are well known to be countable, > and things aren't both countable and uncountable, > so to have a reason to think that arguments about the real numbers > that are used to establish that they are uncountable > apply also to the rationals, > the integer fractions, > has for an example in Cantor's first argument, > about the nested intervals, > that the rationals are dense in the reals, > so even though they aren't gapless or complete, > they are no- where non-dense, they are everywhere dense on the real > number line. > > (The rationals > are well known to be countable, > and things aren't both countable and uncountable, so ) > to have a reason to think that arguments about the real numbers > that are used to establish that they are uncountable > apply also to the rationals, > the integer fractions, > has for an example in Cantor's first argument, > about the nested intervals, > that the rationals are dense in the reals, > so even though they aren't gapless or complete, > they are no- where non-dense, they are > everywhere dense > on the real number line. > (...) > > You left out the part before and after. > > Arguments about the uncountability of the real numbers include those > derived from the numeric property of their density. For example one > of them is called "Cantor's first argument for the uncountability of > the reals." > > The constructive (computable) sets are mappable to the countable > ordinals, where, the countable ordinals is the same thing as the > enumerative ordinals, because, they're each countable and that's all > of them. The constructive universe is complete, each in it countable, > but then the results of results are results so they are infinite and > their own powersets. (Sound familiar?) The existence of the > constructive universe is a result. > > Ha what's funny is you can still read them. > > Basically from having an idea to write a sentence, as it's written > then the parts of it are added automatically for, as you describe, > contemplative pause, as well as any emplacement of comment to provide > context generally. This is in the case where the writing is for a > particular medium, when there's a lot of writing back in forth (in > complete sentences, thank you) then to edit for readability is > deferred for real intent. But, there's not really a lot of writing > going on that way, rather, I much prefer the writing with the theme > and the content (on the mathematics). So, I read. > > Warm regards, > > Ross Finlayson Warm regards, why warm regards? We parse your posts, here I'm replying to myself. (It's OK.) No I'm just kidding, but this is great, this is a great medium of expression. (Excuse me, while I fix the previous sentence befi meidum -> medium of expression.) Well, thank you very much. Warm regards, Ross Finlayson |