PlanetMath (more info)
 Math for the people, by the people. Sponsor PlanetMath
Encyclopedia | Requests | Forums | Docs | Wiki | Random | RSS  
Login
create new user
name:
pass:
forget your password?
Main Menu
Owner confidence rating: Medium 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 | get metadata)

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 32 references to this entry.

This is version 1 of branch, born on 2002-07-26.
Object id is 3211, canonical name is Branch.
Accessed 11455 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)