Re: Co-optation Today

Rusty Sites wrote:
John Harshman wrote:
Rusty Sites wrote:
John Harshman wrote:
Rusty Sites wrote:
John Harshman wrote:
Rusty Sites wrote:
John Harshman wrote:
r norman wrote:

In other words, every tree can be interpreted to be a nested
hierarchy. You have to do the same with phylogenetic trees. The
nesting requires that a node be associated not only with the species
that occupies that node but with the clade descended from that
species.

I agree. Every tree *can be interpreted* as a nested hierarchy. Or it could be interpreted as a non-nested hierarchy. That's why I say that a tree is a representation of the hierarchy, not the hierarchy itself. This is not a big deal. But a nested hierarchy is best understood and defined in terms of sets, not trees. And of course a natural nested hierarchy is best *explained* by a tree.


Well trees can be defined in terms of sets. From Donald Knuth

A finite set T of one or more nodes such that:

1. there is one specially designated node called the root of the tree, root(T); and
2. the remaining nodes (excluding the root) are partitioned into
m >= 0 disjoint sets T1, ..., Tm, and each of these sets in
turn is a tree. The trees T1, ..., Tm are called the subtrees
of the root.

I think this is properly called a rooted tree.

A rooted tree can be represented as

{a, {b, {c, d}}, {e, f}}

which is a nested hierarchy of sets. I don't see how it could be interpreted as a non-nested hierarchy.

A tree is just a graph. That graph can be interpreted as you like. I gave an example of a tree interpreted as a non-nested hierarchy. Now it's true that any rooted tree can be interpreted as only one nested hierarchy in which its terminal nodes, but not its internal nodes, are elements, but there is no a priori reason why you have to interpret the tree that way. To put it another way, every nested hierarchy implies a tree, but a tree doesn't imply anything; it's just a topological figure.


I am not sure how you are using graph, but in the mathematical sense a tree is a special case of a graph. Every tree is a graph, but not every graph is a tree. In the most general definition of a tree, there is no specified root node, so there is not a one to one correspondence to a nested hierarchy. (At least, a root has to be specified to construct a nested hierarchy) A rooted tree (which is commonly what people think of when they speak of trees) does have a specified root so it avoids the problem. Your definition of nested hierarchy,

I agree that a nested hierarchy can be described using a rooted tree, and that each nested hierarchy corresponds to exactly one rooted tree. By "graph" I meant a figure composed of branches and nodes, each node connecting either 3 or more branches or being at the end of only one branch. In systematics, a tree is a graph in which there is one and only one path between any pair of nodes. A rooted tree is a tree in which a point on one of the branches has been designated the root node. Terminology in mathematics may be different.

From ancient memory, a graph is a set of nodes with at most one arc from one node to another. That would include cases where there is no path from some nodes to other nodes. A connected graph adds the requirement that there be at least one path between any two nodes. I am sure that the correct definition, if I am not giving it, is different than that which you stated.

Sorry, I got ahead of myself. I meant merely to say that a graph was a figure of branches and nodes. Your requirement eliminates redundant branches, which sounds good. Now if I recall a tree is called an acyclic connected graph, which means that there is no path from a node back to the same node without retracing steps. And a rooted tree adds a direction to each branch, i.e. away from the root. In systematics at least, you are not allowed to have a node connecting only two branches, except for the root node. And we don't generally consider the root to be a real node.

Here: a nested hierarchy is a set of groups in which each group has one of two relationships with each other group; either the two groups are wholly disjunct, or one group is entirely included within the other. Partially overlapping groups are right out. Phylogenies can further be described as natural nested hierarchies: only one hierarchical arrangement of groups will work.

is, I believe entirely equivalent to the definition given for a rooted tree if a common ancestor of all members of the hierarchy is included. Otherwise, a nested hierarchy might contain no root node. It would then be a set of rooted trees. The groups in your definition translate to subtrees. Given two subtrees, they are either disjoint or one contains the other.

Well, in practice we never have a common ancestor. Instead we designate some particular branch as containing the root node, because of information extraneous to the tree itself. But a tree described as nested sets wouldn't seem to need an element identified as the ancestor. Why, mathematically, is a common ancestor needed? It would seem to be a superfluous member of the set, since the first division of the set defines a root.

I think {{a, b}, {c, d}} would represent a nested hierarchy, but no tree could be constructed from it without an implied root node.

But there is an implied root node (at least in systematics); the root must be between {a,b} and {c,d}. If the root were elsewhere those two subsets would not exist. There are 15 possible rooted trees with those four elements, but all others would have different subsets. For example, the tree {a,{b, {c,d}}} has an implied root between a and the rest.


Now I realize that my set notation for trees doesn't work. There is no place to put a root. I know there is such a notation, but without a current ACM or IEEE membership, I can't look at the papers I found that seem to address the issue online. Anyway, when I said "if a common ancestor of all members of the hierarchy was included", I was thinking of an implied node like the ancestor of all life, not necessarily an actual ancestor.

Right, but I don't see why you need any explicit representation of the root. Given that set notation, which works just fine (and is the notation used by systematists), there is only one possible place for the root to be. So what's the problem?

.

Relevant Pages

  • Re: Co-optation Today
    ... hierarchy. ... hierarchy is best *explained* by a tree. ... of the root. ... which is a nested hierarchy of sets. ...
    (talk.origins)
  • Re: Co-optation Today
    ... hierarchy. ... But a nested hierarchy is best understood and defined in ... hierarchy is best *explained* by a tree. ... definition of a tree, there is no specified root node, so there ...
    (talk.origins)
  • Re: Co-optation Today
    ... hierarchy. ... But a nested hierarchy is best understood and defined in ... hierarchy is best *explained* by a tree. ... definition of a tree, there is no specified root node, so there ...
    (talk.origins)
  • Re: Co-optation Today
    ... hierarchy. ... But a nested hierarchy is best understood and defined in ... hierarchy is best *explained* by a tree. ... definition of a tree, there is no specified root node, so there ...
    (talk.origins)
  • Re: Co-optation Today
    ... hierarchy. ... That's why I say that a tree is a representation of the hierarchy, ... But a nested hierarchy is best understood and defined in terms of sets, ... of the root. ...
    (talk.origins)