Partially ordered set

A term's definition may require additional properties that are not listed in this table.

Formally, a partial order is a homogeneous binary relation that is reflexive, antisymmetric, and transitive.

When the meaning is clear from context and there is no ambiguity about the partial order, the set

A reflexive, weak,[1] or non-strict partial order,[2] commonly referred to simply as a partial order, is a homogeneous relation ≤ on a set

it must satisfy: A non-strict partial order is also known as an antisymmetric preorder.

An irreflexive, strong,[1] or strict partial order is a homogeneous relation < on a set

may be converted to a strict partial order by removing all relationships of the form

may be converted to a non-strict partial order by adjoining all relationships of that form; that is,

, we may uniquely extend our notation to define four partial order relations

[a] Another way of defining a partial order, found in computer science, is via a notion of comparison.

as defined previously, it can be observed that two elements x and y may stand in any of four mutually exclusive relationships to each other: either x < y, or x = y, or x > y, or x and y are incomparable.

This includes both reflexive and irreflexive partial orders as subtypes.

[11] Specifically, taking a strict partial order relation

, a directed acyclic graph (DAG) may be constructed by taking each element of

Similarly this process can be reversed to construct strict partial orders from certain DAGs.

Standard examples of posets arising in mathematics include: One familiar example of a partially ordered set is a collection of people ordered by genealogical descendancy.

[14] Series-parallel partial orders are formed from the ordinal sum operation (in this context called series composition) and another operation called parallel composition.

If the number 0 is included, this will be the greatest element, since this is a multiple of every integer (see Fig. 6).

Isomorphic orders have structurally similar Hasse diagrams (see Fig. 7a).

Taking instead each number to the set of its prime power divisors defines a map

and its isomorphic image under g. The construction of such an order-isomorphism into a power set can be generalized to a wide class of partial orders, called distributive lattices; see Birkhoff's representation theorem.

[16] In computer science, algorithms for finding linear extensions of partial orders (represented as the reachability orders of directed acyclic graphs) are called topological sorting.

Every poset (and every preordered set) may be considered as a category where, for objects

is a partially ordered set that has also been given the structure of a topological space, then it is customary to assume that

Under this assumption partial order relations are well behaved at limits in the sense that if

A convex sublattice of a lattice L is a sublattice of L that is also a convex set of L. Every nonempty convex sublattice can be uniquely represented as the intersection of a filter and an ideal of L. An interval in a poset P is a subset that can be defined with interval notation: Whenever a ≤ b does not hold, all these intervals are empty.

Every interval is a convex set, but the converse does not hold; for example, in the poset of divisors of 120, ordered by divisibility (see Fig.

For example, the integers are locally finite under their natural ordering.

Using the interval notation, the property "a is covered by b" can be rephrased equivalently as

Media related to Hasse diagrams at Wikimedia Commons; each of which shows an example for a partial order