Cantor Confusion
in [Math]
|
Prev: Pi berechnen: Ramanujan oder BBP
Next: Group Theory
From: Virgil on 22 Jan 2007 15:25 In article <45b483f8$0$97267$892e7fe2(a)authen.yellow.readfreenews.net>, Franziska Neugebauer <Franziska-Neugebauer(a)neugeb.dnsalias.net> wrote: > 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? Whether the set of all possible pats is required to involve every node and every edge. For finite trees it is. For infinite trees it is not. > > >> Do you agree that the set of paths if kind of a "derived" property? > > > > For finite trees, yes. For infinite trees no! At least not if we are allowed to excude unneeded paths. > > 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? Sorry. Yes! > > > 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? In a finite tree, there is a necessary bijection between paths and terminal edges (or leaf nodes). So that the set of paths contains exactly the same information about a finite tree as does the combination of the set of nodes and set of edges. In an infinite tree, at least one in which no path ends, there are no such things as terminal edges or leaf nodes. So the set of paths contains more information than does the combination of the set of nodes and set of edges, and different sets of paths lead to the same sets of nodes and edges. Since it is sets of paths of a tree that WM has been going on about, it seems more reasonable to consider those sets of paths from the start. > > 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). On the other hand, your path-confined tree does not use all of its nodes and edges in its paths, as mine are required to do. > > > So that for infinite trees, sets of nodes and edges alone do not tell > > the while story. > > What story? What is a minimal set of paths required to use every node and edge of one of those (M,E) trees? For a finite tree, it is the set of all possible paths, but for an infinite tree it is not. > > > 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.
From: Virgil on 22 Jan 2007 15:35 In article <45b489e1$0$97253$892e7fe2(a)authen.yellow.readfreenews.net>, Franziska Neugebauer <Franziska-Neugebauer(a)neugeb.dnsalias.net> wrote: > Virgil wrote: > > [...] > > 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. > > I think noone (except WM) doubts that the countably infinite union of > the set of the sets of *paths* (not the trees!) of all finite binary > trees is different from the set of all paths in the infinite binary > tree. The latter contains infinitely long paths but the former does > not. > > But the union of the set of the sets of paths P(n) of the finite binary > trees trees T(n) n e omega is not a tree at all. It is a set of paths. > > So to meaningfully speak of "union of all finite trees" (WM) > > T(1) U T(2) ... = U { T(i) | i e N } > > you must either > > 1. (WM-1) re-define union and the union-U so one gets the binary > tree having max({ depth(T(i) | i e N }) depth as "union". > -> undefined since max(N) does not exist. > > 2. (WM-2) re-define union and the union-U so one gets the binary > tree having sup({depth(T(i) | i e N }) depth as "union". > -> undefined yet. But after extending T(n) to T(omega) meaning the > infinite binary tree it may be meaningful though due to the use of a > redefined notion of "union" this leads to faulty conclusions about > what cardinality can be "reached" by countable "unions" of finite > sets. > > 3. (Virgil?) Use a variant definition of tree. Possibly by defining > every set of paths (having certain properties) to be a tree. > > Regardless of what you choose you must deviate from the vital > mathematical definitions to achieve any reasonable result (if at all). My variant definition gives exactly the same tree structure up through the leaf nodes as the standard definition for all finite binary trees of fixed path length, but differs by having all of those finite trees as proper subtrees of all larger such finite trees and also of the tree of all infinite binary paths (corresponding to the standard infinite binary tree).
From: Virgil on 22 Jan 2007 15:40 In article <1169471679.368724.213270(a)l53g2000cwa.googlegroups.com>, mueckenh(a)rz.fh-augsburg.de wrote: > Franziska Neugebauer schrieb: > > > Even if we now use > > > > T(m) U T(n) := T(sup(m, n)). (fin-u') > > > > and and try to define (inf-u) by > > > > T(1) U T(2) ... := T(omega) > > > > it is still left open what T(omega) shall mean. One has to take special > > care for the notation: The union symbol "U" does not mean the usual set > > theoretical union. > > It does. Claimed but not proven.
From: Virgil on 22 Jan 2007 15:45 In article <1169472355.486545.309380(a)q2g2000cwa.googlegroups.com>, mueckenh(a)rz.fh-augsburg.de wrote: > Virgil schrieb: > > > Cantor, using his original diagonal argument, and anyone else who wants > > to emulate him, can show that any /list/ of paths in a complete infinite > > binary tree is incomplete. > > So you do not believe in complete trees? Non sequitur. What I believe is that complete infinite trees always have a set of paths which is actual but unlistable. > Somewhere in the mist of infinity ... WM's mind got lost, and he has been searching vainly for it ever since.
From: Virgil on 22 Jan 2007 15:52
In article <1169473008.561623.314970(a)v45g2000cwv.googlegroups.com>, mueckenh(a)rz.fh-augsburg.de wrote: > Virgil schrieb: > > > > The minimal set of paths consistent with a tree being infinite is > > countable but the maximal one is not. > > The minimal set is the maximal set. WRONG! I can name a less than maximal set of paths using every node and edge in a complete infinite binary tree quite different from the set of all possible paths. Specifically the set of all paths which are "eventually constant" is a proper subset of the set of all possible paths, but it still uses every node and every edge. > > > > 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. > > Both sets are the same countable set. As per my example above, the set of "eventually constant" paths is countable (as can be easily shown) but the set of all paths is not (as Cantor proved with his original diagonal argument). |