Partially ordered set

A partially ordered set, or poset, is a set equipped with a reflexive, antisymmetric and transitive binary relation.

A partial order in which the strict predecessors of each node form a well-order. The height of a node is the order type of its predecessors; nodes of a common height form a level. This order-theoretic meaning is distinct from a graph-theoretic tree.

A tree is splitting if every node has two incompatible extensions. This property is additional to height and level-size bounds in a kappa-tree. A cofinal branch through a splitting tree of regular uncountable height produces an equally large antichain by taking off-branch extensions and proceeding beyond their divergence heights. Thus a splitting ${\omega }_1$-tree with countable antichains has no uncountable chains; the nonsplitting chain ${\omega }_1$ itself is a counterexample to omitting splitting.

At a limit level, two nodes with the same predecessor at every smaller level must be equal. This is a uniqueness condition; it need not provide an upper node for every cofinal branch through the lower levels.

Every node has an extension at every higher level below the height of the set-theoretic tree. Equivalently, its extension heights are unbounded in the set-theoretic tree height. Having no terminal nodes alone is weaker.

For a kappa-tree, retain nodes whose extension heights are unbounded in $\kappa$. The retained nodes are predecessor-closed. Each level remains nonempty: otherwise regularity would bound the union of fewer than $\kappa$ bounded extension sets. The same argument above a retained node ensures retained extensions at every later level. Singular height invalidates this proof and the unrestricted conclusion.

For a regular uncountable cardinal number $\kappa$, a set-theoretic tree of height $\kappa$ with nonempty levels of cardinality less than $\kappa$. The regular-height convention is important for the unbounded-extension kernel of a regular tree.

For infinite regular cardinals $\kappa <\lambda$, a $\lambda$-tree whose levels all have size less than $\kappa$ has a cofinal branch. At levels of cofinality $\kappa$, bound all heights distinguishing distinct predecessor chains. The Fodor lemma makes this bound constant on a stationary set; one predecessor at that height occurs stationarily often. The resulting predecessor chains agree below their common heights and unite into a branch through every level. Distinct limit-level nodes with identical predecessor chains do not affect this argument.

A set-theoretic tree of height ${\omega }_1$ with countable levels and at least ${\aleph }_2$ distinct cofinal branches.

Let $\kappa$ be strongly inaccessible cardinal in the ground model and perform the finite Lévy collapse to omega-one. The ground full binary set-theoretic tree of height $\kappa$ has all levels of size less than $\kappa$, so these levels become countable. Its at least $({\kappa }^{+}{)}^M$ ground branches remain distinct. The chain in a partial order condition preserves $({\kappa }^{+}{)}^M$, which is the extension ${\aleph }_2$. The unchanged ground set-theoretic tree therefore witnesses the Kurepa hypothesis.

There exists an ${\omega }_1$-tree with countable levels and at least ${\aleph }_2$ distinct cofinal branches.

There is $\mathcal{F}\subseteq \mathcal{P}({\omega }_1)$ of size ${\aleph }_2$ such that $\{X\cap \alpha :X\in \mathcal{F}\}$ is countable for every $\alpha <{\omega }_1$. Its initial-segment tree, pruned and leveled to be normal, is a Kurepa tree.

A set-theoretic tree of height ${\omega }_1$ with countable levels and no cofinal branch. More generally, a $\kappa$-Aronszajn tree has height a regular uncountable $\kappa$, levels of size less than $\kappa$, and no cofinal branch.

Given coherent coinfinite injections into omega, use all restrictions $e_{\alpha }\upharpoonright \beta$, where $\beta \le \alpha <{\omega }_1$, ordered by proper extension. Every level is countable because its nodes differ finitely from a fixed function on a countable domain. An uncountable chain in a partial order would have unbounded domain heights, and its union would inject ${\omega }_1$ into $\omega$, which is impossible.

An Aronszajn tree with no uncountable tree antichain. A normal splitting Suslin tree yields a Suslin line by a lexicographic ordering followed by Dedekind completion.

A well-pruned set-theoretic tree that is an Aronszajn tree and a Suslin tree gives a forcing with the countable chain condition for forcing: stronger nodes extend weaker ones. The ${\omega }_1$ dense subsets of a forcing order of nodes at or above each level cannot all be met by a filter in an ordered set, since that would produce a cofinal branch. Thus ${\mathrm{MA}}_{{\aleph }_1}$ fails. When the continuum exceeds ${\aleph }_1$, full Martin axiom includes this instance.

An Aronszajn tree that is a union of countably many tree antichains. Equivalently, it admits a map into a countable set that is injective on each chain.

A set-theoretic tree of height ${\omega }_2$, levels of size at most ${\aleph }_1$, and no cofinal branch. The Continuum hypothesis supplies one through the minimal-walk tree.

A set-theoretic tree with one root, extensions of every node at every higher level, at least two immediate successors for every node, and distinct limit-level nodes distinguished by their predecessor chains. If splitting occurs only at later levels, a continuous cofinal selection of levels can enforce immediate splitting.

A maximal chain with nodes at unbounded heights in a set-theoretic tree. Taking predecessor closure gives one node at each level below the tree height.

A set of pairwise incomparable nodes in a set-theoretic tree. A maximal tree antichain has a comparable member for every node of the tree.

A subset of a partially ordered set on which the inherited order is total. The upper-bound hypothesis in Zorn lemma concerns all such subsets, not just countable increasing sequences.

A differential poset is a locally finite graded partially ordered set with a unique minimum, finite ranks, and up and down cover operators satisfying $DU-UD=rI$ for a fixed positive integer $r$. The Young lattice has $r=1$: distinct equal-rank diagrams have equally many common upper and lower covers, and each diagram has one more upper cover than lower cover.

If $DU-UD=I$, commuting every $D$ past every $U$ gives $(D+U{)}^{\ell }={\sum }_{i+j+2m=\ell }\ell !U^i{D}^j/(2^{m}i!j!m!)$. The recurrence follows from $D{U}^i=U^{i}D+i{U}^{i-1}$. Applied to the empty diagram in the Young lattice, it counts oscillating tableaux.

A filter is a nonempty upward-closed subset $G$ of a partial order such that every two members have a common lower bound in $G$. With standard notation for forcing, lower means stronger, so these are exactly the directed filters used to define a generic filter. The projection of a product-generic filter uses these properties before genericity of its factor filters is proved.

The principal filter in an ordered set generated by $p$ contains exactly the elements above $p$. It is upward closed, and $p$ is a common lower bound in the filter for any two of its members. With standard notation for forcing, these are the conditions weaker than $p$. The principal filter need not be a generic filter: a dense set can require a strict strengthening. The compatible-condition filter in a forcing atom determines a ground-model generic filter includes strengthenings as well as weakenings and can therefore be strictly larger.

A linear extension is a total ordering of the elements of a partially ordered set that preserves all its comparisons. For a finite set it can be recorded as a list. If two adjacent elements in that list are incomparable, their interchange is again a linear extension.

Two linear extensions of a finite partially ordered set can be joined using as many admissible adjacent swaps as the inversion count of their relative permutation. Label the current list by the desired positions in the target. An adjacent descent consists of incomparable elements, since comparable elements have the same order in both lists. Swap that descent; its inversion count decreases by one. Iteration sorts the list and gives a path of minimal Coxeter length.

An order-preserving function $f:P\to Q$ between partially ordered sets satisfies $x\le y\Rightarrow f(x)\le f(y)$.

The order dimension of a partially ordered set $(X,<)$ is the least cardinality of a family of total orders on $X$ whose intersection is $<$. Such a family is called a realizer of the partial order.

A partially ordered set is two-dimensional when there are two total orders ${<}_1$ and ${<}_2$ on its ground set such that

A partially ordered set is two-dimensional if every one of its finite induced suborders is two-dimensional. Encode two candidate total orders by propositional variables; every finite collection of the order, extension, and intersection clauses concerns a finite induced suborder, so the propositional compactness theorem supplies two global realizing orders.

A chain in a partially ordered set is a subset in which every two elements are comparable.

An upper bound of a subset $A$ of a partially ordered set is an element $u$ satisfying $a\le u$ for every $a\in A$.

A directed set is a nonempty preorder in which every finite subset has an upper bound. It provides an index set in which any finite collection of stages has a common later stage.

An element $m$ of a partially ordered set is maximal when $m\le x$ implies $x=m$. A poset can have several maximal elements and need not have a greatest element.

An element $m$ of a partially ordered set is minimal when $x\le m$ implies $x=m$.