Cantor Confusion
in [Math]
|
Prev: Pi berechnen: Ramanujan oder BBP
Next: Group Theory
From: Ralf Bader on 21 Jan 2007 20:13 Franziska Neugebauer wrote: > Virgil wrote: > >> The difficulty with that definition is that for "infinite" trees, >> the set of nodes and the set of edges is not enough to determine the >> set of paths, as it is in finite trees. >> >> The minimal set of paths consistent with a tree being infinite is >> countable but the maximal one is not. >> >> As the distinction between the set of paths being countable and >> uncountable is what WM is interested in, those sets of paths must be >> taken into consideration. > > Do you agree that a tree (finite and infinite) is completely determined > by the nodes and edges? > > Do you agree that the set of paths if kind of a "derived" property? > > I asked since I have the apprehension that you take the structure > (M, E, P) (M = set of nodes, E = set of edges, P = set of paths) for > the tree. Whereas I take (M, E) for the tree. Whew! This is getting interesting again! There have been hardly 5 zillions of postings on trees and the like, and you're already going to take definitive steps towards a working and unique definition of that notion! Now I'm really curious to watch what Mückenheim will come up with to spoil such attempts. Ralf
From: Dik T. Winter on 21 Jan 2007 20:57 In article <PCmgPBce1YsFFwuD(a)phoenixsystems.demon.co.uk> Andy Smith <Andy(a)phoenixsystems.co.uk> writes: > Dik T. Winter writes > >Perhaps, but I do not know. To show that |x|^n converges to 0 for all > >|x| < 1 it is sufficient to get the definition of limit from the cupboard: > > lim{n -> oo} f(n) = L iff for all eps > 0 there can be found an n0 such > > that for all n > n0, |f(n) - L| < eps. > >So assume some eps < 1. Take n0 = ceil[log eps / log |x|]. We have eps and > >|x| < 1, so log eps and log |x| < 0 and the quotient is > 0, so n0 > 0. Now > >set n some integer > n0, we have: > > n > log eps / log |x| > > n.log |x| < log eps (because log |x| < 0) > > exp(n.log |x|) < exp(log eps) (because exp is strictly increasing) > > |x|^n < eps > >as required. So given an arbitrary eps we can find an n0, and that proves > >that the limit is what it should be. > > Do you see any possible difficulties with the above as eps->0 and |x|->1 > ? What would the difficulties be? In the above I see no |x| -> 1, nor an eps -> 0. Given an arbitrary x with |x| < 1 and an arbitrary eps > 0, the requirements of the definition work, and that is all that is needed. -- dik t. winter, cwi, kruislaan 413, 1098 sj amsterdam, nederland, +31205924131 home: bovenover 215, 1025 jn amsterdam, nederland; http://www.cwi.nl/~dik/
From: David Marcus on 21 Jan 2007 21:15 Ralf Bader wrote: > Franziska Neugebauer wrote: > > Virgil wrote: > > > >> The difficulty with that definition is that for "infinite" trees, > >> the set of nodes and the set of edges is not enough to determine the > >> set of paths, as it is in finite trees. > >> > >> The minimal set of paths consistent with a tree being infinite is > >> countable but the maximal one is not. > >> > >> As the distinction between the set of paths being countable and > >> uncountable is what WM is interested in, those sets of paths must be > >> taken into consideration. > > > > Do you agree that a tree (finite and infinite) is completely determined > > by the nodes and edges? > > > > Do you agree that the set of paths if kind of a "derived" property? > > > > I asked since I have the apprehension that you take the structure > > (M, E, P) (M = set of nodes, E = set of edges, P = set of paths) for > > the tree. Whereas I take (M, E) for the tree. > > Whew! This is getting interesting again! There have been hardly 5 zillions > of postings on trees and the like, and you're already going to take > definitive steps towards a working and unique definition of that notion! Maybe you are right and we shouldn't rush into this. I'm reminded of a Dilbert cartoon where Dilbert is told about a pre-meeting to plan a meeting and asks (sarcastically) whether they should jump right into the pre-meeting without planning it first. So, the boss decides to call a pre-pre-meeting to plan the pre-meeting. > Now I'm really curious to watch what Mückenheim will come up with to spoil > such attempts. -- David Marcus
From: Dik T. Winter on 21 Jan 2007 21:53 In article <1169375886.670658.154840(a)q2g2000cwa.googlegroups.com> mueckenh(a)rz.fh-augsburg.de writes: > Dik T. Winter schrieb: > > > 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 that is wrong. The set of paths is *not* the union of the sets of > > paths in the finite trees. And that is easy to prove. The path > > 0.010101... is not in that union of sets of paths because it is in > > *none* of the sets of paths, so it also can not be in the union of > > sets of paths. > > Hi Dik, I hope not to disturb you. Not at all. > If the union of singletons {1} U {2} U {3} U... U {n} U ... is an > infinite number omega, then the union of domains of sequences {1} U {1, > 2} U {1, 2, 3} U... U {1, 2, 3, ..., n} U ... is the domain of an > infinite seqeunce {1, 2, 3, ...}. Pray explain what you understand under "domain of", and what you understand under "union of domains". That is complete non-standard terminology. But whatever, whenever in a collection of sets A_k, none of the sets A_k contains a particular element E, it is also not in the union. > > > >From this we can conclude that also every other infinite path belongs > > > to the union T1 of all finite trees. > > > > Yes, it is in the union of finite trees. But *not* in the union of sets > > of paths in finite trees. > > How could a path be in the union of finite trees if it were not a path > of a finite tree? Ah, that is the key question. Clearly 0.010101... is not a path in any of the finite trees. But it is because by one of your definitions of path and tree such a path does exist. You never stop to rigurously define what a tree and a path is. I have a few times attempted to define a tree, but each time you skipped my definition and resorted to intuitive, bad-defined concepts. Once you stated that a tree was a set of nodes. That is obviously false. A set of nodes is nothing more than a set of nodes until you introduce edges. When you introduce edges you get a graph. But, equally obviously, not every graph is a tree. A tree needs a set of nodes and a set of directed edges (in a particular fashion). I did grant you all that and gave (I think) a rigorous definition of a tree, and even how to produce unions of trees. > Two trees which are identical by all nodes and edges are identical by > all paths. Right. > T1 as the countable union of all finite sets of finite paths contains > only a countable set of finite paths. No. It *is* the countable set of finite paths. > And T1 = T2. No. T1 is a set of paths, it is not a tree. T1 does not contains nodes or edges as elements. Only paths. > > > 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. > > > > It is not countable, you have not given a proof. > > Here it is (for trees of the kind weeping willow): Taking the union of > two trees corresponds to taking the union of their sets of paths. Why? The union of the sets of paths is a set of paths, not a tree. > Then > we have:The set of paths in the union is the set of paths in the larger > tree. If you define a tree by the set of paths in it. Yes. > This holds if it holds for domains of finite seqeuences. The domain of > two finite sequences is the domain of the longer sequence. The domain > of all finite sequences is omega. But using this kind of defining and uniting trees, the complete tree will not have 0.010101... as a path. Do you see how it crucially depends on how you define things? If you define trees by nodes and edges, and paths as a consequence of that, you get a different result. (And I still wonder what you mean with "domain of".) > > > Then it exists in the union tree - together with all paths of same > > > length. > > > > But I am not contradicting that. Again, I state that it is not in the > > union of sets of paths in finite trees. There is a huge difference. > > See the proof above. The sets of paths can be unioned as the trees can > be unioned. Not so. If you define trees as sets of paths, they can be united as you wish, but you will not have 0.010101... in the union tree. If you define them as some particular graphs, they can also be united, but you have a different result. > There is a bijecton between the set of finite trees T(n) and the sets > of paths P(n) in finite trees. Yes. They are both countable. > > > > 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. > > > > Yes, so it is not *in* the union. > > The cardinal number of the union (in general 1) cannot be larger than > the cardinal number of the set of elements of the union (often an > aleph). The cardinal number of the union of path segments cannot be > larger than the cardinal number of all path segments. This makes no sense. The cardinal number of a union is the cardinal number of the set of elements of the union. Because the two sets are the same. And you are switching focus again, from paths to path segments. > > > So if we have the union of all digits, then we have > > > the diagonal. > > > > The union of the digits is *not* the union of the sets of diagonals. > > If we have the ordered union of all digits, then we have the diagonal. What is the union of all digits? Unions are about sets. But if you want to maintain the von Neumann paradigm, we get for e: 0.2718281828459045... as initial union the set: {0, 1, 2, 4, 5, 7, 8, 9}; not even close to e. > > > This is a wrong approach. (It is insufficient to observe the problem.) > > > > It is the only possible approach when you consider unions of sets of paths. > > No. The directions of paths are given. If you assert that in T2 and T1 > there are different paths, then they can differ by length only. But you > do not assert that, contrary to William, for instance. No. Because I use a different approach to what you are actually meaning. As you do not define things, it is pretty difficult to ascertain what you are meaning. But paths can be different by many things. I focus on the way they are different in the number of nodes they visit, William Hughes focusses on the paths they visit. > > > The elements of our sets are nodes. The paths are subsets. If you do > > > not observe this fact, you cannot find a contradiction. > > > > You are using a countable union of *sets* of paths. > > The tree is an (ordered) set of nodes. The nodes can be used to form > paths, i.e., subsets of the tree. As a tree is a set of nodes, any subset of it is a set of nodes. Not every subset of it is a path. But whatever, the number of subsets of the final tree is not countable. The union of the sets of paths of the finite trees is not the set of paths of the complete tree. -- dik t. winter, cwi, kruislaan 413, 1098 sj amsterdam, nederland, +31205924131 home: bovenover 215, 1025 jn amsterdam, nederland; http://www.cwi.nl/~dik/
From: Franziska Neugebauer on 22 Jan 2007 04:29
Virgil wrote: > Franziska Neugebauer wrote: >> Virgil wrote: [...] >> Do you agree that a tree (finite and infinite) is completely >> determined by the nodes and edges? > > Finite trees are. Infinite trees are not. Please correct me if I am wrong: 1. Let the set of nodes M = omega\{0}. 2. Introduce the nodes of /level/ n e omega: L(n) = {2^n, ..., 2^(n+1) -1} n=0 1 / \ n=1 2 3 / \ / \ n=2 4 5 6 7 ... 3. Let the set of edges of all nodes from level m-1 to level m, m e omega\{0}: E(m) = U {{(i, 2i), (i, 2i + 1)} | i e L(m - 1)} (finite union) 4. Let the set of all edges be E = U {E(m) | m e omega\{0}} (countable infinite union) According to the usual definitions of graph theory G = (M, E) is an infinite graph. It is even an infinite binary tree. So I would like to ask you what _in_ or _of_ G is not completely determined by its sets M and E? >> Do you agree that the set of paths if kind of a "derived" property? > > For finite trees, yes. For infinite trees no!. To begin with let us agree on what kind of paths we are talking about: In the present context ("representation of real numbers") we are concerned with paths which originate in the root node of the tree (0). I would like to define an infinite path as an infinite sequence of nodes (s(i))_i e omega having the property a) s(0) = 0 b) (s(i-1), s(i)) e E for all i e omega\{0} A finite path is a finite sequence of nodes over some domain D(m) = {0} U { n | n < m } m e omega having a) s(0) = 0 b) (s(i-1), s(i)) e E for all i e D\{0} >> I asked since I have the apprehension that you take the structure >> (M, E, P) (M = set of nodes, E = set of edges, P = set of paths) for >> the tree. Whereas I take (M, E) for the tree. >> >> F. N. > > For finite trees (M,P) works nicely, but it does not for infinite > trees. (M, P)? You mean (M, E), do you? > Consider the infinite binary tree limited to paths which are > "eventually constant", IMHO in the usual definition of tree, G = (M, E), there is no facility to restrict the tree to only those paths which share a certain property. So you obviously have a variant definition of tree in mind? > i.e., have some node beyond which all their branches go in the same > direction. In my view the set of paths P is a property which is "derived" or "constructed" from G. It does not constitute G. > A little thought should convince you that every node and every edge > that is in a maximal infinite binary tree is also in this much more > limited infinite tree. I would call that trees "path-confined" or so. A usually defined tree (set of nodes plus set of egdes) is by no means path-confined. Even finite trees can be path-confined in the way you propose: Let M = {0, 1, 2} and E = {(0, 1), (0, 2)}. This unconfined tree obviously has P = { (0, 1), (0, 2) }. You may _define_ the a path- confined tree by T' = ( M, E, P' ) for example by explicitly _setting_ P' = { }. Then T' contains no paths at all. Nonetheless this is not a property of the origial usually defined tree G = (M, E). > So that for infinite trees, sets of nodes and edges alone do not tell > the while story. What story? > It surprised me a bit when I discovered it, too. > > Note that in any finite tree, each path is uniquely determined by its > terminal edge and leaf node, from which, using the set of edges and > nodes, the entire path can be reconstructed. > > In a tree in which no path has a terminal edge nor a leaf node, there > is no way of reconstructing an infinite path from anything less > tha[n] a set of infinitely many nodes in it or a set of infinitely > many edges in it. I agree to that observation but I don't see a problem. The aforementioned tree G has countable-infinitely many nodes and countable-infinitely many edges (in fact all edges). What I do not understand is what you mean by "reconstruct" and for what this is relevant. > So that infinite trees are quite different from finite trees, and > cannot be specified merely by their sets of edges and nodes, as finite > trees can. With all due respect: This is wrong under the usual definition of "tree". Please take the sets M (1.) and E (4.). I cannot see how to "set-up" a second tree G'' which is is different from G = (M, E). F. N. -- xyz |