Cantor Confusion
in [Math]
|
Prev: Pi berechnen: Ramanujan oder BBP
Next: Group Theory
From: Andy Smith on 22 Jan 2007 13:36 Fuckwit writes >On Mon, 22 Jan 2007 14:41:45 GMT, Andy Smith ><Andy(a)phoenixsystems.co.uk> wrote: > >> >> Suppose you set out the integers progressively (as e.g. bit patterns) >> >> 1 0000 >> 2 0001 >> 3 0011 >> 4 0100 >> 5 0101 >> 6 0110 >> 7 0111 >> 8 1000 >> >> etc, filling leading zeros when required. Then given n entries in the >> list we can always define a new number not in the list so bit 0 is != to >> bit 0 in entry 1 and so on. So from an infinite hypothetically complete >> list we can construct a new natural number not in the list. >> >No, we can't. > >In the infinite case we would have, say, the following list: > > ...0000 > ...0001 > ...0010 > ...0011 > ...0100 > : > >Note that a natural number (by definition) only has _finitely_ many >digits =/= 0. > >Now consider the list above: the sequence of digits in the diagonal >(top - down) is > > 0 0 0 0 ... > >Hence the sequence of altered digits would be > > 1 1 1 1 ... > >An infinite sequence of digits =/= 0. Hence this is not (the >representation of) a natural number. > But, with respect, m'lud, can't I have as many bits as there are rows in the table? I'm not saying that Cantor is wrong, and anyway, I can well believe that the reals are uncountable. I am just trying to clarify for myself why Cantor's line of argument is valid when the above isn't (you clearly can place the natural numbers in a 1;1 correspondence with themselves !). >> >> But why is Cantor's argument valid but such a construction (or variants >> of it) invalid? Cantor's argument goes, as I understand it : construct >> a hypothetical table of all the reals (in [0,1) , defined for the sake >> of argument as a infinite bit patterns from .000.. to .111.. . Assume >> that this is a complete list - then show that E a number not in the >> list, therefore you cannot have such a list. >> >Cantor's argument doesn't work for natural numbers, because in this >case it's not guaranteed that the "diagonal" delivers a natural >number. (You might compare that with Cantor's argument concerning a >list of real numbers with decimal representation.) > Thanks. I'm thinking about it. -- Andy Smith
From: David Marcus on 22 Jan 2007 13:38 mueckenh(a)rz.fh-augsburg.de wrote: > Virgil schrieb: > > > Cantor, using his original diagonal argument, and anyone else who wants > > to emulate him, can show that any /list/ of paths in a complete infinite > > binary tree is incomplete. > > So you do not believe in complete trees? Somewhere in the mist of > infinity the paths cease to split, or become unobservable? That is a > possible point of view to avoid inconsistencies. An even better point > of view would be not to believe in complete infinite sets of digits of > real numbers and of complete diagonals of infinite lists. Somewhere in > the mist of infinity ... You appear to have ignored Virgil's "/list/" in your reply. If we change your first sentence to "So you do not believe in complete /lists/ of paths in infinite binary trees", how would you continue your paragraph? -- David Marcus
From: Andy Smith on 22 Jan 2007 13:42 Dik T. Winter writes >In article <uC3ofBOf0MtFFwCD(a)phoenixsystems.demon.co.uk> Andy Smith ><Andy(a)phoenixsystems.co.uk> writes: >... > > But with a finite list of n entries we can always define the number e.g. > > 2^n which is not in the list. So for an infinite list of natural numbers > > of size n we can always construct a number not in the list (trivially true > > anyway because any natural number has a successor). > >This is wrong. With an infinite list you get a string of digits of an >infinite length. But each natural number has a finite number of digits, >and so the constructed string does not represent a natural number. OK, thanks, maybe that gets to the heart of my misunderstanding. If we write numbers in their simplest form e.g 0 = 0 1 = s0 2 = ss0 n = n s's 0 we can never have an infinite number of s's, is what you are saying? -- Andy Smith
From: Fuckwit on 22 Jan 2007 14:10 On Mon, 22 Jan 2007 18:36:15 GMT, Andy Smith <Andy(a)phoenixsystems.co.uk> wrote: > > But, with respect, m'lud, can't I have as many bits as there are rows in > the table? > Sure you can. So what? > > [...] I am ... trying to clarify for myself why Cantor's line of > argument is valid when the above isn't. > I repeat myself: "Cantor's argument doesn't work for natural numbers, because in this case it's not guaranteed that the "diagonal" delivers a natural number. (You might compare that with Cantor's argument concerning a list of real numbers with decimal representation.)" To make a long story short: (a) List of (representations of) real numbers => diagonal delivers a real number (which -as it turns out- is not in the list). (b) List of (representations of) natural numbers => diagonal doesn't delivers a natural number. (Hence the diagonal argument does not apply.) Clear enough? F.
From: Fuckwit on 22 Jan 2007 14:15
On Mon, 22 Jan 2007 18:42:11 GMT, Andy Smith <Andy(a)phoenixsystems.co.uk> wrote: > > If we write numbers in their simplest form e.g. > > 1 = s0 > 2 = ss0 > : > In general: If n e IN, then n = s...s0. ----- finite many s's Hence "we can never have an infinite number of s's", right. F. |