Cantor Confusion
in [Math]
|
Prev: Pi berechnen: Ramanujan oder BBP
Next: Group Theory
From: William Hughes on 22 Jan 2007 09:36 mueckenh(a)rz.fh-augsburg.de wrote: > William Hughes schrieb: > > > mueckenh(a)rz.fh-augsburg.de wrote: > > > William Hughes schrieb: > > > > > > > > > > > The directions of the paths are the same in T1 and T2. If you insist on > > > > > a difference, then it can only result from the length of the paths. > > > > > > > > Yes. T1 contains only finite paths. > > > > > > Which path is finite? Where does a path end? > > > > Every path in T1 ends at a node. The fact > > that you can continue a path does not mean that you must continue > > a path. > > There is no path which ends at a node which you can specify. Every path > of the union tree has maximum length. 0.11 is not a path in the tree of > three or more levels. Since T1 is not a tree, you cannot use a statement about the properties of of a tree to say something about the properties of T1. 0.11 is a path in T1. > > Define "the maximum set" as the union of > > {1}, {1,2}, {1,2,3}, ..., {1,2,3,...,n} > "the maximum set" is different for every n. > It is obviously nonsense to assert that every maximum set ends > somewhere, because there is only one maximum set which ends at n. There are lots of different n so there are lots of different maximum sets. Each different maximum set ends some n. > > > > > > > > > > > T2 contains only > > > > (potentially) infinite paths. > > > > > > > > > > > The paths in T1 are not determined by the nodes in T1. > > > > > > > > > > By its nodes and edges every path is determined. > > > > > > > > Yes, but the fact that these nodes and edges are in T1 > > > > does not mean the path determined by these nodes > > > > and edges in in T1. > > > > > > Even if the paths are in T1 this does not mean that the paths are in > > > T1, I assume? > > > > You assume wrong. > > > > The statement was that even if the nodes and edges of > > path P1 are in T1, this does not mean that path P1 is in T1. > > This statement is wrong. According the definition of a path in the > trees defined by me, the nodes and edges determine it completely. > If you don't believe it, take it as a definition. I do take it as the definition of a tree. However, as T1 is not a tree, this definition is not relevant .. > > > > More formally. T1 is the union of all finite paths. Let M be the > > set of nodes in T1, (that is if a node m is in M, then there is a > > path p(m) in T1, such that the node m is in p(m)). > > > > Let p1 be a (potentially) infinite path. Then > > > > Every node in p1 is contained in some path > > in T1. > > The infinite union of all finite trees can only contain nodes which are > in a path. Otherwise the nodes could not enter the union. Nodes are > ends of paths of finit trees. And therefore every node in p1 is contained in some path in T1. This is not enough to show that p1 is contained in T1. > > > > However > > > > There is no path in T1 that contains every node in p1 > > Then not every node of T1 is in T1. No. Every node in p1 is contained in T1, however, you need more than one path in T1 (indeed an infinite number of paths) to get every node in p1. > > > > Proof: > > > > Let a path in T1 that contains every node in p1 be called L_D > > > > L_D is in T1 so L_D is finite. > > > > L_D contains every node in p1, so L_D is (potentially) infinite. > > > > Contradiction. Therefore L_D does not exist. > > Let P be in the union of all intial segments {1,2,3,...,n} of N. You keep changing your mind about whether the set N is an initial segment of N. To be clear let us define P to the union of all initial segments which have a fixed maximum. > There is no initial segment P of N which contains all natural numbers. > Therefore the union of all P (which is N) does not exist? No. To have the union of all P to be N it is necessary that for any natural number n, there is an initial segment p(n) such that p(n) contains n. It is not necessary that p(n) be the same segment for every n. > > You make the following error: > A node cannot enter the union tree unless it belongs to a path. > If there is not one finite tree containing all nodes, then not all > nodes can be in the union of all finite trees. This implies that the > complete infinite tree contains more nodes than the union of finite > trees. > I have stated many times that the union of finite trees contains the same nodes as the infinite tree. The union of finite trees is not a tree. The fact that it contains the same nodes as the infinite tree does not mean that it contains the same paths as the infinite tree. - William Hughes
From: Andy Smith on 22 Jan 2007 09:41 Another stupid question. Possibly this has already been answered to me, but if so, I have forgotten and lost the thread (literally, on my pc). Re Cantor's diagonalisation argument. 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. That argument is not very satisfactory, because the number we construct has a magnitude of order 2^n given only n elements in the list, so I can see that an extrapolation to an infinite case might be unreasonable. 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). I am very aware that David Marcus and others will shout loudly at this point "do not extrapolate reasoning about finite sets to infinite sets" (which I wholly understand). 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. But it isn't clear to me that such a line of argument is valid ( "do not extrapolate reasoning about finite sets to infinite sets") ? -- Andy Smith
From: Dave Seaman on 22 Jan 2007 10:13 On Mon, 22 Jan 2007 14:41:45 GMT, Andy Smith wrote: > Another stupid question. Possibly this has already been answered to me, > but if so, I have forgotten and lost the thread (literally, on my pc). > Re Cantor's diagonalisation argument. > 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, you can't. You can construct an infinite bit string that is not in the list, but that bit string will necessarily contain infinitely many 1's and therefore does not represent an integer. > That argument is not very satisfactory, because the number we construct > has a magnitude of order 2^n given only n elements in the list, so I can > see that an extrapolation to an infinite case might be unreasonable. > 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. The difference is that when you apply the Cantor diagonal argument to a list of real numbers, you get a real number not in the list. When you apply a similar argument to a list of integers, you do not get an integer at all. > But it isn't clear to me that such a line of argument is valid ( "do not > extrapolate reasoning about finite sets to infinite sets") ? In this case, it would be the reasoning that every finite bit string represents an integer. We can show that it works for the reals by invoking the fact that every Cauchy sequence of rationals converges to some real number, but there is no corresponding fact for the integers. -- Dave Seaman U.S. Court of Appeals to review three issues concerning case of Mumia Abu-Jamal. <http://www.mumia2000.org/>
From: Andy Smith on 22 Jan 2007 10:28 Dave Seaman writes >On Mon, 22 Jan 2007 14:41:45 GMT, Andy Smith wrote: >> Another stupid question. Possibly this has already been answered to me, >> but if so, I have forgotten and lost the thread (literally, on my pc). > >> Re Cantor's diagonalisation argument. > >> 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, you can't. You can construct an infinite bit string that is not in >the list, but that bit string will necessarily contain infinitely many >1's and therefore does not represent an integer. > I was only proposing modifying bits 0-(n-1) in a list of n integers, not generating "numbers" ...111" (we have had that discussion, and I have accepted that these are not meaningful). >> That argument is not very satisfactory, because the number we construct >> has a magnitude of order 2^n given only n elements in the list, so I can >> see that an extrapolation to an infinite case might be unreasonable. > >> 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. > >The difference is that when you apply the Cantor diagonal argument to a >list of real numbers, you get a real number not in the list. When you >apply a similar argument to a list of integers, you do not get an integer >at all. Even if you truncate the exercise at the nth bit? > >> But it isn't clear to me that such a line of argument is valid ( "do not >> extrapolate reasoning about finite sets to infinite sets") ? > >In this case, it would be the reasoning that every finite bit string >represents an integer. We can show that it works for the reals by >invoking the fact that every Cauchy sequence of rationals converges to >some real number, but there is no corresponding fact for the integers. > > > OK, understand that re the reals, but not necessarily about validity of reasoning over a hypothetically infinite list, nor about the integer case - you don't have to try to generate numbers like ...111 not to be on the list of n integers (indeed , n+ 1 will do as number not in the list). So for integers, the argument goes - let there be a 1:1 correspondence between the set of all integers and itself. Construct a numbered table of all integers that is complete. But we can create a new number not in the list, so such a list cannot be constructed, therefore there is no 1:1 correspondence between the integers and themselves? -- Andy Smith Phoenix Systems Mobile: +44 780 33 97 216 Tel: +44 208 549 8878 Fax: +44 208 287 9968 60 St Albans Road Kingston-upon-Thames Surrey KT2 5HH United Kingdom
From: Fuckwit on 22 Jan 2007 10:44
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 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.) F. |