# Partially ordered set

A non-empty set on which some order relation is given.

Examples of partially-ordered sets. 1) The set of natural numbers with the usual order relation. 2) The set of natural numbers, where $a \leq b$ means that $a$ divides $b$. 3) The set of all subsets of some set, where $a \leq b$ means that $a \subseteq b$. 4) The set of all real-valued functions on the interval $[ 0 , 1 ]$, where $f \leq g$ means that $f ( t) \leq g ( t)$ for all $t \in [ 0 , 1 ]$. 5) The set of all finite increasing sequences of natural numbers, where

$$( a _ {1} \dots a _ {k} ) \leq ( b _ {1} \dots b _ {l} )$$

means that $k \leq l$ and $a _ {i} = b _ {i}$ for $1 \leq i \leq k$( cf. Tree). 6) An arbitrary non-empty set, where $a \leq b$ means that $a = b$( such a set is called a trivial or discrete partially ordered set).

Every partially ordered set $P$ can be considered as a small category, whose objects are the elements of $P$ and in which the set of morphisms $H ( a , b )$ consists of one element if $a \leq b$ and is empty otherwise. Conversely, every small category in which $H ( a , b ) \cup H( b, a)$ contains at most one element for each pair of objects $( a, b)$ is equivalent to the category of a partially-ordered set.

If one defines the relation $\geq$ on a partially ordered set $P$ by putting $a \geq b$ whenever $b \leq a$, 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 $P$.

A mapping $\phi$ from a partially ordered set $P$ into a partially ordered set $P ^ \prime$ is called isotone (antitone), or an (anti-) homomorphism, if $a \leq b$ in $P$ implies

$$\phi ( a) \leq \phi ( b) \ \ ( \phi ( b) \leq \phi ( a))$$

in $P ^ \prime$. A bijective (anti-) homomorphism is called an (anti-) isomorphism. The identity mapping of a partially ordered set $P$ onto itself is an anti-isomorphism between $P$ and its dual. An isomorphism is a special case of a residual mapping. The composite of two anti-homomorphisms is a homomorphism. The collection of all partially ordered sets forms a 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 $A$ is a non-empty subset of a partially ordered set $P$, then the lower cone $A ^ \nabla$( the upper cone $A ^ \Delta$) is defined to be the set of all elements $x \in P$ such that $x \leq a$( $a \leq x$) for all $a \in A$. If $a , b \in P$ and $a \leq b$, the subset

$$[ a , b ] = a ^ \Delta \cap b ^ \nabla = \ \{ {x } : {a \leq x \leq b } \}$$

is called an interval or segment. The cones $a ^ \Delta$ and $a ^ \nabla$, $a \in P$, are often called intervals also. An element $u$ of a subset $A$ is called greatest (least) if $a \leq u$( $u \leq a$) for all $a \in A$. In this case $u$ is the unique element in the intersection $A \cup A ^ \Delta$( $A \cap A ^ \nabla$). A greatest (least) element of a partially ordered set $P$( if it exists) is called a unit (a zero) of $P$, and is denoted by $1$. An element $m$ of a subset $A$ is called maximal (minimal) if, for any element $x \in A$, $m \leq x$( $x \leq m$) only if $m = x$. In other words

$$m ^ \Delta \cap A = m \ \ ( m ^ \nabla \cap A = m ) .$$

A greatest (least) element is maximal (minimal). The converse does not always hold. A least (greatest) element of the upper (lower) cone $A ^ \Delta$( $A ^ \nabla$) is called a least upper (greatest lower) bound of the subset $A$, and is denoted by $\sup A$( $\inf A$). Rewriting this definition, one can say that $u = \sup A$ if $u \geq a$ for all $a \in A$ and if $u ^ \prime \geq u$ whenever $u ^ \prime \geq a$ for all $a \in A$. There is an analogous way of rewriting the definition of $\inf A$. If $P$ is a chain, then the last condition may be expressed thus; "… and if u'<a0 for some a0 A whenever u'< u" , as is usual in mathematical analysis. Elements of $A ^ \Delta$( $A ^ \nabla$) are often called upper (lower) bounds for the subset $A$. It is clear that $1 = \sup P$ and $0 = \inf P$. It is a common convention that $\sup \emptyset = 0$ and $\inf \emptyset = 1$. The following properties hold:

a) if $A \subseteq B$, then $B ^ \Delta \subseteq A ^ \Delta$ and $B ^ \nabla \subseteq A ^ \nabla$;

b) $A \subseteq A ^ {\Delta \nabla } \cap A ^ {\nabla \Delta }$;

c) $A ^ \Delta = A ^ {\Delta \nabla \Delta }$ and $A ^ \nabla = A ^ {\nabla \Delta \nabla }$;

d) $( A \cup B ) ^ \Delta = A ^ \Delta \cap B ^ \Delta$;

e) $( A \cup B ) ^ \nabla = A ^ \nabla \cap B ^ \nabla$;

f) if $\sup A$ or $\inf A ^ \Delta$ exists, then $\sup A = \inf A ^ \Delta$;

g) if $\inf A$ or $\sup A ^ \nabla$ exists, then $\inf A = \sup A ^ \nabla$;

h) (generalized associativity) if $\{ {A _ \alpha } : {\alpha \in I } \}$ is a set of subsets of a partially ordered set $P$ and if $\sup ( \cup _ \alpha A _ \alpha )$ and $\sup A _ \alpha$( $\inf ( \cup _ \alpha A _ \alpha )$ and $\inf A _ \alpha$) exist for all $\alpha \in I$, then

$$\sup ( \cup _ \alpha A _ \alpha ) = \sup \{ \sup A _ \alpha \} ,$$

$$( \inf ( \cup _ \alpha A _ \alpha ) = \ \inf \{ \inf A _ \alpha \} ) ;$$

i) if $\phi$ is an isotone mapping from a partially ordered set $P$ into a partially ordered set $P ^ \prime$, if $A \subseteq P$ and if both $\sup A$ in $P$ and $\sup \phi ( A)$ in $P ^ \prime$( $\inf A$ in $P$ and $\inf \phi ( A)$ in $P ^ \prime$) exist, then $\sup \phi ( A) \leq \phi ( \sup A )$( $\phi ( \inf A ) \leq \inf \phi ( A)$).

Some of the definitions and results introduced above may be obtained from one another by changing the symbol $\leq$ to $\geq$. 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 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; Directed set; Lattice; Semi-lattice; Totally ordered set; Well-ordered set). A special role is played by algebraic structures that are also partially ordered sets (cf. Ordered semi-group; Partially ordered group; 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 , 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 . 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 , 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 , . Ordered sets were used by Shatunovskii , and also by E.H. Moore and H.L. Smith , in connection with the general definition of limit in mathematical analysis.