PlanetMath (more info)
 Math for the people, by the people.
Encyclopedia | Requests | Forums | Docs | Wiki | Random | RSS  
Login
create new user
name:
pass:
forget your password?
Main Menu
Owner confidence rating: Very low Entry average rating: No information on entry rating
branch (Definition)

A subset $ B$ of a tree $ (T,<_T)$ is a branch if $ B$ is a maximal linearly ordered subset of $ T$. That is:

  • $ <_T$ is a linear ordering of $ B$
  • If $ t\in T\setminus B$ then $ B\cup \{t\}$ is not linearly ordered by $ <_T$.

This is the same as the intuitive conception of a branch: it is a set of nodes starting at the root and going all the way to the tip (in infinite sets the conception is more complicated, since there may not be a tip, but the idea is the same). Since branches are maximal there is no way to add an element to a branch and have it remain a branch.

A cofinal branch is a branch which intersects every level of the tree.



"branch" is owned by Henry.
(view preamble)

View style:

See Also: tree (set theoretic), example of tree (set theoretic)

Also defines:  branch, cofinal branch
Log in to rate this entry.
(view current ratings)

Cross-references: level, intersects, infinite sets, root, nodes, linearly ordered, tree, subset
There are 45 references to this entry.

This is version 1 of branch, born on 2002-07-26.
Object id is 3211, canonical name is Branch.
Accessed 9022 times total.

Classification:
AMS MSC05C05 (Combinatorics :: Graph theory :: Trees)
 03E05 (Mathematical logic and foundations :: Set theory :: Other combinatorial set theory)

Pending Errata and Addenda
None.
Discussion
Style: Expand: Order:
forum policy

No messages.

Interact
post | correct | update request | add derivation | add example | add (any)