# Partially ordered set

A partially ordered set, or poset, is a set together with a binary relation that is reflexive, antisymmetric, and transitive, so that some pairs of elements are ranked relative to each other while others may be unrelated<sup>[1](https://stats.libretexts.org/Bookshelves/Probability_Theory/Probability_Mathematical_Statistics_and_Stochastic_Processes_%28Siegrist%29/01%253A_Foundations/1.04%253A_Partial_Orders)</sup>. The pair \( (S, \preceq) \) is called a partially ordered set when \( \preceq \) satisfies the three defining properties: \( x \preceq x \) for every \( x \) (reflexivity); \( x \preceq y \) and \( y \preceq x \) imply \( x = y \) (antisymmetry); and \( x \preceq y \) with \( y \preceq z \) imply \( x \preceq z \) (transitivity)<sup>[1](https://stats.libretexts.org/Bookshelves/Probability_Theory/Probability_Mathematical_Statistics_and_Stochastic_Processes_%28Siegrist%29/01%253A_Foundations/1.04%253A_Partial_Orders)</sup>. The word "partial" marks the contrast with a total order, in which every pair of elements is comparable<sup>[2](https://datafield.dev/discrete-mathematics/part-02/chapter-13/)</sup>.

| Key fact | Detail |
|---|---|
| Defining properties | Reflexive, antisymmetric, transitive; the pair \( (S, \preceq) \) is the poset<sup>[1](https://stats.libretexts.org/Bookshelves/Probability_Theory/Probability_Mathematical_Statistics_and_Stochastic_Processes_%28Siegrist%29/01%253A_Foundations/1.04%253A_Partial_Orders)</sup> |
| Standard examples | \( (\mathbb{Z}, \le) \) is a total order; \( (\mathcal{P}(S), \subseteq) \) has most pairs incomparable; divisibility \( \mid \) orders the positive integers<sup>[2](https://datafield.dev/discrete-mathematics/part-02/chapter-13/)</sup><sup> • </sup><sup>[1](https://stats.libretexts.org/Bookshelves/Probability_Theory/Probability_Mathematical_Statistics_and_Stochastic_Processes_%28Siegrist%29/01%253A_Foundations/1.04%253A_Partial_Orders)</sup> |
| Domain matters | Divisibility is antisymmetric on \( \mathbb{Z}^{+} \) but not on \( \mathbb{Z} \), since \( 2 \mid -2 \) and \( -2 \mid 2 \) with \( 2 \ne -2 \)<sup>[2](https://datafield.dev/discrete-mathematics/part-02/chapter-13/)</sup> |
| Dimension | Introduced by Dushnik and Miller (1941): the minimum number of linear orders whose intersection is the poset<sup>[3](https://arxiv.org/abs/1501.01147)</sup> |
| Complexity | Testing whether dimension \( \le k \) is NP-complete for \( k \ge 3 \) (Yannakakis, 1982); dimension at most 2 has efficient algorithms<sup>[3](https://arxiv.org/abs/1501.01147)</sup> |
| Distributed systems | Lamport's 1978 happened-before relation is a strict partial order on the events of a distributed system<sup>[4](https://www.scitepress.org/PublishedPapers/2006/15724/pdf/index.html)</sup> |
| History | First clear formulation attributed to Felix Hausdorff; order axioms considered by Leibniz around 1690; Cantor first defined the totally ordered set accurately<sup>[5](https://encyclopediaofmath.org/wiki/Partially_ordered_set)</sup> |

## Definition and derived relations

A binary relation on a set \( S \) is formally a subset of \( S \times S \), and the notation \( x \preceq y \) records that the pair \( (x, y) \) belongs to it<sup>[6](https://appliedcombinatorics.org/book/s_background_order.html)</sup>. From a partial order \( \preceq \) several other relations arise naturally: the inverse \( \succeq \), the strict order \( \prec \) defined by \( x \prec y \) if and only if \( x \preceq y \) and \( x \ne y \), and the comparability relations \( \perp \) (related one way or the other) and \( \parallel \) (unrelated, or incomparable)<sup>[1](https://stats.libretexts.org/Bookshelves/Probability_Theory/Probability_Mathematical_Statistics_and_Stochastic_Processes_%28Siegrist%29/01%253A_Foundations/1.04%253A_Partial_Orders)</sup>. The strict relation \( \prec \) is transitive and irreflexive, and it completely determines \( \preceq \), since \( x \preceq y \) holds exactly when \( x \prec y \) or \( x = y \)<sup>[1](https://stats.libretexts.org/Bookshelves/Probability_Theory/Probability_Mathematical_Statistics_and_Stochastic_Processes_%28Siegrist%29/01%253A_Foundations/1.04%253A_Partial_Orders)</sup>.

**Terminology varies across the literature.** Some texts call the reflexive version a weak partial order and the irreflexive, transitive version a strict or strong partial order<sup>[1](https://stats.libretexts.org/Bookshelves/Probability_Theory/Probability_Mathematical_Statistics_and_Stochastic_Processes_%28Siegrist%29/01%253A_Foundations/1.04%253A_Partial_Orders)</sup>. The irreflexive transitive relation is also called a quasi order in some sources, which note that a second, different convention exists in which "quasi order" means a reflexive and transitive relation, that is, a preorder<sup>[7](https://www.cs.odu.edu/~toida/nerzic/content/relation/order/order.html)</sup>.

## Standard examples

Three posets serve as touchstones because many others reduce to them<sup>[2](https://datafield.dev/discrete-mathematics/part-02/chapter-13/)</sup>:

1. \( (\mathbb{Z}, \le) \), the integers under less-than-or-equal. Every pair is comparable, so this is a total order, also called a linear order<sup>[7](https://www.cs.odu.edu/~toida/nerzic/content/relation/order/order.html)</sup>.
2. \( (\mathcal{P}(S), \subseteq) \), the power set of a set \( S \) ordered by inclusion. Antisymmetry here is exactly the set-equality argument that mutual inclusion forces equality; most pairs are incomparable, for example \( \{1\} \) and \( \{2\} \)<sup>[2](https://datafield.dev/discrete-mathematics/part-02/chapter-13/)</sup>.
3. \( (\mathbb{N}_{+}, \mid) \), the positive integers ordered by divisibility, where \( m \mid n \) means \( n = km \) for some positive integer \( k \). This order is a sub-order of the ordinary order \( \le \)<sup>[1](https://stats.libretexts.org/Bookshelves/Probability_Theory/Probability_Mathematical_Statistics_and_Stochastic_Processes_%28Siegrist%29/01%253A_Foundations/1.04%253A_Partial_Orders)</sup>.

Further classical examples include the real-valued functions on \( [0, 1] \) ordered pointwise, finite increasing sequences of natural numbers ordered by the prefix relation, and the trivial order in which \( a \le b \) only when \( a = b \)<sup>[5](https://encyclopediaofmath.org/wiki/Partially_ordered_set)</sup>. The set of functions from any set \( S \) into a poset \( (T, \preceq_T) \) is itself a poset under the pointwise order \( f \preceq g \) when \( f(x) \preceq_T g(x) \) for all \( x \); no order is needed on the domain<sup>[1](https://stats.libretexts.org/Bookshelves/Probability_Theory/Probability_Mathematical_Statistics_and_Stochastic_Processes_%28Siegrist%29/01%253A_Foundations/1.04%253A_Partial_Orders)</sup>.

The inverse of a partial order is again a partial order, and restricting a partial order to a subset \( A \subseteq S \) gives a partial order on \( A \)<sup>[1](https://stats.libretexts.org/Bookshelves/Probability_Theory/Probability_Mathematical_Statistics_and_Stochastic_Processes_%28Siegrist%29/01%253A_Foundations/1.04%253A_Partial_Orders)</sup>.

## Total orders, extensions, and dimension

A partial order is a total or linear order when for every \( x, y \) either \( x \preceq y \) or \( y \preceq x \); there are then no unrelated elements<sup>[1](https://stats.libretexts.org/Bookshelves/Probability_Theory/Probability_Mathematical_Statistics_and_Stochastic_Processes_%28Siegrist%29/01%253A_Foundations/1.04%253A_Partial_Orders)</sup>. One partial order \( \preceq_1 \) is a sub-order of another \( \preceq_2 \) when \( x \preceq_1 y \) implies \( x \preceq_2 y \), in which case \( \preceq_2 \) is an extension of \( \preceq_1 \)<sup>[1](https://stats.libretexts.org/Bookshelves/Probability_Theory/Probability_Mathematical_Statistics_and_Stochastic_Processes_%28Siegrist%29/01%253A_Foundations/1.04%253A_Partial_Orders)</sup>.

**Dimension measures incomparability.** In their 1941 paper, [Ben Dushnik](https://www.edgepedia.org/ben-dushnik) and E. W. Miller defined a linear extension of a partial order \( P \) as a linear order on the same set containing every ordered pair of \( P \), and proved that every partial order possesses linear extensions, indeed extensions placing any two incomparable elements in either order<sup>[8](https://fa.ewi.tudelft.nl/~hart/set_theory/material/dushnik_miller-partially_ordered_sets.pdf)</sup>. The dimension of \( P \), denoted \( \dim(P) \), is the minimum size of a family of linear extensions whose intersection is \( P \), meaning \( x \le_P y \) holds exactly when it holds in every extension<sup>[3](https://arxiv.org/abs/1501.01147)</sup>. Equivalently, it is the least \( d \) for which \( P \) embeds into a product of \( d \) linear orders<sup>[9](https://arxiv.org/abs/2201.12952)</sup>. Hiraguchi proved in 1955 that the maximum dimension of a poset of order \( n \) is \( n/2 \)<sup>[10](https://arxiv.org/abs/1803.08641)</sup>.

Computationally, there are efficient algorithms to test whether a partial order has dimension at most 2<sup>[3](https://arxiv.org/abs/1501.01147)</sup>. [Mihalis Yannakakis](https://www.edgepedia.org/mihalis-yannakakis) showed in 1982 that for \( k \ge 3 \) it is NP-complete to test whether a partial order has dimension \( \le k \), and also that for \( k \ge 4 \) the problem remains NP-complete restricted to posets of height 2, where height is the maximum size of a chain<sup>[3](https://arxiv.org/abs/1501.01147)</sup>. The remaining height-2, dimension-3 case, long a well-known open problem in dimension theory, was later shown NP-complete as well<sup>[3](https://arxiv.org/abs/1501.01147)</sup>.

## Hasse diagrams and finite posets

For a finite poset, \( y \) is said to cover \( x \) when \( x \prec y \) but no element \( z \) satisfies \( x \prec z \prec y \). The covering relation completely determines the partial order, by transitivity<sup>[1](https://stats.libretexts.org/Bookshelves/Probability_Theory/Probability_Mathematical_Statistics_and_Stochastic_Processes_%28Siegrist%29/01%253A_Foundations/1.04%253A_Partial_Orders)</sup>. The covering graph, or Hasse graph, named for the German mathematician [Helmut Hasse](https://www.edgepedia.org/helmut-hasse), has the elements as vertices and a directed edge for each covering pair; it is customarily drawn with edges directed upward so arrows can be omitted<sup>[1](https://stats.libretexts.org/Bookshelves/Probability_Theory/Probability_Mathematical_Statistics_and_Stochastic_Processes_%28Siegrist%29/01%253A_Foundations/1.04%253A_Partial_Orders)</sup>.

Minimal and maximal elements generalize least and greatest numbers: a minimal element has no element strictly below it, and a poset can have several, as in \( \{\{1\}, \{2\}, \{1, 2\}\} \) under inclusion, where \( \{1\} \) and \( \{2\} \) are both minimal and incomparable<sup>[7](https://www.cs.odu.edu/~toida/nerzic/content/relation/order/order.html)</sup>.

## Applications

**Task scheduling.** A partial order models must-come-before constraints among tasks, as in compiling source files, installing package dependencies, or scheduling university course prerequisites. A topological sort is a linear sequence respecting all constraints, and every finite DAG has one<sup>[2](https://datafield.dev/discrete-mathematics/part-02/chapter-13/)</sup><sup> • </sup><sup>[11](https://ocw.mit.edu/courses/6-042j-mathematics-for-computer-science-spring-2015/mit6_042js15_textbook.pdf)</sup>.

**Distributed systems.** Because clocks cannot be synchronized perfectly across a distributed system, physical time cannot order arbitrary pairs of events. [Leslie Lamport](https://www.edgepedia.org/leslie-lamport)'s 1978 paper defined the happened-before relation, a strict partial order generated by intra-process event order and message send-before-receive, generalizing these two relationships into a partial ordering of events<sup>[4](https://www.scitepress.org/PublishedPapers/2006/15724/pdf/index.html)</sup><sup> • </sup><sup>[12](https://ftp.utcluj.ro/pub/users/civan/CPD/3.RESURSE/6.Book_2012_Distributed%20systems%20_Couloris.pdf)</sup>. Its complement is the concurrent relation, holding when neither event precedes the other<sup>[4](https://www.scitepress.org/PublishedPapers/2006/15724/pdf/index.html)</sup>. Vector clocks realize this order exactly: for events \( e \) and \( e' \), \( VC(e) < VC(e') \) if and only if \( e \) happens-before \( e' \)<sup>[13](https://www.cs.yale.edu/homes/aspnes/classes/4650/notes.pdf)</sup>.

**Lattices and category theory.** A lattice is a poset in which every pair of elements has a greatest lower bound and a least upper bound<sup>[14](https://diposit.ub.edu/bitstreams/8b1c3c3c-594b-4e6f-a18b-669cf03bc8d4/download)</sup>. Every poset can be viewed as a small category whose objects are its elements, with exactly one morphism from \( a \) to \( b \) when \( a \le b \) and none otherwise; conversely, a small category with at most one morphism in each direction between two objects is equivalent to the category of a poset<sup>[5](https://encyclopediaofmath.org/wiki/Partially_ordered_set)</sup>.

**Extremal combinatorics.** Extremal questions, asking for optimal parameter values under constraints, have in recent years been extended from graphs to posets, with active work on Turán-type and Ramsey-type problems for families of sets ordered by inclusion<sup>[15](https://www.cambridge.org/core/books/abs/surveys-in-combinatorics-2026/extremal-poset-theory/69620990E4827A4D09B930B8B6B36B4A)</sup>.

## History

The order axioms had been considered by [Gottfried Wilhelm Leibniz](https://www.edgepedia.org/gottfried-wilhelm-leibniz) around 1690, but the definition of a partially ordered set was first clearly formulated by [Felix Hausdorff](https://www.edgepedia.org/felix-hausdorff) in his 1914 *Grundzüge der Mengenlehre*. An accurate definition of the totally ordered set was first given by [Georg Cantor](https://www.edgepedia.org/georg-cantor), who in the same work defined the order type of a totally ordered set, the class of all totally ordered sets isomorphic to a given one<sup>[5](https://encyclopediaofmath.org/wiki/Partially_ordered_set)</sup>. The systematic study of finite posets as combinatorial objects began with the 1941 paper of Dushnik and Miller, which introduced order dimension<sup>[8](https://fa.ewi.tudelft.nl/~hart/set_theory/material/dushnik_miller-partially_ordered_sets.pdf)</sup><sup> • </sup><sup>[3](https://arxiv.org/abs/1501.01147)</sup>.

## References

1. [Partial Orders, Statistics LibreTexts (Kyle Siegrist), section 1.4](https://stats.libretexts.org/Bookshelves/Probability_Theory/Probability_Mathematical_Statistics_and_Stochastic_Processes_%28Siegrist%29/01%253A_Foundations/1.04%253A_Partial_Orders)
2. [Chapter 13: Partial Orders, Lattices, and Boolean Algebra, Discrete Mathematics](https://datafield.dev/discrete-mathematics/part-02/chapter-13/)
3. [The Complexity of the Partial Order Dimension Problem – Closing the Gap, arXiv:1501.01147](https://arxiv.org/abs/1501.01147)
4. [A Temporal Synchronization Mechanism for Real-Time Distributed Continuous Media, SciTePress](https://www.scitepress.org/PublishedPapers/2006/15724/pdf/index.html)
5. [Partially ordered set, Encyclopedia of Mathematics](https://encyclopediaofmath.org/wiki/Partially_ordered_set)
6. [Partial Orders and Total Orders, Applied Combinatorics](https://appliedcombinatorics.org/book/s_background_order.html)
7. [Order Relation, Old Dominion University (Toida), Discrete Mathematics notes](https://www.cs.odu.edu/~toida/nerzic/content/relation/order/order.html)
8. [Ben Dushnik and E. W. Miller (1941). Partially Ordered Sets. American Journal of Mathematics 63(3): 600–610](https://fa.ewi.tudelft.nl/~hart/set_theory/material/dushnik_miller-partially_ordered_sets.pdf)
9. [The Dimension of Divisibility Orders and Multiset Posets, arXiv:2201.12952](https://arxiv.org/abs/2201.12952)
10. [On difference graphs and the local dimension of posets, arXiv:1803.08641](https://arxiv.org/abs/1803.08641)
11. [Mathematics for Computer Science, MIT OpenCourseWare 6.042J (Lehman, Leighton, Meyer)](https://ocw.mit.edu/courses/6-042j-mathematics-for-computer-science-spring-2015/mit6_042js15_textbook.pdf)
12. [Distributed Systems: Concepts and Design (Coulouris et al.)](https://ftp.utcluj.ro/pub/users/civan/CPD/3.RESURSE/6.Book_2012_Distributed%20systems%20_Couloris.pdf)
13. [Notes on Theory of Distributed Systems, Yale University (James Aspnes)](https://www.cs.yale.edu/homes/aspnes/classes/4650/notes.pdf)
14. [A Study of Partially Ordered Sets, Universitat de Barcelona thesis](https://diposit.ub.edu/bitstreams/8b1c3c3c-594b-4e6f-a18b-669cf03bc8d4/download)
15. [Maria Axenovich, Ryan R. Martin, and Balázs Patkós. Extremal Poset Theory. Surveys in Combinatorics 2026, Cambridge University Press, pp. 31–74](https://www.cambridge.org/core/books/abs/surveys-in-combinatorics-2026/extremal-poset-theory/69620990E4827A4D09B930B8B6B36B4A)

---
*Topic: Encyclopedia › Physical world and mathematics › Mathematics and statistics › Logic and discrete mathematics › General discrete mathematics and discrete structures › Discrete mathematics*

*Initially written Sep 17, 2026 · Reviewed: Oct 15, 2026 · Edited: Oct 15, 2026 · Last review: Oct 15, 2026*

*Copyright 2026 EdgeChat AI, a subsidiary of Biostate AI.*

License: Edgepedia Community License 1.0, https://www.edgepedia.org/edgepedia/license