Partially ordered set

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

Every subset having an upper bound has a least upper bound. If the empty subset is included, a nonempty such partially ordered set has a least element. This condition differs from a directed-complete partial order: a directed set need not have an upper bound.

A partially ordered set in which, for every $x$, the elements way-below $x$ form a directed set with least upper bound $x$. Directed least upper bounds other than these approximating ones need not exist.

A partially ordered set in which the compact elements below each element form a directed set with that element as their least upper bound.

Let $K_x$ be the directed set of compact elements below $x$, with least upper bound $x$, and put $A_x=\{y:y\ll x\}$. A compact element $k\le x$ belongs to $A_x$: a directed set whose least upper bound is at least $x$ also has least upper bound at least $k$, so the definition of $k\ll k$ supplies an element above $k$. Hence $K_x\subseteq A_x$.

If $y_1,y_2\in A_x$, apply the way-below relation to $K_x$ to find $k_1,k_2\in K_x$ above them. Since $K_x$ is directed, it contains a common upper bound $k$ for $k_1,k_2$. This $k$ belongs to $A_x$, proving that $A_x$ is directed. Every member of $A_x$ is below $x$, while $K_x\subseteq A_x$ has least upper bound $x$. Therefore $x$ is the least upper bound of $A_x$, which is the defining property of a continuous poset.

A continuous poset that is also a directed-complete partial order.

Give the real interval $[0,1]$ its usual total order. Every nonempty directed set has a least upper bound in the real interval, so it is a directed-complete partial order. If $x<y\le \sup D$, some $d\in D$ exceeds $x$; otherwise $x$ would be an upper bound for $D$. Also $0\ll 0$, since every member of a nonempty $D$ is at least zero. For $x>0$, the increasing sequence $x(1-1/n)$, $n\ge 1$, has least upper bound $x$ but never reaches it, so $x/\ll x$. Together with $x\ll y\Rightarrow x\le y$, this proves the displayed way-below relation.

For each $y>0$, the elements way-below $y$ form $[0,y)$, a directed set with least upper bound $y$; for $y=0$ they form $\{0\}$. Thus this is a continuous poset. Its only compact element is zero, so it is not an algebraic partially ordered set.

In a partially ordered set, $x\ll y$ means that every nonempty directed set $D$ whose least upper bound exists and satisfies $y\le \sup D$ contains some $d$ with $x\le d$. Taking $D=\{y\}$ shows that $x\ll y$ implies $x\le y$; the converse need not hold. Some formulations quantify over the empty directed set as well; this changes the behaviour at the least element and must be specified.

An element that is way-below itself.

The partial order on nonempty closed integer intervals given by subset inclusion. The least upper bound of two such intervals is their interval hull $[\min (l,l^{\prime }),\max (u,u^{\prime })]$. The hull can contain points absent from both original intervals, so it need not equal their union.

A subset $U$ of a partially ordered set is an upper set when $x\in U$ and $x\le y$ imply $y\in U$. The upward closure $\uparrow A=\{y:\exists a\in A,a\le y\}$ is the smallest upper set containing $A$. Both union and intersection preserve this property.

An upper set generated by a finite set $A$ is represented by the minimal elements of $A$. Removing a nonminimal generator preserves the upward closure. If each pair has a least upper bound, then $\uparrow A\cap \uparrow B=\uparrow \{a\vee b:a\in A,b\in B\}$, so finite generators support intersection without enumerating the potentially infinite represented sets.

An irreflexive transitive comparison whose induced incomparability relation is transitive. Incomparability is then an equivalence relation, and its classes are totally ordered by the comparison. A comparison-based sorting algorithm can treat incomparable elements as ties; a merge algorithm that takes from the left input on ties preserves stable sorting. Ordinary ordering on real numbers is an example; machine NaN values require separate handling.

Given a partially ordered set $B$ and a set $A$, the pointwise order on the function space of functions $A\to B$ compares their values at every argument. It is a partial order: reflexivity and transitivity hold at every argument, and antisymmetry follows because two functions equal at every argument are equal. Even if $B$ has a total order, this function space need not: the two functions on $\{0,1\}$ with values $(0,1)$ and $(1,0)$ are incomparable when $B=\mathbb{R}$.

Take disjoint antichains $P,C$ and place every element of $P$ below every element of $C$. Together with equality these comparisons define a partial order: a strict step always moves from $P$ to $C$, so there cannot be a strict two-step path or a reverse comparison.

If both levels have at least two elements, a subset $S$ has an upper bound exactly when it contains at most one element of $C$. When it contains one such element $c$, that element is its maximum and its only upper bound. A singleton $\{p\}\subseteq P$ has maximum and least upper bound $p$. A subset of $P$ with at least two elements has all of $C$ as upper bounds and has no least upper bound, because these elements are incomparable. The empty subset has all of $P\bigsqcup C$ as upper bounds and has no least upper bound. These cases prove the complete classification.

A Hasse diagram draws a finite partially ordered set using one point for each element and an upward line from $x$ to $y$ for each cover relation $x\prec y$. It omits reflexive loops and comparisons already implied by paths. Line crossings are not additional elements. In a finite partially ordered set, following upward paths recovers exactly the original comparisons. The diagram is named after Helmut Hasse.

In a partially ordered set, $y$ covers $x$ when $x<y$ and there is no $z$ with $x<z<y$. Thus a cover relation records an immediate increase, rather than every comparable pair. For a finite partially ordered set, every strict comparison can be obtained by chaining cover relations.

A subset $I$ of a partially ordered set such that $x\in I$ and $y\le x$ imply $y\in I$. Thus membership forces all smaller elements to belong as well. This definition concerns an order, rather than an ideal of a ring.

For an order ideal in a finite rectangular grid with coordinatewise partial order, occupied cells in each row form a left prefix. Their lengths form a nonincreasing sequence $r_y$. Conversely, any nonincreasing sequence of valid row lengths specifies exactly one such order ideal, giving an abstraction function with no redundant per-cell information.

Removing all occupied cells with $x\ge a$ and $y\ge b$ replaces $r_y$ by $\min (r_y,a)$ for $y\ge b$ and leaves earlier rows unchanged. The new lengths remain nonincreasing: affected rows preserve their mutual order, and the first affected row only decreases. For a legal removal, the boundary immediately below it was already at least $a$. A cached sum of row lengths can be updated by subtracting the decreases. This yields constant-time membership and count queries, linear storage, and an update linear in the number of affected rows.

A downward-closed subset of a finite product grid can be represented by nonincreasing column heights. Occupancy is $0\le y<h(x)$; the condition $h(0)\ge \cdots \ge h(N-1)$ is exactly closure toward smaller coordinates. Removing the northeast rectangle anchored at a legal $(x,y)$ truncates each height to its right to $\min (h(i),y)$, preserving closure. This represents a potentially quadratic number of occupied cells using a linear number of boundary values.

The zeta transform on a finite partially ordered set sends $f$ to $F(x)={\sum }_{y\le x}f(y)$. The subset zeta transform is the case where the order is inclusion of subsets.

In a partially ordered set $P$, an upper set $U$ satisfies $x\in U$ and $x\le y\Rightarrow y\in U$; a lower set $L$ satisfies $x\in L$ and $y\le x\Rightarrow y\in L$. The complement of a set exchanges the two conditions: if $x\notin U$ and $y\le x$, then $y\in U$ would force $x\in U$, so $P\setminus U$ is lower. In a Boolean lattice ordered by inclusion, these are the up-set and down-set conditions.

A greatest element lies above every member of an ordered set, and a least element lies below every member. Antisymmetry makes either unique if it exists. A greatest element is maximal, but a maximal element need not be greatest.

An element is greatest when every element of the ordered set is less than or equal to it.

An element $\perp$ of a partially ordered set $P$ is a least element if $\perp \le x$ for every $x\in P$. A least element is unique: two such elements are below each other, so antisymmetry makes them equal.

A maximal element has no strictly greater element; a minimal element has no strictly smaller one. Either can be nonunique, unlike a greatest or least element. These notions are defined for arbitrary partially ordered sets.

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 is maximal when there is no strictly greater element of the partially ordered set. This is different from being a greatest element, which must dominate every other element.

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

An upper bound of a subset is an element above every member, and a lower bound is below every member. They need not lie in the subset or be unique. Infimum and supremum are the greatest lower and least upper bounds when those exist.

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$.

The least upper bound in a partially ordered set of a subset $A$, when it exists. It bounds every element of $A$ and is at most every other upper bound. For two elements it is written $x\vee y$; an empty join is a least element.

For $D=\{(x,y):x^2+y^2<1\}$, the product order gives least upper bound $(1,1)$, because each coordinate has supremum one. The lexicographic order instead has no least upper bound. Every point $(1,v)$ is an upper bound, but $(1,v-1)$ is a strictly smaller upper bound; a point with first coordinate below one cannot bound the disc. The same geometric set therefore has different order-completeness behavior under the two partial orders. Neither conclusion is determined by the usual drawing alone.

A real-valued function on a partially ordered set is increasing when it preserves its order. Indicators of increasing events are examples. In spin or edge configuration spaces the order is coordinatewise, so increasing observables grow when a zero coordinate is replaced by one. Positive association of random variables concerns pairs of such observables, and stochastic domination compares their expectations.

Every partial order has a total order extension. Apply Zorn's lemma to extensions ordered by inclusion: the union of a chain is a partial order. If a maximal extension leaves two elements incomparable, adjoining one comparison and taking its transitive closure of a relation creates no cycle, contradicting maximality. Quotienting a preorder by its indifference relation and lifting a total order gives a complete weak-order extension preserving its strict part.

Every finite partially ordered set can be partitioned into as many chains in a partial order as its largest antichain. Reachability in an acyclic directed graph is a partial order, so the theorem supplies chains which can be expanded into directed paths, possibly overlapping at intervening vertices.

A lower bound of a subset $S$ of a partially ordered set is an element $\ell$ no greater than every member of $S$. For minimization, a number below every feasible objective value is therefore a lower bound on the optimum; a relaxation often provides such a certificate.

// Target: mathematical-optimization.bigb

A lower bound in a partially ordered set which is greater than or equal to every other lower bound. For a pair it is written $a\wedge b$; an empty meet, when it exists, is the greatest element. In a complete lattice, every subset has a meet. In the open-set frame, this is the interior of the intersection, with finite meets given by the intersections themselves.

A chain-complete partially ordered set has a supremum for every chain, with the empty-chain condition requiring a least element if empty chains are included. This implies the weaker upper-bound hypothesis of Zorn lemma, which requires only that each chain have some upper bound, not necessarily a least one. Some treatments use “chain-complete” for that weaker condition, so the convention should be specified. In the inclusion order on lattice ideals avoiding a specified element, the union of a nonempty chain is an ideal and is its supremum. This union observation is the step needed to apply Zorn in prime-ideal separation arguments.

A family of order-completeness notions used in semantics: in particular, a directed-complete partial order has every directed join, while a pointed one additionally has a least element. The precise completeness condition should be specified, since this terminology is not synonymous with complete lattice.

A partially ordered set is directed-complete if every directed set in it has a least upper bound. A complete lattice is directed-complete. Conversely, directed completeness together with all finite joins, including the empty join, gives arbitrary joins: take the directed set of joins of finite subsets.

Take two increasing countable chains sharing a least element $\perp$ and a greatest element $\top$, with interiors $a_1<a_2<\cdots$ and $b_1<b_2<\cdots$ and no comparisons between branches. Each entire interior chain has $\top$ as its least upper bound. A directed set meeting both interiors must contain $\top$. Otherwise it lies within one branch, where it has either a greatest member or least upper bound $\top$. This proves that the partially ordered set is a directed-complete partial order.

The only element way-below $a_n$ is $\perp$. Indeed, an element way-below $a_n$ must be below $a_n$, but every positive $a_m\le a_n$ fails the way-below relation when tested against $\{b_1,b_2,\dots \}$: its least upper bound is $\top \ge a_n$, yet it has no member above $a_m$. Nonempty directed sets always contain an element above $\perp$, so $\perp \ll a_n$. Thus the elements way-below $a_n$ have least upper bound $\perp \ne a_n$, and this is not a continuous poset.

A monotone map preserving suprema of nonempty directed sets. Between pointed domains it need not send bottom to bottom. The pointwise directed supremum of a directed family of such maps is again Scott continuous: interchange the two directed suprema in ${\sup }_f{\sup }_{x\in A}f(x)$.

A directed-complete partial order with a least element. Here directed suprema concern nonempty directed sets. Morphisms are Scott continuous maps and need not preserve the least element. Requiring strictness would change the category and its cartesian-closure argument.

For Scott continuous maps $e:D\to E$, $p:E\to D$, these two identities say that $D$ is embedded in $E$ and that projection followed by embedding approximates from below. Such pairs lift to endomorphism spaces by $f\mapsto efp$ and $g\mapsto pge$. Their composite on the smaller space is the identity, and the other composite is $g\mapsto (ep)g(ep)\le g$.

For $D_{n+1}=[D_n\to D_n]$ with recursively lifted embedding-projection pairs, form coherent sequences $x_n=p_n{x}_{n+1}$, ordered componentwise. Stage projections $P_n$ and embeddings $E_n$ satisfy $P_n{E}_n=\mathrm{id}$, $E_n{P}_n\uparrow \mathrm{id}$. A coherent family $f_n\in [D_n\to D_n]$ induces $f={\sup }_n{E}_n{f}_n{P}_n$; conversely $f_n=P_{n}f{E}_n$. These constructions are inverse. Removing the initial coordinate of the coherent sequence identifies this function-space limit with the original domain limit.

The Scott continuous maps from $D$ to $E$, ordered pointwise. A nonempty directed family has pointwise supremum, and the constant-bottom function is least. Joint evaluation is Scott continuous: for a directed family of pairs $(f_i,x_i)$, directedness makes diagonal values cofinal among all $f_i(x_j)$. Evaluation and currying make the category of pointed complete partial orders and non-strict Scott continuous maps a Cartesian closed category.

For a directed set of Scott continuous maps $f_i:D\to E$, its least upper bound is $f(x)={\sup }_i{f}_i(x)$. The two directed suprema over $i$ and over inputs commute, proving that $f$ remains Scott continuous. Thus the function space of complete partial orders is a complete partial order.

Let $f$ be order-preserving and inflationary on a directed-complete partial order. Define $xRy$ when every set containing $x$ and closed under $f$ and directed joins contains $y$. This is a partial order refining $\le$. The order-preserving maps $h$ satisfying $xRh(x)$ form a composition-closed family $H$. The values $Hx$ are directed, since $h(k(x))$ bounds $h(x)$ and $k(x)$. Their least upper bound $h_0(x)$ lies in every such closed set containing $x$, so $h_0\in H$. Then $f\circ h_0\in H$ gives $f(h_0(x))\le h_0(x)$, while inflationarity gives the reverse inequality. If $p=f(p)$ and $x\le p$, the lower set $\{y:y\le p\}$ is closed, proving $h_0(x)\le p$. Thus $h_0(x)$ is the least fixed point of $f$ above $x$.

The product order on a Cartesian product of partially ordered sets compares every coordinate separately. Points that improve one coordinate and worsen another are incomparable. It is generally a partial order, not a total order.

A maximal external point of a finite set has no other point strictly larger in every coordinate. This weak nondominance differs from a maximal element in the product order when coordinate ties exist: for example $(1,0)$ passes the weak test against $(1,1)$ but is not maximal in the product order. In an independent continuous-coordinate random sample, ties have probability zero, so the two notions coincide almost surely.

For $n$ independent uniform points in a rectangle, condition on one point with normalized coordinates $(x,y)$. It is a maximal external point if all others avoid the upper-right rectangle of area $(1-x)(1-y)$, giving conditional probability $[1-(1-x)(1-y){]}^{n-1}$. Integrating gives $H_n/n$, where $H_n$ is a harmonic number. Linearity of expectation over the $n$ indicator random variables gives $\mathbb{E}{K}_n=H_n$. The same answer holds for independent continuous coordinate distributions, by transforming each coordinate with its distribution function.

A strict partial order is an irreflexive transitive relation. In a classical set, it corresponds to a partial order through reflexification, but recovering the strict relation from the weak one requires inequality. In an arbitrary topos, this reverse operation need not be geometric or define an inverse interpretation.

A strict partial order that is a serial relation has no finite nonempty first-order model. If the domain had $N$ elements, seriality would produce a chain of $N+1$ successive elements. The pigeonhole principle supplies a repeated element, and transitivity along the resulting cycle contradicts irreflexivity. An infinite example is the usual strict order on the natural numbers: every element has its successor. The nonempty-domain convention is essential; the displayed universal conditions hold vacuously on an empty domain if such domains are permitted.

Reflexification turns a strict partial order into a partial order. Reflexivity is immediate, transitivity follows by the four disjunction cases, and antisymmetry follows because two opposed strict comparisons imply a forbidden self-comparison. The construction uses only coherent logic, so is preserved by inverse image functors of geometric morphisms.

If $\mathrm{Ch}(P)$ is the inclusion-ordered collection of every chain in a partial order, including the empty chain, it has no order-preserving injection into $P$. Supposing $j$ exists, recursively set $p_{\alpha }=j(\{p_{\beta }:\beta <\alpha \})$ for $\alpha <h(P)$. By induction the earlier values form a chain; its proper initial chains are distinct, so monotonicity and injectivity make $p_{\alpha }$ strictly greater than every earlier value. This would inject the Hartogs ordinal into $P$.

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.

For an uncountable cardinal $\kappa$, this convention requires a cofinal branch in every separated rooted tree of height $\kappa$ with fewer than $\kappa$ immediate successors per node, without bounding level sizes. It is stronger than the usual tree property away from inaccessible cardinals. If $\mathrm{cf}(\kappa )<\kappa$, attach chains of cofinally increasing lengths below $\kappa$ above fewer than $\kappa$ children of one root; this contradicts the property. If $2^{\lambda }\ge \kappa$ for $\lambda <\kappa$, take a binary tree through level $\lambda$, choose $\kappa$ distinct nodes there, and attach to the $\xi$th a chain of length $\xi$. It has height $\kappa$, binary branching, and no cofinal branch. Hence the property implies that $\kappa$ is a strongly inaccessible cardinal. At such a cardinal a separated tree with small immediate branching has small levels, so this convention agrees with the usual tree property. It is not the different notion called the strong tree property in modern set theory.

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 an infinite cardinal $\kappa$, the tree property says that every tree of height $\kappa$ with nonempty levels of cardinality less than $\kappa$ has a cofinal branch. In the all-trees-of-size-$\kappa$ convention it also forces regularity: disjoint chains of lengths cofinal in a singular $\kappa$ form a counterexample. It does not, by itself, imply strong inaccessibility. A strong limit cardinal with the tree property satisfies the self-partition relation by applying it to the end-homogeneous coloring tree. At a strongly inaccessible cardinal this is the usual weak-compactness characterization.

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.

Construct countable levels of bounded increasing rational sequences, maintaining the bounded rational extension property. At successor stages append every allowed rational. At a countable limit, handle each earlier-node/rational-cap pair by a cofinal sequence of extensions with values approaching a rational strictly below the cap. Its union has that rational supremum. Countably many requirements give a countable new level. Strictly increasing labels exclude uncountable chains, and label fibers are tree antichains, so the result is a special Aronszajn tree.

For every earlier node and rational cap above its label, an extension at each later level remains below the cap. In the rationally labelled Aronszajn tree construction this reserves space for limit-stage unions. Choosing an intermediate rational and forcing successive values toward it ensures a rational supremum and strictly increasing labels even at limit levels.

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)$.

An inflationary map on a partially ordered set satisfies $x\le f(x)$ for every $x$. This condition is distinct from being order-preserving.

A strict order-preserving function preserves strict comparisons. Between strict partial orders it may identify incomparable elements. Between strict total orders it is necessarily injective, and in a finite chain it is exactly an increasing injection. It need not reflect comparisons between incomparable elements of general partial orders.

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.

The order induced on this subset is a total order.

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.

In a finite nonempty directed set, repeatedly take an internal common upper bound of the element reached so far and the next element. The final member is above every element of the directed set and is therefore its greatest element and least upper bound.