Notes

Description: Definitions for forms [10 F], [14 M], [14 N], [43 H], [106 A], Form 216, and Form 249.

Content:

Definitions for forms [10 F], [14 M], [14 N], [43 H], [106 A], Form 216, and Form 249.

Definition:

  1. A tree is a connected undirected graph without circuits one of whose vertices is designated as the origin.
    Note that a tree may also be defined as a partially ordered set \((P,\le)\) with a least element and with the property that for any element \(x\in P\) the set of predecessors of \(x\)is a finite set which is linearly ordered by \(\le\).  Every tree in this sense is also a tree in the sense of definition 1 (under the obvious translation) and vice versa.  Note also that the definition of tree for form [86 A(\(\alpha\))] in Note 119 differs from the definition given above.
  2. The number of vertices on the unique path connecting a vertex \(v\) with the origin is the level of \(v\),\(l(v)\). (Thus the set of vertices of a tree can be decomposed  into an at most denumerable  set  of  levels.)
  3. A vertex \(v'\) is a successor of a vertex \(v\) if \(v\)and \(v'\) are connected by an edge and \(l(v') = l(v) + 1.\)
  4. A tree is finite if its set of vertices is finite and locally finite if each vertex has only finitely many successors.
  5. A branch in a tree is a maximal path beginning at the origin. If \(v\) and \(v'\) are on the same branch, then \(v'\)dominates \(v\) if \(l(v')\ge l(v)\).
    König's lemma states that any infinite locally finite tree has an infinite branch.
  6. An \(\omega\)-tree is a locally finite tree with at least one vertex of level \(n\) for each \(n\in\omega\).
  7. A subtree of a tree \((P,\le)\) is a subset of \(P\) which is a tree under the induced ordering and which is closed under predecessor.
  8. An antichain in a tree \((P,\le)\) is a subset of \(P\) whose elements are pairwise incomparable.  (Note that this differs from the definition of antichain used in form [86 A(\(\alpha\))] and given in Note 119.)
  9. Let \(T\) be a collection of locally finite trees (not necessarily pairwise disjoint). By a vertex or a level of \(T\), we mean a vertex or a level of some tree in T.
  10. If \(v\) and \(v'\) are vertices of \(T\), then \(v'\) dominates \(v\) in \(T\) if \(v'\) dominates\(v\) in some tree in T.
  11. Let \(S\) be a set of vertices of \(T\).  \(S\) pierces a level \(l\) of \(T\) if \(|S\cap l| = 1\).
  12. \(S\) is consistent if for  every \(v, v'\)in \(S\) there is a \(v''\) which dominates them both in T.

Howard-Rubin number: 21

Type: Definitions

Back