View source for Partially ordered set

A non-empty set on which some order relation is given.  
In this context an order relation is a [[Binary relation|binary relation]] $\le$ on the set with the properties [2]:
# If $a \le b$ and $b \le c$, then $a \le c$ ([[Transitivity|transitivity]])
# If $a \le b$ and $b \le a$, then $a = b$
# If $a \le b$, then $a \le a$ and $b \le b$

Examples of partially-ordered sets. 1) The set of natural numbers with the usual order relation. 2) The set of natural numbers, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p0717201.png" /> means that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p0717202.png" /> divides <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p0717203.png" />. 3) The set of all subsets of some set, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p0717204.png" /> means that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p0717205.png" />. 4) The set of all real-valued functions on the interval <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p0717206.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p0717207.png" /> means that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p0717208.png" /> for all <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p0717209.png" />. 5) The set of all finite increasing sequences of natural numbers, where

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p07172010.png" /></td> </tr></table>

means that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p07172011.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p07172012.png" /> for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p07172013.png" /> (cf. [[Tree|Tree]]). 6) An arbitrary non-empty set, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p07172014.png" /> means that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p07172015.png" /> (such a set is called a trivial or discrete partially ordered set).

Every partially ordered set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p07172016.png" /> can be considered as a [[Small category|small category]], whose objects are the elements of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p07172017.png" /> and in which the set of morphisms <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p07172018.png" /> consists of one element if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p07172019.png" /> and is empty otherwise. Conversely, every small category in which <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p07172020.png" /> contains at most one element for each pair of objects <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p07172021.png" /> is equivalent to the category of a partially-ordered set.

If one defines the relation <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p07172022.png" /> on a partially ordered set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p07172023.png" /> by putting <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p07172024.png" /> whenever <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p07172025.png" />, then this relation also turns out to be an order relation. The resulting set is said to be the opposite or dual partially ordered set to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p07172026.png" />.

A mapping <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p07172027.png" /> from a partially ordered set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p07172028.png" /> into a partially ordered set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p07172029.png" /> is called isotone (antitone), or an (anti-) homomorphism, if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p07172030.png" /> in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p07172031.png" /> implies

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p07172032.png" /></td> </tr></table>

in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p07172033.png" />. A bijective (anti-) homomorphism is called an (anti-) isomorphism. The identity mapping of a partially ordered set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p07172034.png" /> onto itself is an anti-isomorphism between <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p07172035.png" /> and its dual. An isomorphism is a special case of a [[Residual mapping|residual mapping]]. The composite of two anti-homomorphisms is a homomorphism. The collection of all partially ordered sets forms a [[Category|category]] if the isotone mappings are taken as morphisms. Every non-empty subset of a partially ordered set is a partially ordered set with respect to the induced order relation.

If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p07172036.png" /> is a non-empty subset of a partially ordered set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p07172037.png" />, then the lower cone <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p07172038.png" /> (the upper cone <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p07172039.png" />) is defined to be the set of all elements <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p07172040.png" /> such that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p07172041.png" /> (<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p07172042.png" />) for all <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p07172043.png" />. If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p07172044.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p07172045.png" />, the subset

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p07172046.png" /></td> </tr></table>

is called an interval or segment. The cones <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p07172047.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p07172048.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p07172049.png" />, are often called intervals also. An element <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p07172050.png" /> of a subset <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p07172051.png" /> is called greatest (least) if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p07172052.png" /> (<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p07172053.png" />) for all <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p07172054.png" />. In this case <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p07172055.png" /> is the unique element in the intersection <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p07172056.png" /> (<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p07172057.png" />). A greatest (least) element of a partially ordered set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p07172058.png" /> (if it exists) is called a unit (a zero) of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p07172059.png" />, and is denoted by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p07172060.png" /> . An element <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p07172061.png" /> of a subset <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p07172062.png" /> is called maximal (minimal) if, for any element <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p07172063.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p07172064.png" /> (<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p07172065.png" />) only if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p07172066.png" />. In other words

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p07172067.png" /></td> </tr></table>

A greatest (least) element is maximal (minimal). The converse does not always hold. A least (greatest) element of the upper (lower) cone <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p07172068.png" /> (<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p07172069.png" />) is called a least upper (greatest lower) bound of the subset <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p07172070.png" />, and is denoted by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p07172071.png" /> (<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p07172072.png" />). Rewriting this definition, one can say that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p07172073.png" /> if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p07172074.png" /> for all <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p07172075.png" /> and if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p07172076.png" /> whenever <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p07172077.png" /> for all <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p07172078.png" />. There is an analogous way of rewriting the definition of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p07172079.png" />. If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p07172080.png" /> is a chain, then the last condition may be expressed thus;  "… and if u'&lt;a0 for some a0 A whenever u'&lt; u" , as is usual in mathematical analysis. Elements of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p07172081.png" /> (<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p07172082.png" />) are often called upper (lower) bounds for the subset <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p07172083.png" />. It is clear that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p07172084.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p07172085.png" />. It is a common convention that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p07172086.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p07172087.png" />. The following properties hold:

a) if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p07172088.png" />, then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p07172089.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p07172090.png" />;

b) <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p07172091.png" />;

c) <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p07172092.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p07172093.png" />;

d) <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p07172094.png" />;

e) <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p07172095.png" />;

f) if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p07172096.png" /> or <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p07172097.png" /> exists, then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p07172098.png" />;

g) if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p07172099.png" /> or <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p071720100.png" /> exists, then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p071720101.png" />;

h) (generalized associativity) if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p071720102.png" /> is a set of subsets of a partially ordered set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p071720103.png" /> and if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p071720104.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p071720105.png" /> (<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p071720106.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p071720107.png" />) exist for all <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p071720108.png" />, then

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p071720109.png" /></td> </tr></table>

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p071720110.png" /></td> </tr></table>

i) if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p071720111.png" /> is an isotone mapping from a partially ordered set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p071720112.png" /> into a partially ordered set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p071720113.png" />, if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p071720114.png" /> and if both <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p071720115.png" /> in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p071720116.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p071720117.png" /> in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p071720118.png" /> (<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p071720119.png" /> in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p071720120.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p071720121.png" /> in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p071720122.png" />) exist, then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p071720123.png" /> (<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p071720124.png" />).

Some of the definitions and results introduced above may be obtained from one another by changing the symbol <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p071720125.png" /> to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p071720126.png" />. This applies, for example, to the definitions of upper and lower cones, and those of greatest and least elements. Such concepts are said to be dual. In particular, the statements d) and e) are dual, as are f) and g). This is all expressed in the general duality principle (cf. [[Duality principle|Duality principle]] in partially ordered sets).

Special forms of partially ordered sets are totally ordered sets (or chains), well-ordered sets, directed sets, lattices, semi-lattices, and Boolean algebras (cf. [[Boolean algebra|Boolean algebra]]; [[Directed set|Directed set]]; [[Lattice|Lattice]]; [[Semi-lattice|Semi-lattice]]; [[Totally ordered set|Totally ordered set]]; [[Well-ordered set|Well-ordered set]]). A special role is played by algebraic structures that are also partially ordered sets (cf. [[Ordered semi-group|Ordered semi-group]]; [[Partially ordered group|Partially ordered group]]; [[Ordered ring|Ordered ring]]). The concept of a partially ordered set is one of the most fundamentals notions in general mathematics, and is used extensively, both in mathematics itself and in its applications.

The definition of a partially ordered set was first clearly formulated by F. Hausdorff [[#References|[11]]], although the axioms appearing in the definition of an order relation had been considered by G. Leibniz around 1690. An accurate definition of a totally ordered set was first given by G. Cantor [[#References|[10]]]. In the same work he defined the order type of a totally ordered set, that is, in modern terminology, the class of all totally ordered sets isomorphic to a given one. Even earlier, Cantor had considered well-ordered sets [[#References|[9]]], although the definition he gave does not agree with the modern one. An original approach to the axiomatic definition of totally ordered sets was presented by S.O. Shatunovskii [[#References|[6]]], [[#References|[7]]]. Ordered sets were used by Shatunovskii [[#References|[8]]], and also by E.H. Moore and H.L. Smith [[#References|[12]]], in connection with the general definition of limit in mathematical analysis.

See also the references [[#References|[6]]]–[[#References|[9]]] to [[Lattice|Lattice]].

====References====
<table><TR><TD valign="top">[1]</TD> <TD valign="top">  G. Birkhoff,   "Lattice theory" , ''Colloq. Publ.'' , '''25''' , Amer. Math. Soc.  (1973)</TD></TR><TR><TD valign="top">[2]</TD> <TD valign="top">  N. Bourbaki,   "Elements of mathematics. Theory of sets" , Addison-Wesley  (1968)  (Translated from French)</TD></TR><TR><TD valign="top">[3]</TD> <TD valign="top">  A.G. Kurosh,   "Lectures on general algebra" , Chelsea  (1963)  (Translated from Russian)</TD></TR><TR><TD valign="top">[4]</TD> <TD valign="top">  V.V. Rozen,   "Partial operations on ordered sets" , Saratov  (1973)  (In Russian)</TD></TR><TR><TD valign="top">[5]</TD> <TD valign="top">  L.A. Skornyakov,   "Elements of lattice theory" , A. Hilger  (1977)  (Translated from Russian)</TD></TR><TR><TD valign="top">[6]</TD> <TD valign="top">  S.O. Shatunovskii,   ''Zap. Novoross. Obshch. Estestvoispytatelei'' , '''26'''  (1904)  pp. 21–25</TD></TR><TR><TD valign="top">[7]</TD> <TD valign="top">  S.O. Shatunovskii,  , ''Proc. 1-st All-Russian Congress of Mathematics Teachers'' , '''1'''  (1913)  pp. 276–281  (In Russian)</TD></TR><TR><TD valign="top">[8]</TD> <TD valign="top">  S.O. Shatunovskii,   "Introduction to analysis" , Odessa  (1923)  (In Russian)</TD></TR><TR><TD valign="top">[9]</TD> <TD valign="top">  G. Cantor,   "Ueber unendliche Punktmannigfaltigkeiten, V"  ''Math. Ann.'' , '''21'''  (1883)  pp. 545–591</TD></TR><TR><TD valign="top">[10]</TD> <TD valign="top">  G. Cantor,   "Beiträge zur Begründung der transfiniten Mengenlehre, I"  ''Math. Ann.'' , '''46'''  (1895)  pp. 481–512</TD></TR><TR><TD valign="top">[11]</TD> <TD valign="top">  F. Hausdorff,   "Grundzüge der Mengenlehre" , Leipzig  (1914)  (Reprinted (incomplete) English translation: Set theory, Chelsea (1978))</TD></TR><TR><TD valign="top">[12]</TD> <TD valign="top">  E.H. Moore,   H.L. Smith,   "A general theory of limits"  ''Amer. J. Math.'' , '''44'''  (1922)  pp. 102–121</TD></TR></table>



====Comments====
A partially ordered set, or poset, is said to satisfy the maximum condition if every chain of increasing elements stabilizes, i.e. if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p071720127.png" />, then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p071720128.png" /> for all large enough <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p071720129.png" />. Such a set is also called a Noetherian poset. Dually one has the minimum condition and an Artinian poset.

The words join and meet (or supremum and infimum) are often used in place of  "least upper bound"  and  "greatest lower bound" , respectively.

A useful pictorial representation of a finite partially ordered set is provided by its Hasse diagram, which is a [[Graph|graph]] having one vertex for each element of the underlying set, and an edge joining the vertices corresponding to elements <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p071720130.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p071720131.png" /> (with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p071720132.png" /> represented higher up the page than a) if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p071720133.png" /> but there is no element <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p071720134.png" /> with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p071720135.png" />. (Here  "a&lt; b"  means, as usual,  "a≤ b but a≠ b" ). For example, the diagram below represents a certain five-element partially ordered set having a least element but no greatest element.

<img style="border:1px solid;" src="https://www.encyclopediaofmath.org/legacyimages/common_img/p071720a.gif" />

Figure: p071720a

From such a diagram the entire order relation may be read off using transitivity: <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p071720136.png" /> if and only if there is a raising path from the vertex corresponding to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p071720137.png" /> to that corresponding to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p071720138.png" />.

The applied theory of partial order is of very much more mathematical interest than the pure. Partial orderings arise naturally in all branches of mathematics. Broadly, there are two principal types of partially ordered sets of mathematical objects: partial solutions of problems, ordered by consistent extension — here one wants a maximal, indeed a complete, solution; and diagrams of related objects, for which the aim is not to cross it but to analyze it.

==Choice and dependent choice.==
Probably a majority of the applications of the [[Axiom of choice|axiom of choice]] involve one of the order-theoretic versions of the axiom. These are mainly: <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p071720139.png" />) the maximality principle (also called the [[Zorn lemma|Zorn lemma]]): If a partially ordered set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p071720140.png" /> includes an upper bound of each of its totally ordered subsets, then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p071720141.png" /> has a maximal element. <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p071720142.png" />) A variant form: Each partially ordered set contains a maximal totally ordered subset. <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p071720143.png" />) The Teichmüller–Tukey principle: If a family of conditions on partial functions from <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p071720144.png" /> to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p071720145.png" /> concerns only their values on finite subsets of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p071720146.png" />, then there is a maximal partial function satisfying these conditions. Each of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p071720147.png" />)–<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p071720148.png" />) is equivalent to the axiom of choice.

The principle of dependent choice (Brouwer's infinity lemma, König's selection theorem) is this. Suppose given an infinite sequence of non-empty finite sets <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p071720149.png" />, and a relation <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p071720150.png" /> true for certain pairs <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p071720151.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p071720152.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p071720153.png" />. Suppose that for each <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p071720154.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p071720155.png" /> is true for at least one <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p071720156.png" />. Then there exists a sequence <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p071720157.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p071720158.png" />, such that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p071720159.png" /> is true for all <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p071720160.png" />. A classic application of dependent choice is to colouring in four colours an infinite planar map <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p071720161.png" />. Enumerate the regions of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p071720162.png" /> in any order; let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p071720163.png" /> be the submap composed of the first <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p071720164.png" /> regions; let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p071720165.png" /> be the set of admissible colourings of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p071720166.png" />. The relation <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p071720167.png" /> is extension; each colouring of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p071720168.png" /> extends a (unique) colouring of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p071720169.png" />. By the four-colour theorem (cf. [[Graph colouring|Graph colouring]]; [[Four-colour problem|Four-colour problem]]), each <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p071720170.png" /> is non-empty. Accordingly there is a sequence <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p071720171.png" /> of colourings of the submaps <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p071720172.png" /> which is consistent, since each <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p071720173.png" /> is an extension of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p071720174.png" />. This determines a colouring of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p071720175.png" />.

==Combinatorics.==
In the combinatorics of ordered objects or diagrams of objects, usually the role of the partial order is inseparable, or separable only unnaturally, from the rest of the structure. There is a neat illustration in the series of nine papers  "On the foundations of combinatorial theory. I–IX" , published by G.C. Rota and collaborators in 1964–1974. Paper I [[#References|[a4]]] is subtitled  "Theory of Möbius functions" . The Möbius function of a (finite, or locally finite in a suitable sense) partially ordered set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p071720176.png" /> is an integer-valued function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p071720177.png" /> of two variables <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p071720178.png" />, which is 0 unless <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p071720179.png" />. The characteristic property is that, like the number-theoretic [[Möbius function|Möbius function]], it inverts the process of summing a function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p071720180.png" /> with values in an additive group, to the sum <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p071720181.png" /> defined by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p071720182.png" />; the formula is <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p071720183.png" />. These Möbius functions recur often in the rest of the series and in many other places.

One of the fundamental theorems of combinatorics is, exceptionally, in pure order theory. That is the theorem of R. Dilworth: A partially ordered set is the union of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p071720184.png" /> totally ordered subsets if and only if it contains no <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p071720185.png" /> pairwise incomparable elements. In [[Combinatorial analysis|combinatorial analysis]] this theorem is mentioned, but it is bracketed with P. Hall's theorem on systems of distinct representatives. Note the radical difference: Dilworth's theorem is true for arbitrary partially ordered sets, the number <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p071720186.png" /> being finite [[#References|[a2]]]. Hall's theorem applies only to systems of distinct representatives of families of finite sets. For the relationships of Dilworth's theorem, see [[#References|[a1]]].

Sometimes the nature of a naturally occurring partial order is the central problem. For instance, much study has been devoted to extensions of Kuratowski's theorem that the set of topological types of non-planar finite graphs, ordered by imbeddability, has just two minimal elements. (See [[Graph, planar|Graph, planar]]; [[Graph theory|Graph theory]].) Here, as in many cases, the naturally given order relation is only a quasi-ordering (cf. [[Pre-order|Pre-order]]), i.e. a reflexive, transitive relation. Every quasi-ordering of a set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p071720187.png" /> determines a partial ordering on the equivalence classes of the equivalence relation  "x≤ y and y≤ x" . Accordingly one is interested in well-quasi-ordered sets: sets <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p071720188.png" /> with a quasi-ordering under which <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p071720189.png" /> contains no infinite pairwise incomparable set and no infinite strictly-decreasing sequence. Then in the associated partially ordered set of equivalence classes, the set of minimal elements of each non-empty subset is non-empty and finite. N. Robertson and P. Seymour have announced the theorem — extending a number of previous results — that finite graphs are well-quasi-ordered by the relation of containment as a minor. (Here a [[Minor of a graph|minor of a graph]] <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p071720190.png" /> is a graph that can be obtained from a subgraph of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p071720191.png" /> by contracting edges.) The proof is emerging in a long series of papers; the subtitles of the first nine are given in the announcement [[#References|[a3]]], and six of them have so far (1989) been published.

Well-quasi-ordering is the beginning of the combinatorics of infinite partially ordered sets, a division of [[Set theory|set theory]] which has some impressive results but relatively little connection with most of mathematics. However, another aspect of infinite partially ordered sets is fundamental for topology and functional analysis: this is convergence of nets. (See [[Net (directed set)|Net (directed set)]].) The role of subsequences in ordinary convergence of sequences is taken by subnets, which are carried by convergent mappings between directed sets; that is, mappings <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p071720192.png" /> such that the image of every cofinal subset of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p071720193.png" /> is cofinal in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p071720194.png" />. The use of cofinal subsets <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p071720195.png" /> is not sufficient (as it is for sequences). However, one has the theorem of J.W. Tukey: If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p071720196.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p071720197.png" /> are directed sets for which there are convergent mappings <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p071720198.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p071720199.png" />, then there exists a directed set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p071720200.png" /> in which both <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p071720201.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p071720202.png" /> can be imbedded as cofinal subsets (and conversely). In this case <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p071720203.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p071720204.png" /> are said to be cofinally similar, or of the same cofinal type.

The classification of cofinal types is in a primitive state. All countable directed sets without a greatest element are of one cofinal type. The main further results known are: A) it is consistent with the axioms of set theory (ZFC) that there are only three more cofinal types represented by directed sets of power <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p071720205.png" /> (namely <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p071720206.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p071720207.png" />, and the set of finite subsets of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p071720208.png" />); but B) there are <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p071720209.png" /> different cofinal types of directed sets of the power of the continuum <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p071720210.png" />, see [[#References|[a5]]].

====References====
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  M. Aigner,   "Combinatorial theory" , Springer  (1979)  (Translated from German)</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  R.P. Dilworth,   "A decomposition theorem for partially ordered sets"  ''Ann. Math. (2)'' , '''51'''  (1950)  pp. 161–166</TD></TR><TR><TD valign="top">[a3]</TD> <TD valign="top">  N. Robertson,   P.D. Seymour,   "Graph minors - a survey"  I. Anderson (ed.) , ''Surveys in Combinatorics 1985'' , Cambridge Univ. Press  (1985)  pp. 153–171</TD></TR><TR><TD valign="top">[a4]</TD> <TD valign="top">  G.C. Rota,   "On the foundations of combinatorial theory. I: Theory of Möbius functions"  ''Z. Wahrsch.'' , '''2'''  (1964)  pp. 340–368</TD></TR><TR><TD valign="top">[a5]</TD> <TD valign="top">  S. Todorčević,   "Directed nets and cofinal types"  ''Trans. Amer. Math. Soc.'' , '''290'''  (1985)  pp. 711–723</TD></TR><TR><TD valign="top">[a6]</TD> <TD valign="top">  G. Grätzer,   "General lattice theory" , Birkhäuser  (1978)  (Original: Lattice theory. First concepts and distributive lattices. Freeman, 1978)</TD></TR></table>