partial order

English

Hasse diagram of a set with the partial order "is divisible by"

Noun

partial order (plural partial orders)

1. (set theory, order theory) (informal) An ordering of the elements of a collection that behaves like that of the natural numbers by size, except that some elements may not be comparable (if all elements are comparable, it is called a total order); (formal) a binary relation that is reflexive, antisymmetric, and transitive.
   • 1986, Kenneth R. Goodearl, Partially Ordered Abelian Groups with Interpolation, American Mathematical Society, Softcover reprint 2010, page xxi,

     A partial order on a set X is any reflexive, antisymmetric, transitive relation on X. In most cases, partial orders are denoted ≤.

   • 1999, Paul A. S. Ward, An Online Algorithm for Dimension-Bound Analysis, Patrick Amestoy, P. Berger, M. Daydé, I. Duff, V. Frayssé, L. Giraud, D. Ruiz (editors), Euro-Par ’99 Parallel Processing: 5th International Euro-Par Conference, Proceedings, Springer, LNCS 1685, page 144,

     The vector-clock size necessary to characterize causality in a distributed computation is bounded by the dimension of the partial order induced by that computation.

   • 2008, David Eppstein, Jean-Claude Falmagne, Sergei Ovchinnikov, Media Theory: Interdisciplinary Applied Mathematics, Springer, page 7:

     Consider an arbitrary finite set S. The family ${\mathcal {P}}$ of all strict partial orders (asymmetric, transitive, cf. 1.8.3, p. 14) on S enjoys a remarkable property: any partial order P can be linked to any other partial order P’ by a sequence of steps each of which consists of changing the order either by adding one ordered pair of elements of S (imposing an ordering between two previously-incomparable elements) or by removing one ordered pair (causing two previously related elements to become incomparable), without ever leaving the family ${\mathcal {P}}$.

Synonyms

• partial ordering relation

Hypernyms

• preorder

Hyponyms

• total order
  • well-order

Related terms

• order
• partially ordered set

Translations

binary relation that is reflexive, antisymmetric, and transitive

• Czech: uspořádání (cs) n
• Finnish: osittainen järjestys, osittaisjärjestys
• German: Halbordnung f, partielle Ordnung f
• Japanese: 半順序 (はんじゅんじょ, hanjunjo)
• Korean: 부분 순서 (bubun sunseo)
• Polish: częściowy porządek m
• Russian: части́чный поря́док (častíčnyj porjádok)
• Swedish: partiell ordning (sv)

References

• B. Dushnik and E. W. Miller, Partially Ordered Sets, Amer. J. Math. 63 (1941), 600-610.

Further reading

• Partially ordered set on Wikipedia.Wikipedia
• Complete partial order on Wikipedia.Wikipedia