Description:
Definitions from Shannon [1992] for form [86 A(\(\alpha\))]
Content:
Definitions from Shannon [1992] for form [86 A(\(\alpha\))]
Definition: Assume \((P,\le)\) is a quasi-order (i.e.,reflexive and transitive).
- \(x, y\in P\) are incompatible if there is no \(z\in P\)such that \(z\le x\) and \(z\le y\).
- \(I\subseteq P\) is an antichain if any two different elements of \(I\) are incompatible.
- A partially ordered set \((P,\le)\) is a tree iff \(\forall x \in P\), \(\{y\in P: y\le x\}\) is well ordered by \(\le\) and \((P,\le)\) has a unique minimal element.
Assume \((P,\le)\) is a tree.
- If \(x\in P\) then \(ht(x)\) (the height of \(x\)) is the order type of \(\{y\in P: y \le x\}\).
- lev\(_{\alpha}(P) = \{x\in P: ht(x) = \alpha\}\).
- The height of \(P\) is the least \(\alpha\) such that lev\(_\alpha(P) = \emptyset\).
- A branch in \((P,\le)\) is a maximal chain.
- If \((P,\ge)\) is an upside down tree then a strong antichain in \((P,\ge)\) is an antichain that has at most one element from each level of \((P,\le)\).
Howard-Rubin number:
119
Type:
Definitions
Back