Cantor Confusion
in [Math]
|
Prev: Pi berechnen: Ramanujan oder BBP
Next: Group Theory
From: Virgil on 17 Jan 2007 15:52 In article <1169038455.180403.228070(a)l53g2000cwa.googlegroups.com>, mueckenh(a)rz.fh-augsburg.de wrote: > Franziska Neugebauer schrieb: > > > > > Every edge is related to a node. > > > > Every edge is actually related to _two_ nodes (vertices). > > And sometimes they are drawn with black ink while the nodes are red. > Sometimes colours are reversed or even different colours are used. > Relevance? A set of nodes without any information about which nodes are connected by edges nor, when connected, which node is parent and which is child, does not produce anything more than a mere set of points with no other structure at all. It certainly does not produce a tree. Even a mere set of 3 points, {a,b,c}, creates at least 3 different trees with different root nodes. > > > > > The set of nodes is the set of ends of edges united with the set of > > > root nodes (which is only one). > > > > The "set of ends of edges" (united with a set of roots or not) does not > > _constitute_ the tree. Nonetheless this union may perhaps _equal_ the > > set of vertices. > > > > > Edges can but need not be used. > > > > Whether they "need" to be "used" is irrelevant. Relevant is: > > that definition which I gave for that kind of trees which I use in my > proof. If your definition is faulty for what mathematics requires of a tree, then your proof is faulty, too. > > > > One can use only nodes as well as one can use only edges. > > > > As said: There is already a well-established notion of tree in > > mathematics. A tree is an ordered pair of a set of vertices and a set > > of nodes _by_ _definition_. > > As I said: Relevant is only that definition which I gave for that kind > of trees which I use in my proof. Then your proof does not apply to mathematical binary trees but only to WM-trees. http://en.wikipedia.org/wiki/Binary_Tree http://en.wikipedia.org/wiki/Portal:Mathematics
From: Virgil on 17 Jan 2007 16:00 In article <1169049396.325322.35090(a)a75g2000cwd.googlegroups.com>, mueckenh(a)rz.fh-augsburg.de wrote: > William Hughes schrieb: > > > mueckenh(a)rz.fh-augsburg.de wrote: > > > William Hughes schrieb: > > > > > > > > > > > > > If there is no difference in terms of nodes, why does T1 not contain > > > > > all possible paths? > > > > > > > > Because the paths define the nodes, not the other way round. > > > > > > Wrong. My trees are defined by nodes. > > > > In this case T1 is not a tree. There is no set of nodes > > which contains all finite paths but does not contain > > an infinite path. > > Of course not. The complete tree T1 contains all paths. But since WM's trees are mot the same as mathematically defined rooted binary trees, none of his proofs are valid for mathematically defined rooted binary trees. > Then show me which node of the path 0.010101... is missing in T1. Since nodes alone cannot define a rooted binary tree, what WM has is not such a tree and is irrelevant when discussing such trees. > > Using your definition of tree, nothing. Using your > > definition, there is no such > > thing as a tree that is not node-complete. > > However, using your definition, T1 is not a tree.# > > No? What is missing? All you have is a set of nodes. That is not enough. http://en.wikipedia.org/wiki/Binary_Tree > You know that tere are finite trees in > mathematics? Not the way you define them. > > > > If you define a tree to be a set of paths, then > > two different trees can have the same nodes. > > Not if all paths go downwards as regularly as in my tree. Since WM's trees are just sets of nodes, they don't have any paths at all. > > Simply consider the trees as defined by me. God forbid, if there is a god. Definitions for rooted trees ? A directed edge refers to the link from the parent to the child (the arrows in the picture of the tree). ? A leaf is a node that has no children. ? The depth of a node n is the length of the path from the root to the node. The set of all nodes at a given depth is sometimes called a level of the tree. ? The height of a tree is the length of the path from the root node to its furthest leaf. ? Siblings are nodes that share the same parent node. ? If a path exists from node p to node q, then p is an ancestor of q and q is a descendant of p. ? The size of a node is the number of descendants it has including itself. [edit]Types of binary trees ? A rooted binary tree is a rooted tree in which every node has at most two children. ? A full binary tree, or proper binary tree, is a tree in which every node has zero or two children. ? A perfect binary tree (sometimes complete binary tree) is a full binary tree in which all leaves are at the same depth. ? A complete binary tree may also be defined as a full binary tree in which all leaves are at depth n or n-1 for some n. In order for a tree to be the latter kind of complete binary tree, all the children on the last level must occupy the leftmost spots consecutively, with no spot left unoccupied in between any two. For example, if two nodes on the bottommost level each occupy a spot with an empty spot between the two of them, but the rest of the children nodes are tightly wedged together with no spots in between, then the tree cannot be a complete binary tree due to the empty spot. ? An almost complete binary tree is a tree in which each node that has a right child also has a left child. Having a left child does not require a node to have a right child. Stated alternately, an almost complete binary tree is a tree where for a right child, there is always a left child, but for a left child there may not be a right child..
From: Virgil on 17 Jan 2007 16:04 In article <1169050591.632101.147680(a)l53g2000cwa.googlegroups.com>, mueckenh(a)rz.fh-augsburg.de wrote: > Dik T. Winter schrieb: > > > > > > > > > > > 0. > > > > > / \ > > > > > 0 1 > > > > > / \ / \ > > > > > 0 1 0 1 > > > > > | | | | > > > > > 0 1 0 1 > > > > > | | | | > > > > > 0 1 0 1 > > > > > ........................... > > > This finite tree I call: Trauerweide > > > Ok. But this does not help either. The complete tree contains the > > path 0.0101010101...; none of the 'finite' trees contains that path. > > So that path is *not* in the union of the sets of paths of the finite > > trees, while it is in the union of trees. > > So you say 0.0101010101... is in the union of finite trees while ohers > say it is not? Wm cannot even read. > It cannot be in the union of the finite trees, they say, because it is > not in one of the finite trees. 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. Not according to any mathematical definition of rooted trees. Since WM's trees are not the same as mathematical rooted trees, whatever WM says about his trees is irrelevant to properties of mathematical rooted trees.
From: Virgil on 17 Jan 2007 16:09 In article <1169051138.652899.162960(a)a75g2000cwd.googlegroups.com>, mueckenh(a)rz.fh-augsburg.de wrote: > Franziska Neugebauer schrieb: > > > mueckenh(a)rz.fh-augsburg.de wrote: > > > > > Franziska Neugebauer schrieb: > > >> > What I defined as the union of finite trees is the union in the > > >> > sense of set theory. > > >> > > >> I remember that you refused to use usual graph theoretical approach > > >> where a tree is a directed graph. A graph is an ordered pair of a set > > >> of nodes _and_ a set of edges. Please show that in general a union of > > >> trees (ordered pairs of sets of nodes and sets of edges) is a tree. > > > > > > I do not assert that this is so in general. Therefore I will not prove > > > it. > > > > Then please don't call it "union". > > > > > What I said is that the union of the trees with n levels and the > > > tree with m >= n levels is the tree with m levels. > > > > So your "union" is merely a kind of "maximum". For there is no max. > > element n e N the "union of all finite trees" is undefined in the first > > place. > > The union of {1} and {1,2} is {1,2}. This holds for initial segments > of N as well as for finite trees, cut or as Trauerweide. > > > > > This is valid for > > > the levels, for the nodes, for the edges, and for the paths of trees > > > like the following with n = 2 levels. > > > > > >>> > 0. > > >>> > / \ > > >>> > 0 1 > > >>> > / \ / \ > > >>> > 0 1 0 1 > > >>> > | | | | > > >>> > 0 1 0 1 > > >>> > | | | | > > >>> > 0 1 0 1 > > >>> > ........................... > > > > > > > > >> > > > >> > The Equilateral Infinite Triangle (EIT) contains all lines which > > >> > can be enumerated by natural numbers: > > >> > > > >> > 1 0.1 > > >> > 2 0.11 > > >> > 3 0.111 > > >> > ........... > > >> > > >> This is simply a(n infinite) list (sequence) of unary > > >> representations. > > > > > > The diagonal has an infinite number of digits. > > >> > (Otherwise, Cantor's diagonal proof would fail.) > > > > > >> 2. Cantor's proof does not "fail" in that case cause 0.1... is not > > >> _in_ the "EIT"-list (i.e. there is no pair (n, 0.111...) e EIT, > > >> n e N). > > > > > > I said *otherwise* Cantor's proof would fail. "Otherwise" means: If > > > there is no infinite diagonal. > > > > Your claimed (please take a look into the restored context): Not necessary. > > > > i. (1) is true. There is an infinite diagonal (by definition). > > But there is no infinite path by definition? > > > > > If there is an infinite diagonal, however, then there is no reason for > > > the path 0.111... of the union of finite trees to be finite. > > > > The question is whether 0.[01] is in the "union of all finite paths". > > If it exists, then it must be in the union, because there is nothing > remaining outside of the union of all finite trees and all finite > paths which could extend any of its paths. That may be true in WM's misdefinition of trees, but is false in the sort of trees that satisfy actual mathematical definitions of rooted binary trees. Definitions for rooted trees ? A directed edge refers to the link from the parent to the child ? A leaf is a node that has no children. ? The depth of a node n is the length of the path from the root to the node. The set of all nodes at a given depth is sometimes called a level of the tree. ? The height of a tree is the length of the path from the root node to its furthest leaf. ? Siblings are nodes that share the same parent node. ? If a path exists from node p to node q, then p is an ancestor of q and q is a descendant of p. ? The size of a node is the number of descendants it has including itself. Types of binary trees ? A rooted binary tree is a rooted tree in which every node has at most two children. ? A full binary tree, or proper binary tree, is a tree in which every node has zero or two children. ? A perfect binary tree (sometimes complete binary tree) is a full binary tree in which all leaves are at the same depth. ? A complete binary tree may also be defined as a full binary tree in which all leaves are at depth n or n-1 for some n. In order for a tree to be the latter kind of complete binary tree, all the children on the last level must occupy the leftmost spots consecutively, with no spot left unoccupied in between any two. For example, if two nodes on the bottommost level each occupy a spot with an empty spot between the two of them, but the rest of the children nodes are tightly wedged together with no spots in between, then the tree cannot be a complete binary tree due to the empty spot. ? An almost complete binary tree is a tree in which each node that has a right child also has a left child. Having a left child does not require a node to have a right child. Stated alternately, an almost complete binary tree is a tree where for a right child, there is always a left child, but for a left child there may not be a right child..
From: Virgil on 17 Jan 2007 16:11
In article <1169051272.929052.169560(a)a75g2000cwd.googlegroups.com>, mueckenh(a)rz.fh-augsburg.de wrote: > Franziska Neugebauer schrieb: > > > > You can read what _mathematically_ relevant in > > > > ,----[ http://en.wikipedia.org/wiki/Simple_path ] > > No. Just what is mathematically relevant, is not yet given there. What IS mathematically relevant re mathematical trees is not a part of WM's knowledge base. For something that works like a real "union of trees", we start by assuming that all trees and all paths issue from a common root node. We may embed every such finite binary tree in a complete infinite binary tree by extending each finite path infinitely in the opposite direction of its last branching, so each such infinite path is eventually constant", and the original path can be recovered from the infinite path by deleting everything from the last change of direction onwards. Then each finite binary tree extends uniquely to an /incomplete/ infinite binary tree which is a proper subtree of the /complete/ infinite binary tree and the extension restricts uniquely to the original tree. (A tree is /complete/ if and only if every non-leaf node has the same number of child nodes as all others and all paths have the same finite length or are all infinite). Then every finite path in every finite subtree corresponds to a unique infinite and eventually constant path in the complete tree, and every finite tree to an incomplete infinite tree which is a proper subtree of a single compete infinite binary tree. The obvious 'union' of all such incomplete infinite binary trees will necessarily be a subtree of the complete infinite binary tree. So far, I hope WM and I agree. The issue between WM and the rest of the world is whether that union will be a proper subtree of the complete infinite binary tree or will be the entire tree. Since every path in every one of the incomplete infinite binary trees in the union is 'eventually constant', every path in the union of all those trees will also be eventually constant. But most" paths in a complete infinite binary tree are NOT eventually constant, but have infinitely many branchings in each direction both left branchings and right breanchings. But WM's union of trees cannot contain any path which has infinitely many branchings in each direction (is not eventually constant). One can then easily show that the set of paths in WM's union will be countable, but the set of paths in the complete infinite binary tree will be uncountable. As a matter of fact, Cantor's original diagonal proof was of the uncountability of the set of all binary sequences, which is exactly the same thing as the set of all paths in an infinite binary tree. Thus WM's argument that the union of finite binary trees generates a /complete/ infinite binary tree is falsified. |