Cantor Confusion
in [Math]
|
Prev: Pi berechnen: Ramanujan oder BBP
Next: Group Theory
From: MoeBlee on 30 Jan 2007 16:54 On Jan 30, 1:46 pm, "MoeBlee" <jazzm...(a)hotmail.com> wrote: > showing that for every interval there is a diagonal method to > construct a real not in that interval. Correction, should be: showing that for every interval there is a diagonal method to construct a real in that interval but not on the list.
From: Virgil on 30 Jan 2007 17:00 In article <1170187343.409722.8620(a)a34g2000cwb.googlegroups.com>, "MoeBlee" <jazzmobe(a)hotmail.com> wrote: > On Jan 29, 10:33 pm, David Marcus <DavidMar...(a)alumdotmit.edu> wrote: > > MoeBlee wrote: > > > On Jan 27, 2:26 pm, Andy Smith <A...(a)phoenixsystems.co.uk> wrote: > > > > > > The maximum number of bits required to describe any index no. i is > > > > ceiling(log(i+1,base 2)). For all i>0, i+1> ceiling(log(i+1,base 2)). > > > > And for i = 0, the real number is 0.000 . So, all terms on the diagonal > > > > are 0 (and, more of this later, the distance in bits between the 0 on > > > > the diagonal and the first non zero bit goes as (n - log(n,base2)) for > > > > bit n. > > > > > > Following Cantor, we construct an antidiagonal number, different from > > > > the first row, the second row, etc. Because all the diagonal terms are > > > > 0, we construct the number .1111.... > > > > > > This string is certainly not in the hypothetically complete list, but it > > > > is a real number and = 1.000... , which was excluded anyway from our > > > > initial list. So we can make no inference that the list is > > > > incomplete/invalid - we have just generated a number. > > > > > What you've shown is that applying the diagonal method to your list > > > only shows a real number not in [0 1). So what? It doesn't contradict > > > that for any list of real numbers, there is a real number not in the > > > list. We don't have to prove: For any list of real numbers in a > > > certain interval, there is a real number in that interval not listed. > > > Rather, we only have to prove: For any list of real numbers, there is > > > a real number not in the list. > > > > The usual diagonal proof proves that [0,1) or [0,1] (depending on how we > > do it) is uncountable. > > So, the fact that the anti-diagonal is in the > > specified interval is important in the usual proof. The main problem > > with Andy's argument is that he is using a specific list. > > My point still stands: If one gives a list of real numbers in a given > interval and shows that the anti-diagonal of that list is not in that > interval, then one has not thereby refuted the uncountability of the > reals that is proven without reference to that particular list, > interval and anti-diagonal. > > MoeBlee If one can show a bijection between that interval and the set of all reals (which one can do quite easily) and one can also show that the "anti-diagonal" constructed must fall within the interval (which one can also do quite easily), the proof stands.
From: MoeBlee on 30 Jan 2007 17:17 On Jan 30, 2:00 pm, Virgil <vir...(a)comcast.net> wrote: > If one can show a bijection between that interval and the set of all > reals (which one can do quite easily) and one can also show that the > "anti-diagonal" constructed must fall within the interval (which one can > also do quite easily), the proof stands. Of course I don't disagree with that. Only, that just to show the uncountability of the reals, we don't even need to show a bijection between the interval and the set of reals. If a subset of the set of reals is uncountable, then the set of reals is uncountable. MoeBlee
From: David Marcus on 30 Jan 2007 17:42 Andy Smith wrote: > Andy Smith <Andy(a)phoenixsystems.co.uk> writes > > > >Am I right in thinking that any set of "finitely describable" objects > >is necessarily countable? - on the grounds that "finitely describable" > >implies that there exists some (multi-dimensional) address space which > >uniquely defines an object, and that that address is indexable by a > >finite set of natural numbers, and then that that multi-dimensional > >address (as with the "standard arrangement" for counting the rationals) > >can be ordered such that each address has a unique index in the natural > >numbers? > > > >On that basis I would surmise that e.g. the set of all roots of all > >polynomials with rational coefficients are countable - is that correct? > > I just googled that, and got the answer that Cantor showed that the > finite union of countable sets is also countable, and hence that e.g. > the set of all roots of all polynomials with rational coefficients are > countable. How is that a finite union of countable sets? I think you mean that Cantor showed that a countable union of countable sets is countable. This is the same as showing that Q is countable. -- David Marcus
From: David Marcus on 30 Jan 2007 17:48
MoeBlee wrote: > On Jan 30, 1:17 pm, Dave Seaman <dsea...(a)no.such.host> wrote: > > > I disagree. The version of the diagonal proof that I have in mind is > > applied to [0,1), not to R. When correctly presented, the proof shows > > that there is a number in [0,1) that is not in the given list. The > > conclusion is that [0,1) is uncountable, and therefore R is uncountable. > > > > Andy's mistake was in using an incorrect version of the diagonal proof. > > I understand your point, but I am noting that there is also a mistake > in logic even more fundamental. > > The diagonal proof can be used to apply to certain intervals or to the > entire set of real numbers, as the argument is variously formulated. Can't say I've ever seen it applied to the entire set of reals, although of course we could do it that way. -- David Marcus |