Search All of the Math Forum:

Views expressed in these public forums are not endorsed by NCTM or The Math Forum.

Notice: We are no longer accepting new posts, but the forums will continue to be readable.

Topic: An Argument for the Subroot Node
Replies: 28   Last Post: Mar 14, 2008 8:32 PM

 Messages: [ Previous | Next ]
 Tony Orlow Posts: 3,142 Registered: 8/23/06
Re: An Argument for the Subroot Node
Posted: Mar 11, 2008 1:14 PM

Tonico wrote:
> On Mar 11, 5:42 pm, Tony Orlow <t...@lightlink.com> wrote:
>> G. Frege wrote:
>>> On Mon, 10 Mar 2008 23:44:16 -0500, Tony Orlow <t...@lightlink.com>
>>> wrote:

>>>> So, in conclusion, the "complete" binary tree includes not only a root
>>>> node, but a subroot node, which is its own parent [...].

>>> Such a structure (graph) is not a /tree/ any more (since a tree does not
>>> have cycles _by definition_).
>>> See:
>>> http://en.wikipedia.org/wiki/Tree_(graph_theory)
>>> F.

>> "In graph theory, a tree is a graph in which any two vertices are
>> connected by exactly one path."
>>

> ************************************************************
>
> Where did you get that definition from?

It's what it says on that Wikipedia page G. Frege cited. :)

According to it, the perimeter
> of a triangle is a tree...which, of course, it is not.

That's true. Perhaps Wikipedia wasn't the best source to cite.

>
> A tree is a connected graph without any cycles. Period. This is not an
> "alternative" definition to the nonsense written above. This is THE
> definition of a tree in graph theory and it is not equivalent to what
> you wrote above.
>
> Regards
> Tonio
>
> Ps. By the way, are you trying to make some point by tagging a binary
> ""tree"" the way you did? Where are you heading?

Good question. I'm partly just sharing the idea of extrapolating
backwards above the root node to see what might give rise to it in the
first place. I thought it a nice discovery.

Let's say we number the root on level 0 as 1 and the subroot as 0. As we
number the nodes at each level, we have 2^n nodes up to and including
level n, for n>-1. This would appear to be a power set relation, would
it not? Indeed, if we identify each node by the bit string leading from
subroot 0 to that node, where a 0 is a left branch and a 1 is a right,
then each of those bit strings is a unique binary natural, with no
natural excluded, and alternatively represents a unique subset of the
set of levels, with no subset excluded. A left branch 0 may be
considered to exclude that level, and a right branch 1 to include it.
Thus this countably infinite set of binary naturals IS the power set of
the countably infinite set of levels, and some contradiction ensues
regarding the power set result.

This is related to the question as to the required depth for a binary
tree with a countably infinite number of paths. How deep was that again?

Have a nice day.

Tony

Date Subject Author
3/11/08 Tony Orlow
3/11/08 Virgil
3/11/08 G. Frege
3/11/08 Tony Orlow
3/11/08 Virgil
3/11/08 Tony Orlow
3/11/08 Virgil
3/11/08 G. Frege
3/11/08 J. Antonio Perez M.
3/11/08 G. Frege
3/11/08 G. Frege
3/11/08 Tony Orlow
3/11/08 briggs@encompasserve.org
3/14/08 Tony Orlow
3/14/08 David R Tribble
3/14/08 LudovicoVan
3/11/08 Tony Orlow
3/11/08 J. Antonio Perez M.
3/11/08 Tony Orlow
3/11/08 Tony Orlow
3/11/08 Tony Orlow
3/11/08 LudovicoVan
3/11/08 LudovicoVan
3/14/08 Tony Orlow
3/14/08 LudovicoVan
3/14/08 LudovicoVan
3/11/08 David R Tribble
3/11/08 LudovicoVan
3/11/08 LudovicoVan