Cantor Confusion
in [Math]
|
Prev: Pi berechnen: Ramanujan oder BBP
Next: Group Theory
From: Franziska Neugebauer on 21 Jan 2007 18:07 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. F. N. -- xyz
From: David Marcus on 21 Jan 2007 18:27 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. I would prefer to take (M,E), too. I think it is simpler for purposes of the discussion (such as it is) with WM. -- David Marcus
From: Virgil on 21 Jan 2007 19:28 In article <MPG.201dbbc7831f8a8f989bc7(a)news.rcn.com>, David Marcus <DavidMarcus(a)alumdotmit.edu> wrote: > Virgil wrote: > > In article <MPG.201d8bd1f8c7b013989bc1(a)news.rcn.com>, > > David Marcus <DavidMarcus(a)alumdotmit.edu> wrote: > > > > > mueckenh(a)rz.fh-augsburg.de wrote: > > > > It is interesting: > > > > William knows that T1 and T2 exist, but T1 is different. > > > > Virgil is also accepting T1 but, like William, sees only finite trees > > > > therein. > > > > Dik knows that T1 contains infinite trees, but doubts that its paths > > > > are the union of the paths of the finite trees. > > > > You doubt the existence of T1 (seeing that otherwise set theory is > > > > contradiced?). > > > > > > > > Couldn't you get to a consensus? It would spare me a lot of work. > > > > > > Perhaps it would help if you look at the following and see if it is what > > > you are saying. If it isn't, please note any corrections. > > > > > > An edge is an ordered pair of nodes. A tree T is an ordered pair (M,E) > > > where M is a set of nodes, E is a set of edges. Assume that any tree > > > we mention is a complete binary tree. > > > > > > Define a path P in T to be a function P: X -> M where X is either > > > {0,...,n} or N, P(0) is the root node, (P(i),P(i+1)) is in E for all i > > > such that P(i) and P(i+1) are both defined, and if the domain is > > > {0,...,n}, then P(n) is a leaf node. Denote by Q(T) the set of paths > > > in T. > > > > > > Define a nested sequence of trees to be a sequence {T_i} where T_i = > > > (M_i,E_i), M_i is a subset of M_{i+1}, and E_i is a subset of E_{i+1}. > > > Define the union of these trees to be T* = (M*,E*) where M* = U{M_i} > > > and E* = U{E_i}. > > > > > > Claim: |Q(T*)| <= |U{Q(T_i)}|. > > > > 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. > > I meant for Q(T) to be defined to be all paths that satisfy the > definition above of being a path in the tree T. My definition above > defines a tree just by specifying its nodes and edges. The paths are > then determined. > > > The minimal set of paths consistent with a tree being infinite is > > countable but the maximal one is not. > > I believe my Q(T*) is the same as what you call the maximal set. > > > 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. > > True. But, I don't think WM understands that we can tack on the set of > paths as an explicit part of our definition of a tree. This is a rather > advanced mathematical concept. It is analogous to the problem that Tony > has not understanding that a set doesn't have to have an order. > > I'm pretty sure that WM believes that my Q(T*) is a subset of U{Q(T_i)}. > In fact, I'll hazard a guess that he thinks this is obviously true. > > WM: Care to comment? Am I right about what you are saying? Given that U{Q(T-I)} need not have your Q(T*) as its limit in any reasonable sense of limit. I can follow you, but WM seems to imply both the your Q(T*) has only countably many paths and that it is, in some ense, the only limit of the U{Q(T_i)} that is possible. My analysis is based on "embedding" each of the finite trees into your infinite Q(T*) as a proper subtree and then showing that the union of all those subtrees is far short of the maximal infinite binary tree.
From: Virgil on 21 Jan 2007 19:46 In article <45b3f24e$0$97215$892e7fe2(a)authen.yellow.readfreenews.net>, Franziska Neugebauer <Franziska-Neugebauer(a)neugeb.dnsalias.net> 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? Finite trees are. Infinite trees are not. > > Do you agree that the set of paths if kind of a "derived" property? For finite trees, yes. For infinite trees no!. > > 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. Consider the infinite binary tree limited to paths which are "eventually constant", i.e., have some node beyond which all their branches go in the same direction. 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. So that for infinite trees, sets of nodes and edges alone do not tell the while 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 that a set of infinitely many nodes in it or a set of infinitely many edges in it. 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.
From: Virgil on 21 Jan 2007 19:48
In article <MPG.201dc1024d6d938e989bc9(a)news.rcn.com>, David Marcus <DavidMarcus(a)alumdotmit.edu> 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. > > I would prefer to take (M,E), too. I think it is simpler for purposes of > the discussion (such as it is) with WM. I would prefer (M,E) myself, were it not for the fact that it only works for trees in which every path has a terminal edge and a leaf node. |