Cantor Confusion
in [Math]
|
Prev: Pi berechnen: Ramanujan oder BBP
Next: Group Theory
From: mueckenh on 16 Jan 2007 09:50 Dik T. Winter schrieb: > In article <1168870204.087161.242050(a)m58g2000cwm.googlegroups.com> mueckenh(a)rz.fh-augsburg.de writes: > > Dik T. Winter schrieb: > > > In article <1168533543.556066.104940(a)p59g2000hsd.googlegroups.com> mueckenh(a)rz.fh-augsburg.de writes: > > > > Dik T. Winter schrieb: > > > ... > > > > > > But you do not see this small difference. You > > > > > > claim that the union of all finite numbers or of all finite initial > > > > > > segments {1,2,3,...,n} is the infinite set {1,2,3,...}. > > > > > > > > > > Elaborate on the difference. > > > > > > > > Why do you see it different in case of the union of all finite trees or > > > > paths? > > > > > > I am not talking about unions of paths. I am talking about unions of > > > *sets* of paths. That is something completely different. > > > > But it is quite irrelevant, because every path of the set of infinit > > paths is a union of finite segments of paths. There are only countably > > many sequences. > > Whether there are only countably many sequence remains to be decided (I say: > no), Every path is a sequence. There are no sequences which are not paths. > but, yes, a set of paths is a set of unions of segments. The union of > a collection of sets of paths is also a set of unions of segments. But > conside a, b and c three segments. Define p1 = union(a, b) and > p2 = union(a, b, c). Further define s1 = {p1} and s2 = {p2}. In that case: > union(s1, s2) = {p1, p2} = {union(a, b), union(a, b, c)}; > no further simplification is possible. It is *not* equal to s2. If you unite levels of trees, then the union is not the greater level. But if you unite all nodes of trees, then the union is the greater tree. > > > > But the sets of the paths in the finite trees do *not* contain infinite > > > sequences, and so the union of those sets can not contain infinite > > > sequences. > > > > The union of all finite trees and the complete infinite tree are > > identical with respect to nodes and edges, but differ with respect to > > paths? > > Depends on your definition. If in the union of the finite trees the set > of paths is the union of the sets of paths, then they differ. If the > set of paths in the union is not related to the sets of paths in the > the finite trees, they are equal. Every path is a subset of the set of all nodes. The set of al nodes is the union of all finite trees. That is enough. If you insist that only finite paths are possible in the union of all finite trees, then you say that there are no infinite paths at all. > > Could you please specify the asserted difference concerning the > > paths p in terms of their definition? The paths are: > > p = Sequence (a_n) with n in N and a_n in {0, 1} > > while the real numbers in general are represented by: > > r = SUM (a_n * 2^-n) with n in N and a_n in {0, 1}. > > Identical representations imply identical numbers. > > But again, you are now using a limit, not a union. Those things are > different. Consider the intervals in the real of rational numbers: > [1/n, 1-1/n] > all closed, indexed by natural numbers. We can look at those intervals > as sets of numbers, so we can take their union. We find: > union{n in N} [1/n, 1-1/n] = (0, 1) > while > lim{n -> oo} [1/n, 1-1/n] = [0, 1] > by some reasonable definition of limit. That is a good example. Note two things. > (1) difference in notation. In the union there is no order implied in > the uniting, it is independed on the order and can even be done > about collections that are not countable. With the limit you > have to state an order. In the union of paths there is an order (by length of the paths (before getting constant)). > (2) 0 and 1 are in the limit, but not in the union. They are not in > the union because they are in none of the intervals. 1 = 0.111... is in the union of all finite trees, also 0.000... Regards, WM
From: Dik T. Winter on 16 Jan 2007 09:57 In article <1168954593.509889.128600(a)l53g2000cwa.googlegroups.com> mueckenh(a)rz.fh-augsburg.de writes: > Dik T. Winter schrieb: .... > > I am talking about the path 0.01010101... which you claim is also in the > > complete tree. > > I every node is in the tree, then every node of 0.01010101... is in the > tree too. Or is this assertion false? And when I ask you about the initial segments you punt. > > > When all nodes are there , then all paths are there. > > > > All paths are in the complete tree, > > But the union of all finite trees is not the complete tree? Pray read what I always state: "the union of the sets of paths in the finite trees is not the set of paths in the infinite tree". You even quote it below: > > but *not* in the union of the sets > > of paths in the finite trees, otherwise for each path in the complete > > tree there *must* be a finite tree that contains it. Any comments on this? > > > Or the set of digits of Cantor's diagonal is not an infinite number. > > > > I see no connection. > > Cantor's diagonal can be represented as a (diagonal) path in an > infinite matrix. This matrix is the union of finite matrices. It is the > same as with the trees. The diagonal is *not* the union of the sets of diagonals of the finite matrices, because that is a set with infinitely many elements. It is also not in that union, because all elements of that union have finite length. To use unions here you have to be careful about defining the sets you are uniting. Consider the ordered (multi)-sets consisting of the initial n digits of that diagonal for each n. Each set represents an initial segment of the diagonal. The union of them can properly be defined and represents the diagonal. (The definition of union in this case would be something along: The union of two ordered (multi)-sets is defined if for every n either both have an n-th element and they are equal, or at most one has an n-th member. You can extend this to an arbitrary collection.) > > That is my objection to your reasoning above. You still assume that the > > union of the sets of paths of the finite trees *is* the set of paths in > > the complete tree. That is *false*. The complete tree contains the path > > 0.010101... . If that path is not in *any* of the sets of paths in the > > finite trees, that path is also not in their union. So while the countable > > union of the sets of paths in finite trees is countable, that is *not* > > the set of paths in the complete tree. > > If there are all nodes then there are all paths. That is not countering my objection. > > > But every path of the left tree is contained as an initial segment in a > > > path of the right tree. > > > > Yes. I see no problem. Do you agree that the *union* of the sets of > > paths is *not* the set of paths in the right-hand tree? You are talking > > about unions of sets of paths, segments have nothing to do with such. > > I am talking about the union of all nodes. The presence of all paths in > the union of all nodes is obvious. You see it if you try to find out > which node of the path 0.010101... may be missing in the union of trees > but may be present in the complete tree. But when you try to prove that the set of paths is countable you are *using* the union of sets of paths, and that is not the set about which you want to prove something. -- dik t. winter, cwi, kruislaan 413, 1098 sj amsterdam, nederland, +31205924131 home: bovenover 215, 1025 jn amsterdam, nederland; http://www.cwi.nl/~dik/
From: mueckenh on 16 Jan 2007 10:10 William Hughes schrieb: > No. The (potentially) infinite sequence of all digits is not > in the list, nor is it in the union of all finite binary trees. Simply draw the path of 1/3 with a slope of 45°: 0. 0 1 0 1 ... Then you see that it is in the tree which contains all levels enumerated by all n in N, if and only if it is the diagonal of Cantors list enumerated by all n in N. > > > > > > Thus one cannot say > > > Cantor's diagonal "consists only of finite initial segments". > > > > One must say so. It is similar to saying N consists of finite numbers > > only. > > No. The statement > > All elements of N are finite numbers > > is true. The statement > > All initial segments of Cantor's diagonal are finite > > is false. There is one (potentially) infinite initial segment. in a list enumerated by all natural numbers? But there is no infinite path in a tree the levels of which are enumerated by all natural numbers? Regards, WM
From: Dik T. Winter on 16 Jan 2007 10:11 In article <1168955262.910310.48680(a)v45g2000cwv.googlegroups.com> mueckenh(a)rz.fh-augsburg.de writes: > Dik T. Winter schrieb: > > In article <1168869430.273702.199810(a)q2g2000cwa.googlegroups.com> mueckenh(a)rz.fh-augsburg.de writes: .... > > > Depends on definition of "finite tree". If all finite paths are > > > continued with sequences of 000... or 111..., then the union of paths > > > of two finite trees is the set of paths of the larger tree. > > > > Wrong. You can name the paths anything you like, that does not make it > > right. At level 2 the finite tree has only paths that go through two > > nodes. At level 3 the finite tree has only paths that go through three > > nodes. In the union of the sets of paths there are both paths that go > > through two nodes and paths that go through three nodes. They are distinct. > > I meant the following: Accordng to my original definition, the tree > from level 0 to level 1: > > 0. > 0 1 > > has the paths 0.0000..., 0.0111..., 0.1000..., and 0.1111. (the tails > 000... and 111... are always appended.) This set of four paths is also > in the tree from level 0 to level 2 and in all greater trees. No, they are not. I see only paths that go through two nodes. There are no such paths in higher levels. You may give them the same name, that does not make it the same path. > But this is irrelevant. We do not unite sets of paths. You do when you want to prove that the set of paths is countable. Remember what you wrote: (1) In each finite tree the set of paths is finite. (2) A countable union of finite sets is countable. (3) So the set of paths in the complete tree is countable. (3) is not justified because (2) is not about the set of paths in the complete tree. Now try to do this proof *without* using sets of paths. > > > What is the difference > > > between the union of all finite trees and the infinite tree in terms of > > > nodes? > > > > See above. And ultimately, in the union of the sets of paths of all > > finite trees, there are only paths that go through finitely many nodes. > > There is *no* path that goes through infinitely many nodes. > In the union of all finite squares > > (11) > > (11), (12) > (21), (22) > > etc. > > there is no infinite diagonal. Why not? I only state that that diagonal is not in the union of the sets of diagonals of the finite squares. > > > If there is a difference, then it can exist also in Cantor's list. As > > > the digit a_nn has always a finite distance from the first line it has > > > also always a finite distance from the first column. You never cover > > > the complete list. > > > > That is something different. Above we are talking about union. Here > > you are talking about limit. > > Why do you refuse to talk about the limit in case of paths? In that case *you* have to define what you understand under limit. But lets suppose that s_n is the set of paths in the finite tree of level n. I concede that you might be able define a limit such that lim{n -> oo} s_n = s where s is the set of paths in the complete tree. But with this you can show nothing about the cardinality of s because lim{n -> oo} | s_n | = | s | is not necessarily valid. > > > > How than can you draw conclusions about the cardinality of the sets of > > > > paths in the union from the cardinalities of the sets of paths in the > > > > finite trees? > > > > > > A union cannot have more elements than are united. > > > > Indeed. But the union is not the complete collection. > > The union of finite trees contains all (initial) sequences (of paths). > Their number is countable. As long as you allow only the *finite* initial sequences, they are countable. Not if you allow more. That is because the union of the sets of paths in finite trees does exist just of the set of finite initial sequences. And you proof about sets of paths works for this. But that set is not the set of all paths. > > > A set of sequencs cannot have more limits than there are sequences. > > > > Again switching to limit from union. The two concepts are different. > > Feel free to take what you think is necessary to abolish set theory. You can't with unions and you can't with limits. AAs shown above. -- dik t. winter, cwi, kruislaan 413, 1098 sj amsterdam, nederland, +31205924131 home: bovenover 215, 1025 jn amsterdam, nederland; http://www.cwi.nl/~dik/
From: William Hughes on 16 Jan 2007 10:23
mueckenh(a)rz.fh-augsburg.de wrote: > William Hughes schrieb: > > > > No. The (potentially) infinite sequence of all digits is not > > in the list, nor is it in the union of all finite binary trees. > > Simply draw the path of 1/3 with a slope of 45°: > > 0. > 0 > 1 > 0 > 1 > ... > > Then you see that it is in the tree which contains all levels > enumerated by all n in N, if and only if it is the diagonal of Cantors > list enumerated by all n in N. > > > > > > > > > Thus one cannot say > > > > Cantor's diagonal "consists only of finite initial segments". > > > > > > One must say so. It is similar to saying N consists of finite numbers > > > only. > > > > No. The statement > > > > All elements of N are finite numbers > > > > is true. The statement > > > > All initial segments of Cantor's diagonal are finite > > > > is false. There is one (potentially) infinite initial segment. > > in a list enumerated by all natural numbers? But there is no infinite > path in a tree the levels of which are enumerated by all natural > numbers? There are two such trees. T1: The union of all finite trees T2: The inifinite tree. Both T1 and T2 have levels which are enumeratred by all natural numbers. However, the trees are not the same. T1 does not contain an infinite path. T2 does contain an infinite path. For Cantor's diagonal we can say: The (potentially) infinite set of all finite initial segments of Cantor's diagonal does not contain an (potentially) infinite initial segment. Cantor's diagonal does contain an (potentially) infinite initial segment. - William Hughes |