Cantor Confusion
in [Math]
|
Prev: Pi berechnen: Ramanujan oder BBP
Next: Group Theory
From: David Marcus on 22 Jan 2007 21:36 mueckenh(a)rz.fh-augsburg.de wrote: > William Hughes schrieb: > The infinite union of all finite trees can only contain nodes which are > in a path. Otherwise the nodes could not enter the union. Nodes are > ends of paths of finit trees. > > > > However > > > > There is no path in T1 that contains every node in p1 > > Then not every node of T1 is in T1. > > > > Proof: > > > > Let a path in T1 that contains every node in p1 be called L_D > > > > L_D is in T1 so L_D is finite. > > > > L_D contains every node in p1, so L_D is (potentially) infinite. > > > > Contradiction. Therefore L_D does not exist. > > Let P be in the union of all intial segments {1,2,3,...,n} of N. There > is no initial segment P of N which contains all natural numbers. > Therefore the union of all P (which is N) does not exist? > > You make the following error: > A node cannot enter the union tree unless it belongs to a path. > If there is not one finite tree containing all nodes, then not all > nodes can be in the union of all finite trees. This implies that the > complete infinite tree contains more nodes than the union of finite > trees. Is this the error or the correct statement? Are you saying that the infinite tree contains a node that is not in any of the finite trees? -- David Marcus
From: Dik T. Winter on 22 Jan 2007 21:45 In article <45b48de1$0$97231$892e7fe2(a)authen.yellow.readfreenews.net> Franziska Neugebauer <Franziska-Neugebauer(a)neugeb.dnsalias.net> writes: > Dik T. Winter wrote: > > In article <1169375886.670658.154840(a)q2g2000cwa.googlegroups.com> > > mueckenh(a)rz.fh-augsburg.de writes: > > > Dik T. Winter schrieb: > [...] > > 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. > > Do you have a message id for your definition of unions of trees? No. But I provided at least two possible definitions. I can recapulate them, first define a tree: (1) A graph is a set of nodes together with a set of edges (possibly pointing to nothing). In a directed graph each edge is directed. A tree is a directed graph where the edges have some particular properties. The particular properties are: (a) there is only a single node with no incoming edges (the root node). (b) there is no node with more than one incoming edge. (c) from each node emanate two edges. (d) nodes from which emanate two edges pointing to nothing, is called a last node. (e) in a balanced tree all last nodes have the same distance (counting the number of edges) from the root. (2) As (1), but (c) from terminal nodes there are no outgoing edges. (d) if a node is non-terminal, there are two ougoing edges. [ That is, edges pointing to nothing are elided.] (e) in a balanced tree all terminal nodes have the same distance (counting the number of edges) from the root. From this we can define paths, also again two ways: (A) A path is a sequence of edges starting at the root node where successive edges are connected at a node. (B) As (1) but also: that do not terminate until there are no more possible edges or nodes. In all these cases we can define unions of trees by identifying the root of two trees, and identifying successive nodes in the trees. We have here that a tree is: [N, E] where N is the set of nodes in the tree and E the set of edges. Uniting them gives: union [T1, T2] = [union [N1, N2], union [E1, E2]]. But WM is only interested in balanced trees. So the tree T_n, is the tree where all the last or terminating nodes has distance n from the root. T_0 consists of a single node, and two edges emanating from it (according to (1)), or with no edges emanating from it (according to (2)). According to the union of trees definition above, T_0 according to (1) can not be a subset of any other tree, because there is no other tree that has an edge that emanates from the root and points to nothing. However, we can shift a bit and identify the edges in lower trees that point to nothing with edges in higher trees that point to something (assuming nothing is some node at a higher level). So now we have fully defined the union of trees, either according to (1) or to (2). The remaining choices are at the same level as what is 'i' and what is '-i'. We now can look at the sets of paths. With (B) obviously the union of the set of paths is not the set of paths of the union, regardless the definition of tree. We can assign a length to a path depending on the number of edges in that path and for T_n that length is either n or n+1, depending on the definition of tree. On the other hand, with (A) you get in your tree all paths with lengths less than or equal to n or n+1, again, depending on the definition of tree. With that definition, and with either definition of tree, the set of paths in the union of a finite number of finite trees is the union of the sets of paths of the finite trees involved. WM wants (B), but that breaks down immediately. He tried to propose his weeping willows, but that did not help in any way. But with (A) and either (1) or (2) the union of all trees T_n contains infinite paths. But the union of the sets of paths from the T_n does not contain *any* infinite path. So his argument will still fail. > > > 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. > > Doesn't it depend on the defintion of "the union"? No. Not really, I think. You have to define what a path is, but if a tree is defined by the set of paths, you can properly define the union of two sets of paths. But whether that is a tree is a question. > > > 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. > > Wording: WM claims a bijection between > { T(n) | n e N } (*) > and what? > a) P(n) n e N <- what is this I did understand the set of all paths in finite trees. That one is countable. But WM is unclear indeed. -- dik t. winter, cwi, kruislaan 413, 1098 sj amsterdam, nederland, +31205924131 home: bovenover 215, 1025 jn amsterdam, nederland; http://www.cwi.nl/~dik/
From: MoeBlee on 22 Jan 2007 21:51 Andy Smith wrote: > If we write numbers in their simplest form e.g > 0 = 0 > 1 = s0 > 2 = ss0 > n = n s's 0 > > we can never have an infinite number of s's, is what you are saying? There is no natural number that is "an infinte number of successors", right. True, we can have a denumerable sequence of natural numbers. But no natural number is itself "obtained from" a denumerable "number of successor applications". MoeBlee
From: Dik T. Winter on 22 Jan 2007 21:52 In article <Cp+TF3S4VQtFFwlT(a)phoenixsystems.demon.co.uk> Andy Smith <Andy(a)phoenixsystems.co.uk> writes: > Dik T. Winter writes .... > >This is wrong. With an infinite list you get a string of digits of an > >infinite length. But each natural number has a finite number of digits, > >and so the constructed string does not represent a natural number. > > OK, thanks, maybe that gets to the heart of my misunderstanding. > > If we write numbers in their simplest form e.g > 0 = 0 > 1 = s0 > 2 = ss0 > n = n s's 0 > > we can never have an infinite number of s's, is what you are saying? Right. When you increase n you get simply one more s, and the number of s's is still finite. -- dik t. winter, cwi, kruislaan 413, 1098 sj amsterdam, nederland, +31205924131 home: bovenover 215, 1025 jn amsterdam, nederland; http://www.cwi.nl/~dik/
From: G. Frege on 23 Jan 2007 00:27
On Mon, 22 Jan 2007 16:59:19 -0500, David Marcus <DavidMarcus(a)alumdotmit.edu> wrote: >> >> So far I have seen little that isn't too subtle for WM to grasp. >> > Very true. > Then why, oh why, do you still "discuss" mathematical topics with him?! Actually, he's a full blooded crank with a general lack of mathematical understanding (i.e. a mathematical "illiterate"). I really can't see the point in (doing) this. Sorry. F. -- E-mail: info<at>simple-line<dot>de |