Re: Co-optation Today

On Jan 9, 9:15 pm, John Harshman <jharshman.diespam...@xxxxxxxxxxx>
wrote:
Rusty Sites wrote:
John Harshman wrote:
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?

No practical problem, but I said there was a one to one correspondence
between the set notation and trees, but that's not true unless the set
notation is augmented to include a root.  In your case, it isn't
necessary because the root doesn't require any value.  In general, it does.

Wouldn't your notation work in that case? If you want x to be the root,
you can easily have the set {x, {a,b},{c,d}}. But I suppose there needs
to be some kind of explicit notation for the root, because I could also
interpret this as a trichotomy, with x a terminal node at the end of
some branch. In phylogenetics, the root can't have a value, because
there is no way to estimate states at the root node. And we can know
that the root is somewhere along a particular branch, but we can't say
where along that branch.

Sounds like you need one of them there TomTom's.


.

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. ... 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)
  • 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)