Why can no one in sci.math understand my simple point?
in [Logic]
|
From: Peter Webb on 21 Jun 2010 02:28 "Tim Little" <tim(a)little-possums.net> wrote in message news:slrni1tm56.jrj.tim(a)soprano.little-possums.net... > On 2010-06-21, Peter Webb <webbfamily(a)DIESPAMDIEoptusnet.com.au> wrote: >> The same algorithm does work for all n. Look at the first n terms to >> n places of accuracy. > > Provide computer code, please. Here's the required function > signature: int getDigit(BigInteger n). You get to fill in the > function body. > > >>> For some fixed M, you could embed M digits of the diagonal into the >>> algorithm, and the algorithm would work for all n < M. But that's not >>> enough: it has to work for all n. >> >> I can in fact compute the nth digit of the anti-diagonal for any n >> by hand. > > "By hand" is irrelevant to the definition of a computable real, > especially when your "hand" is connected to "eyes" that have the list > as input. The list is *not* input to the algorithm. > Yeah, it is. Cantor constructs the antidiagonal by taking the list and then computing a missing Real based upon the decimal expansion of every Real on the list. > >> The same objection could be raised to Cantor's proof; after all, he >> accepts a purportedly infinite list as input to his algorithn as >> well. > > Cantor does not claim to be proving existence of any finite algorithm. > You are. > Cantor explicitly calculates the real that is missing be examining the decimal expansion of every item in the list. No more or less than I do. > >> Or are you saying I have to do this without using the infinite list >> itself? > > You may use the infinite list to determine which finite algorithm to > use, but the algorithm must be self-contained and not refer to the > list. Not in Cantor's proof. He explicitly uses the decimal expansion of every Real on the list to construct the anti-diagonal. Of course Cantor has know what's on the list to determine an element which is missing. In exactly the same way as I do. > The *only* input to the algorithm you select will be a natural > number, which denotes n. > > >> I note that Cantor's original proof also requires an infinite list >> of Reals, but you seem to have no problem with that. > > Indeed I don't. Cantor is not claiming that the antidiagonal is a > computable real, and so finite algorithms are irrelevant. > Yet he explicitly constructs the missing Real to arbitrary accuracy. > You *are* claiming that the antidiagonal is a computable real, and so > you must prove the existence of a suitable finite algorithm for the > antidiagonal. > Actually, I only need to be able to specify it to arbitrary accuracy for it to be computable, and I can certainly do that. Or are you trying to claim that while I can calculate the explicit decimal expansion of the missing computable Real, I can't compute the missing computable Real itself? If I can compute every digit in the missing computable number, I have computed the number itself. > > - Tim
From: Peter Webb on 21 Jun 2010 02:33 "Owen Jacobson" <angrybaldguy(a)gmail.com> wrote in message news:2010062100324493978-angrybaldguy(a)gmailcom... > On 2010-06-19 22:31:56 -0400, Peter Webb said: > >> Cantor's original proof requires the list to be provided in advance > > No, it does not. It's an existence proof showing that: > > IF a list of reals L(x) (where L : N -> R) exists, THEN a real A_L exists > such that for every natural number n, L(n) ≠ A_L. > > Or, equivalently, showing that: > > For every function L from N to R, there exists a real r not in the image > of L. > > Being a constructive proof, it's usually *presented* as if it were an > algorithm or a procedure, but it's only for ease of comprehension. Umm, I am talking about Cantor's proof as it is generally presented, and in that case it is an explicit algorithm. > Unfortunately, that seems to have backfired on you. > So you are saying that Cantor's proof in its usual form is incorrect, as it pretends to include an algorithmic process for computing the anti-diagonal? > -o > > Incidentally, "countable" and "listable" mean the same thing in > conventional set theories: an infinite set S is countable if and only if > there exists an surjective function f from N to S. Since a "list" of > elements of S is most easily formalized as a surjective function from N to > S, denying that S is listable is equivalent to denying that it is > countable. > The existence of a surjective function from N to S proves it is countable. The ability to prepare a list of exactly the elements proves the list is recursively enumerable. If you cannot form the list, you have proved that it is not recursively enumerable. This is a somewhat weaker condition that it being uncountable.
From: Virgil on 21 Jun 2010 02:48 In article <4c1f04e8$0$14086$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:slrni1tmi9.jrj.tim(a)soprano.little-possums.net... > > On 2010-06-21, Peter Webb <webbfamily(a)DIESPAMDIEoptusnet.com.au> wrote: > >> "Tim Little" <tim(a)little-possums.net> wrote in message > >>> On 2010-06-21, Peter Webb <webbfamily(a)DIESPAMDIEoptusnet.com.au> wrote: > >>>> No, I only need a finite algorithm which will calculate it to n > >>>> decimal places with finite input. > >>> > >>> You have previously stated that you can do this with "about three > >>> lines of Java code". > >>> > >>> Here's your Java method signature: int antidiagonalDigit(BigInteger n). > >>> > >>> Here are the first twenty digits of the first twenty members of my > >>> list: > >>> > >>> 93525532854532512838 > >>> 32127313472944276266 > >>> 70595916184994935423 > >>> 20733652719572401688 > >>> 30472031767118774150 > >>> 47190325821263633948 > >>> 74236814853458351851 > >>> 58521903865615844550 > >>> 91701104659863267390 > >>> 39510921669610680229 > >>> 19656091025330568974 > >>> 49591084533660072011 > >>> 81683520683673830124 > >>> 93720622611168810054 > >>> 50284245443806050152 > >>> 11702670934156383526 > >>> 58534679962278312978 > >>> 68478827933494896765 > >>> 83579375050000862329 > >>> 50241229144880453593 > >>> > >>> Now let's see your Java code. > >> > >> Here is my p-code. > > > > As I suspected, your claim that you could actually do it was pure > > puffery, and you probably know as little about programming as you do > > about mathematics. > > > > > >> Take the nth digit of the nth item. > > > > The n'th item of *what*? > > The list. Of computable Reals. That is supposed to include all Computable > Reals. > > > The list is not a parameter, it is not a > > global variable, it is completely out of scope. You fail already. > > > > > > Actually, Cantor's proof starts with a purported list of all Reals, and then > shows that at least one Real is missing. Technically, it isn't Cantor's proof at all, as the only real Cantor diagonal proof is not about reals but about binary sequences. > > It assumes that a list exists, then shows a Real is missing. If you didn't > supply the list in advance, he wouldn't be able to construct a Real missing > from the list. In fact, if you don't say what is on the list, it you can't > prove soimething is missing from it. There is no Real which is missing from > every list, but every list misses at least one Real. > > You do believe Cantor's original proof that the Reals cannot be listed, > don't you? > > > > - Tim
From: Tim Little on 21 Jun 2010 03:35 On 2010-06-21, Virgil <Virgil(a)home.esc> wrote: > Technically, it isn't Cantor's proof at all, as the only real Cantor > diagonal proof is not about reals but about binary sequences. Indeed. In fact it would be a lot easier if instead of reals, we talked about sets of natural numbers, and instead of computable reals, we talked about recursively enumerable sets of natural numbers. The diagonal proof for the uncountability of P(N) is very much simpler, and so there are fewer distractions from the core idea. It is also much closer to Cantor's original proof. This might help to prevent some of the extraneous confusions Peter has about computable reals, and would help focus on his *central* confusions. - Tim
From: WM on 21 Jun 2010 05:49
On 20 Jun., 21:55, Virgil <Vir...(a)home.esc> wrote: > > The reals in a certain Cantor-list are countable. And if you form the > > anti-diagonal of that list and add it (for instance at first position) > > to the list, this new list is also countable. Again construct the > > anti-diagonal and add it to the list. Continue. The situation remains > > the same for all anti-diagonals you might want to construct. Therefore > > all reals constructed in that way are countable. Nevertheless it is > > impossible to put all of them in one list, because there would be > > another resulting anti-diagonal. > > > Conclusion: It is impossible to obtain a bijection of all these reals > > with N although all "these" reals are countable with no doubt. > > Equal cardinality of two sets requires, by definition, a bijection > between them. > > The naturals are, by definition of COUNTABLE cardinality so that any set > of equally countable cardinality must have a bijection with the > naturals. But the set of all diagonals constructed according to the scheme given above is countable but cannot be listed. > > Cantor has shown that the set of all reals cannot biject with the > naturals, ergo, the set of all reals is NOT of countable cardinality. The same proof shows that some countable sets are of not countable cardinality. But you prefer not to think about that? Regards, WM |