Cantor Confusion
in [Math]
|
Prev: Pi berechnen: Ramanujan oder BBP
Next: Group Theory
From: mueckenh on 19 Jan 2007 07:30 Carsten Schultz schrieb: > mueckenh(a)rz.fh-augsburg.de schrieb: > > Carsten Schultz schrieb: > > > >>> You assume that the union P_i of paths contains more paths than can be > >>> constructed from finite initial segments? > >> I do not assume anything. I just note that being a path in the union of > >> the T_i and being an element of the union of the P_i are a priori > >> different things and that you would have to prove their equivalence in > >> your setting should you claim this equivalence. > > > > > > The union of all finite trees is an infinite tree. > > The countable union of all finite paths is in the union of all finite > > trees. > > The "complete" tree containing all paths is identical to the union of > > al finite trees, with respect to nodes and edges. > > Identical trees cannot contain different sets of paths. > > Therefore, both trees contain the same set of paths. > > > > > >>>> the countability of the union of the P_i that there are only countably > >>>> many paths in the union of the T_i. > >>> Is Cantor's diagonal longer than the union of all of its initial > >>> segments? > >> Can you stay on the subject? > > > > That is the subject. Try to get it. > >>> Is N more than the union of all of its initial segments {1, 2, 3, ..., > >>> n}? > >> Are there subsets of N that are not subsets of a proper initial segment? > > > > Of course. The set of primes, for instance. > > Wow. Even though the set N is identical to the union of its proper > initial segments and identical sets cannot have different sets of subsets? Again you are mistaking one notion for another. Trees which are identical with respect to nodes and edges cannot have different *paths*. A path is a subset of the set of nodes. That does not mean that every subset of the set of nodes is a path. Regards, WM
From: mueckenh on 19 Jan 2007 07:35 William Hughes schrieb: > UT is not a tree. > Call it as you like. Simply call it T1. (If I speak of "tree" blow, simply read "eert".) It may be what you like. In any case it is the same by nodes, edges and paths as T2. Only the "number of paths" is assertede to be different. 0 0. / \ 1 0 1 / \ / \ 2 0 1 0 1 ... ..... The union T1 of all finite binary trees covers all levels enumerated by natural numbers. With respect to nodes and edges it is identical with the infinite binary tree T1 = T2 According to set theory (including the axiom of choice) a countable union of countable sets is a countable set. The set of paths in the union tree T1is merely a countable union of finite sets, and, therefore, T1 contains only a countable set of paths. But does T1 contain only infinite paths? An index denotes the level to which a node belongs. The union of all indexes of nodes of finite paths is the union of all initial segments of natural numbers {1} U {1, 2} U {1, 2, 3} U... U {1, 2, 3, ..., n}... U ... = {1, 2, 3, ...}. This is also the set of all last elements of the finite segments, i.e., it is the set of all natural numbers N. This is the set of all indexes - there is no one left out. With respect to this observation we examine, for instance, all finite paths of the tree T1 which always turn right: 0.1, 0.11, 0.111, ... If considered as sets of nodes, their union is the infinite path representing the real number 0.111... = 1. >From this we can conclude that also every other infinite path belongs to the union T1 of all finite trees. We see, the trees T1 and T2 are identical with respect to all nodes, all edges, and all paths (which would already have been implied by the identity of nodes and edges). But the set of all paths is countable in the tree T1 and uncountable in the same tree T2. Regards, WM
From: mueckenh on 19 Jan 2007 07:38 Franziska Neugebauer schrieb: > mueckenh(a)rz.fh-augsburg.de wrote: > > > Franziska Neugebauer schrieb: > > > >> As I have mentioned in my last post: You have not given a definition > >> of a union of all finite trees. > > > > The union of two finite trees T(m) and T(n) with m and n levels, > > respectively, where m < n, is the tree with n levels. > > OK. > > 1. Let T(i) denote the tree of (finite) depth i e N. > > 2. Define depth(T(i)) := i. > > 3. Let u(E, F) denote the function which yields the deepest of two given > trees E and F: > > / E if depth(E) >= depth(F) > u(E, F) := | > \ F else > > Introduce the notation E U F := u(E, F). > > So obviously Ai,j e N (T(i) U T (j) = T(max(i, j)). > > 4. Extend max to an arbitrary set S of integers: > > If E m e S A i e S (m >= i) > then m is called the maximum of S, max (S). > > (note: this definition does not state that every S has a maximum). > > 5. Let V be some (finite) set of trees { T_1, ..., T_n } n e N. > > 6. Define the set of depths of a set of (finite) trees: > > D(V) := { depth(t) | t e V } > > 6. We now introduce the notion of the "union of a finite set of > trees" (sloppyly "union of trees") as: > > U V := T_1 U ... U T_n (n e N) > > Proof as an exercise that forall sets of finite trees V having card(V) e > N it holds that > > U V = T(max(D(V)). > > 7. Now let V* denote the set of all finite trees { T(i) | i e N }. > > Since U V* is only defined for V having card(V) e N. Since V* does not > meet this requirement we (you?) have to define what > > U V* > > shall mean. The obvious definition > > "U V* = T(max(D(V*))" > > fails due to the reason that max(D(V*)) = max(omega) is not defined. > > The questions is: How do you define U V_omega? > > > This definition unites sets of nodes (and sets of edges, > > respectively) > > Let T1 = (V1, E1) and T2 = (V2, E2). What you define here is > > T1 U T2 := (V1 U V2, E1 U E2) > > which is perfectly legal. But set theoretically a union of trees > (ordered pairs) would read > > T1 U T2 = { V1, { E1 } } U { V2, { E2 } } > = { V1, V2, { E1 }, { E2 } } > > which is hardly a tree. > > > and it is valid for Cut Trees (CT) as well as for trees > > of type Weeping Willow (WWT). > > You should take care that union-operation defined so far _is_ _not_ > identical with the set-theoretical union. > > > The union of all finite trees is the union of all trees with n levels > > where n is a natural number: > > UT = T(1) U T(2) U T(3) U ... > > This is undefined since your expression has card(omega) many terms. > Please supply a finite substitute of that expression. Hint: > > When we (informally) write > > - {1, 2, ...} we mean { i | i e N } > - { 1 } U { 2 } U ... we mean U {{1}, {2}, ...} > = U {{i} | i e N } > = N. > > But when we (informally) write > > - T(1) U T(2) U T(3) U ... we have not yet any definition at all > _and_ we have no proof (or axiom) that this > "infinite union" does exist. It depends simply on the question whether the uninon of all natural numbers does exist. This is connected to the unuion of levels and initial segments and finite trees. See below: 0 0. / \ 1 0 1 / \ / \ 2 0 1 0 1 ... ..... The union T1 of all finite binary trees covers all levels enumerated by natural numbers. With respect to nodes and edges it is identical with the infinite binary tree T1 = T2 According to set theory (including the axiom of choice) a countable union of countable sets is a countable set. The set of paths in the union tree T1is merely a countable union of finite sets, and, therefore, T1 contains only a countable set of paths. But does T1 contain only infinite paths? An index denotes the level to which a node belongs. The union of all indexes of nodes of finite paths is the union of all initial segments of natural numbers {1} U {1, 2} U {1, 2, 3} U... U {1, 2, 3, ..., n}... U ... = {1, 2, 3, ...}. This is also the set of all last elements of the finite segments, i.e., it is the set of all natural numbers N. This is the set of all indexes - there is no one left out. With respect to this observation we examine, for instance, all finite paths of the tree T1 which always turn right: 0.1, 0.11, 0.111, ... If considered as sets of nodes, their union is the infinite path representing the real number 0.111... = 1. >From this we can conclude that also every other infinite path belongs to the union T1 of all finite trees. We see, the trees T1 and T2 are identical with respect to all nodes, all edges, and all paths (which would already have been implied by the identity of nodes and edges). But the set of all paths is countable in the tree T1 and uncountable in the same tree T2. Regards, WM > > F. N. > -- > xyz
From: mueckenh on 19 Jan 2007 07:58 Dik T. Winter schrieb: > In article <1169117024.775595.256400(a)11g2000cwr.googlegroups.com> mueckenh(a)rz.fh-augsburg.de writes: > > Dik T. Winter schrieb: > ... > > > Further with the finite trees as > > > you currently define them (with all having infinitely many nodes, so I > > > the only finiteness is the number of splitting), the union of sets of > > > paths in two finite trees is the set of paths in the union of those > > > two trees. *But* that does not hold when you unite the whole collection > > > of finite trees. > > > > No? > > > > The union of two finite trees T(m) and T(n) with m and n levels, > > respectively, where m < n, is the tree with n levels. This definition > > unites sets of nodes (and sets of edges, respectively) and it is valid > > for Cut Trees (CT) as well as for trees of type Weeping Willow (WWT). > > > > The union of all finite trees is the union of all trees with n levels > > where n is a natural number: > > UT = T(1) U T(2) U T(3) U ... > > > > The paths in a tree are completely defined by the sequences of nodes > > (or edges) which can be followed to an end in CT or without an end in > > their union as well as in WWT. > > In what way does that contradict what I wrote? I was talking about sets > of paths and their union. What you write is completely unrelated to that. You say the set of paths in the union tree is ot the same as the set of paths in the complete tree. If the sets of nodes and edges are identical, then also the sets of paths are identical. But here is the proof that the union contains all infinite paths. According to set theory (including the axiom of choice) a countable union of countable sets is a countable set. The set of paths in the union tree T1is merely a countable union of finite sets, and, therefore, T1 contains only a countable set of paths. But does T1 contain only infinite paths? An index denotes the level to which a node belongs. The union of all indexes of nodes of finite paths is the union of all initial segments of natural numbers {1} U {1, 2} U {1, 2, 3} U... U {1, 2, 3, ..., n}... U ... = {1, 2, 3, ...}. This is also the set of all last elements of the finite segments, i.e., it is the set of all natural numbers N. This is the set of all indexes - there is no one left out. With respect to this observation we examine, for instance, all finite paths of the tree T1 which always turn right: 0.1, 0.11, 0.111, ... If considered as sets of nodes, their union is the infinite path representing the real number 0.111... = 1. >From this we can conclude that also every other infinite path belongs to the union T1 of all finite trees. We see, the trees T1 and T2 are identical with respect to all nodes, all edges, and all paths (which would already have been implied by the identity of nodes and edges). But the set of all paths is countable in the tree T1 and uncountable in the same tree T2. > > > > > But *all* paths are in the union of the > > > > finite trees, because it is simply silly to suspect different sets of > > > > paths in a tree with all nodes. > > > > > > Eh? There is a whole collection of different sets of paths in a tree with > > > all nodes (assuming the definition of tree as I stated above, that is the > > > pair [set of nodes, set of edges]). Of course it is silly to suspect > > > different complete sets of paths. > > > > So it is. > > And there is not. ??? > > > > > Therefore the only conclusion is that > > > > the path 0.010101... does not exist. > > > > > > Wrong. > > > > If it exists, then it exists in every tree with all nodes and edges. > > Yes, and I never contradicted that. Then it exists in the union tree - tgether with all paths of same length. > > > > > So you say. If you were right, there should be some indication for the > > > > difference. > > > > What makes the path 0.010101... be in a tree with all nodes but not in > > > > a tree with all nodes? > > > > > > Again, I do not state that. What I state is that that path is (with the > > > definitions above) in the complete tree. > > > > It is in every tree which contains all nodes and edges (as defined by > > me), because there is no end when we follow the path always swithing > > betwen 0 and 1. > > Yes, so what? I never said that was not the case. Which paths then are you missing in the union tree? > > > > > Is it or part of it outside of this union? > > This is a silly question. Something is an element of a set or somthing > is not an element of a set. You can not have something being partly an > element of a set. As there is no last node of a path, we can nly investigate subsets of a path. > > You say it exists. It exists not in the union. Where does it exist? > > Outside the union. Let's illustrate. Call the diagonal of the triangle > of order n: d_n. The union of the sets of diagonals of the triangles is: > {d_1, d_2, d_3, d_4, ...} > the diagonal d of the infinite tree is not in it. It is the union. So if we have the union of all digits, then we have the diagonal. And the cardinal number of the diagonal cannot be larger than the cardinal number of the union. > > > > > It does contain that path (according to your definition above). > > > > > > > > Yes, that is obvious. But, for a moment, switch to the cut trees, > > > > please. Does the union of all cut trees contain the paths 0.111...? You > > > > would say no. > > > > > > And again, I would say yes. > > > > That is remarkable. Are you really sure? > > Yes. I did even show that in an earlier article I wrote. > > > > I even provided a definition of union of trees > > > for that case and with that definition that was easily enough to prove. > > > But then we have that the union of the sets of paths of two different > > > finite trees is not the set of paths of the union of those two trees. > > > > What is lacking? > > Consider a tree of level 1 and a tree of level 2. The tree of level 1 > contains only paths going through two nodes, the tree of level 2 only > paths going through three nodes. So none of the paths in the level 1 > tree is a path in the level 2 tree. So the union of the sets of paths > contains both all paths of the level 1 tree and all paths of the level > 2 tree. The set of paths of the level 2 tree contains only the paths > of the level 2 tree. This is a wrong approach. (It is insufficient to observe the problem.) > There are no nodes or edges in the union. The union is a union of sets > of paths, so it only contains paths. How you manage to get nodes and > edges as elements of a set of paths escapes me. The elements of our sets are nodes. The paths are subsets. If you do not observe this fact, you cannot find a contradiction. > > > > The reason is that a path is in that union *if and only if* it is in one > > > of the sets that are used to form the union. > > > > The reason is: If every subset of a path in the union, then the whole > > path in that union. > > Wrong. That is not how set theory works. If every subset of a path is > in the union, then the union contains (as elements) a whole lot of > subsets of paths. But not the complete path. Consider the following set: > {{1}, {2}, {3}, ...} > this set does *not* contain (as element) {1, 2}. Your wrong approach again. By subsets linear subsets (initial segments) are meant. > > > Every subset is in the union. Or not? > > Depends. Every subset of the sets of paths is in the union. But every > subset of paths is not in the union. > > > > > There are only countable many sequences. > > > > > > I disagree. There are uncountably many limits. You are trying to prove > > > that there are countably many sequences and limits. If there are countably > > > many sequences there are countably many limits, and the other way around. > > > But until now you have failed to prove either the first or the other. > > > > Every initial segment of a sequence in the union of trees. All initial > > segments are countable. > > Indeed, all (proper) initial segments are countable. But this does show > nothing. See above. > > Correct. All paths are in the union of all finite trees. > > And I did never contradict this. But not all paths are in the union of > the sets of paths from the finite trees. There is quite some distinction. > And in your proof of the countability of paths you assume the second. See above. Your examples with {1}, {2}, and {1,2} show a fundamental misconception. Regards, WM
From: Franziska Neugebauer on 19 Jan 2007 08:11
mueckenh(a)rz.fh-augsburg.de wrote: > A path is a subset of the set of nodes. Since every subset of the set of nodes of a tree is a set of nodes you eventually say: "A path is a set of nodes". This is not the whole truth. A path _has_ a set of nodes (besides the information about the connectivity of these nodes). > That does not mean that every subset of the set of nodes is a path. Actually no set of nodes _is_ a path. F. N. -- xyz |