 x Partially ordered set Encyclopedia In mathematics
Mathematics
Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...

, especially order theory
Order theory
Order theory is a branch of mathematics which investigates our intuitive notion of order using binary relations. It provides a formal framework for describing statements such as "this is less than that" or "this precedes that". This article introduces the field and gives some basic definitions...

, a partially ordered set (or poset) formalizes and generalizes the intuitive concept of an ordering, sequencing, or arrangement of the elements of a set. A poset consists of a set together with a binary relation
Relation (mathematics)
In set theory and logic, a relation is a property that assigns truth values to k-tuples of individuals. Typically, the property describes a possible connection between the components of a k-tuple...

that indicates that, for certain pairs of elements in the set, one of the elements precedes the other. Such a relation is called a partial order to reflect the fact that not every pair of elements need be related: for some pairs, it may be that neither element precedes the other in the poset.
Thus, partial orders generalize the more familiar total order
Total order
In set theory, a total order, linear order, simple order, or ordering is a binary relation on some set X. The relation is transitive, antisymmetric, and total...

s, in which every pair is related. A finite poset can be visualized through its Hasse diagram
Hasse diagram
In order theory, a branch of mathematics, a Hasse diagram is a type of mathematical diagram used to represent a finite partially ordered set, in the form of a drawing of its transitive reduction...

, which depicts the ordering relation.

A familiar real-life example of a partially ordered set is a collection of people ordered by genealogical
Genealogy
Genealogy is the study of families and the tracing of their lineages and history. Genealogists use oral traditions, historical records, genetic analysis, and other records to obtain information about a family and to demonstrate kinship and pedigrees of its members...

descendancy. Some pairs of people bear the descendant-ancestor relationship, but other pairs bear no such relationship.

## Formal definition

A partial order is a binary relation
Binary relation
In mathematics, a binary relation on a set A is a collection of ordered pairs of elements of A. In other words, it is a subset of the Cartesian product A2 = . More generally, a binary relation between two sets A and B is a subset of...

"≤" over a set P which is reflexive
Reflexive relation
In mathematics, a reflexive relation is a binary relation on a set for which every element is related to itself, i.e., a relation ~ on S where x~x holds true for every x in S. For example, ~ could be "is equal to".-Related terms:...

, antisymmetric
Antisymmetric relation
In mathematics, a binary relation R on a set X is antisymmetric if, for all a and b in Xor, equivalently,In mathematical notation, this is:\forall a, b \in X,\ R \and R \; \Rightarrow \; a = bor, equivalently,...

, and transitive
Transitive relation
In mathematics, a binary relation R over a set X is transitive if whenever an element a is related to an element b, and b is in turn related to an element c, then a is also related to c....

, i.e., for all a, b, and c in P, we have that:
• a ≤ a (reflexivity);
• if a ≤ b and b ≤ a then a = b (antisymmetry);
• if a ≤ b and b ≤ c then a ≤ c (transitivity).

In other words, a partial order is an antisymmetric preorder
Preorder
In mathematics, especially in order theory, preorders are binary relations that are reflexive and transitive.For example, all partial orders and equivalence relations are preorders...

.

A set with a partial order is called a partially ordered set (also called a poset). The term ordered set is sometimes also used for posets, as long as it is clear from the context that no other kinds of orders are meant. In particular, totally ordered sets can also be referred to as "ordered sets", especially in areas where these structures are more common than posets.

For a, b, elements of a partially ordered set P, if a ≤ b or b ≤ a, then a and b are comparable. Otherwise they are incomparable. A partial order under which every pair of elements is comparable is called a total order or linear order; a totally ordered set is also called a chain (e.g., the natural numbers with their standard order). A poset in which no two distinct elements are comparable is called an antichain
Antichain
In mathematics, in the area of order theory, an antichain is a subset of a partially ordered set such that any two elements in the subset are incomparable. Let S be a partially ordered set...

.

## Examples

Standard examples of posets arising in mathematics include:
• The real number
Real number
In mathematics, a real number is a value that represents a quantity along a continuum, such as -5 , 4/3 , 8.6 , √2 and π...

s ordered by the standard less-than-or-equal relation ≤ (a totally ordered set as well).

• The set of natural number
Natural number
In mathematics, the natural numbers are the ordinary whole numbers used for counting and ordering . These purposes are related to the linguistic notions of cardinal and ordinal numbers, respectively...

s equipped with the relation of divisibility.

• The vertex set of a directed acyclic graph
Directed acyclic graph
In mathematics and computer science, a directed acyclic graph , is a directed graph with no directed cycles. That is, it is formed by a collection of vertices and directed edges, each edge connecting one vertex to another, such that there is no way to start at some vertex v and follow a sequence of...

ordered by reachability
Reachability
In graph theory, reachability is the notion of being able to get from one vertex in a directed graph to some other vertex. Note that reachability in undirected graphs is trivial — it is sufficient to find the connected components in the graph, which can be done in linear time.- Definition :For a...

.

• The set of subset
Subset
In mathematics, especially in set theory, a set A is a subset of a set B if A is "contained" inside B. A and B may coincide. The relationship of one set being a subset of another is called inclusion or sometimes containment...

s of a given set (its power set) ordered by inclusion
Subset
In mathematics, especially in set theory, a set A is a subset of a set B if A is "contained" inside B. A and B may coincide. The relationship of one set being a subset of another is called inclusion or sometimes containment...

(see the figure on top-right).

• The set of subspaces of a vector space
Vector space
A vector space is a mathematical structure formed by a collection of vectors: objects that may be added together and multiplied by numbers, called scalars in this context. Scalars are often taken to be real numbers, but one may also consider vector spaces with scalar multiplication by complex...

ordered by inclusion.

• For a partially ordered set P, the sequence space
Sequence space
In functional analysis and related areas of mathematics, a sequence space is a vector space whose elements are infinite sequences of real or complex numbers. Equivalently, it is a function space whose elements are functions from the natural numbers to the field K of real or complex numbers...

containing all sequence
Sequence
In mathematics, a sequence is an ordered list of objects . Like a set, it contains members , and the number of terms is called the length of the sequence. Unlike a set, order matters, and exactly the same elements can appear multiple times at different positions in the sequence...

s of elements from P, where sequence a precedes sequence b if every item in a precedes the corresponding item in b. Formally, (an)n∈ℕ ≤ (bn)n∈ℕ if and only if an ≤ bn for all n in ℕ.

• For a set X and a partially ordered set P, the function space
Function space
In mathematics, a function space is a set of functions of a given kind from a set X to a set Y. It is called a space because in many applications it is a topological space, a vector space, or both.-Examples:...

containing all functions from X to P, where fg if and only if f(x)g(x) for all x in X.

• A fence
Fence (mathematics)
In mathematics, a fence, also called a zigzag poset, is a partially ordered set in which the order relations form a path with alternating orientations:orA fence may be finite, or it may be formed by an infinite alternating sequence extending in both directions.A linear extension of a fence is...

, a partially ordered set defined by an alternating sequence of order relations a < b > c < d ...

## Extrema

There are several notions of "greatest" and "least" element in a poset P, notably:
• Greatest element
Greatest element
In mathematics, especially in order theory, the greatest element of a subset S of a partially ordered set is an element of S which is greater than or equal to any other element of S. The term least element is defined dually...

and least element: An element g in P is a greatest element if for every element a in P, a ≤ g. An element m in P is a least element if for every element a in P, a ≥ m. A poset can only have one greatest or least element.
• Maximal element
Maximal element
In mathematics, especially in order theory, a maximal element of a subset S of some partially ordered set is an element of S that is not smaller than any other element in S. The term minimal element is defined dually...

s and minimal elements: An element g in P is a maximal element if there is no element a in P such that a > g. Similarly, an element m in P is a minimal element if there is no element a in P such that a < m. If a poset has a greatest element, it must be the unique maximal element, but otherwise there can be more than one maximal element, and similarly for least elements and minimal elements.
• Upper and lower bounds: For a subset A of P, an element x in P is an upper bound of A if a ≤ x, for each element a in A. In particular, x need not be in A to be an upper bound of A. Similarly, an element x in P is a lower bound of A if a ≥ x, for each element a in A. A greatest element of P is an upper bound of P itself, and a least element is a lower bound of P.

For example, consider the positive integers, ordered by divisibility: 1 is a least element, as it divides all other elements; on the other hand this poset does not have a greatest element (although if one would include 0 in the poset, which is a multiple of any integer, that would be a greatest element). This partially ordered set does not even have any maximal elements, since any g divides for instance 2g, which is distinct from it, so g is not be maximal. If we exclude the number 1, while keeping divisibility as ordering on the elements greater than 1, then the resulting poset does not have a least element, but any prime number
Prime number
A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself. A natural number greater than 1 that is not a prime number is called a composite number. For example 5 is prime, as only 1 and 5 divide it, whereas 6 is composite, since it has the divisors 2...

is a minimal element for it. In this poset, 60 is an upper bound (though not a least upper bound) of the subset {2,3,5,10}, which subset does not have any lower bound (since 1 is not in the poset); on the other hand 2 is a lower bound of the subset of powers of 2, which subset does not have any upper bound.

## Orders on the Cartesian product of partially ordered sets

In order of increasing strength, i.e., decreasing sets of pairs, three of the possible partial orders on the Cartesian product
Cartesian product
In mathematics, a Cartesian product is a construction to build a new set out of a number of given sets. Each member of the Cartesian product corresponds to the selection of one element each in every one of those sets...

of two partially ordered sets are:
• Lexicographical order
Lexicographical order
In mathematics, the lexicographic or lexicographical order, , is a generalization of the way the alphabetical order of words is based on the alphabetical order of letters.-Definition:Given two partially ordered sets A and B, the lexicographical order on...

: (a,b) ≤ (c,d) if and only if a < c or (a = c and bd).
• (a,b) ≤ (c,d) if and only if ac and bd (the product order
Product order
In mathematics, given two ordered sets A and B, one can induce a partial ordering on the Cartesian product A × B. Giventwo pairs and in A × B, one sets ≤...

).
• (a,b) ≤ (c,d) if and only if (a < c and b < d) or (a = c and b = d) (the reflexive closure of the direct product of the corresponding strict orders).

All three can similarly be defined for the Cartesian product of more than two sets.

Applied to ordered vector space
Ordered vector space
In mathematics an ordered vector space or partially ordered vector space is a vector space equipped with a partial order which is compatible with the vector space operations.- Definition:...

s over the same field
Field (mathematics)
In abstract algebra, a field is a commutative ring whose nonzero elements form a group under multiplication. As such it is an algebraic structure with notions of addition, subtraction, multiplication, and division, satisfying certain axioms...

, the result is in each case also an ordered vector space.

## Strict and non-strict partial orders

In some contexts, the partial order defined above is called a non-strict (or reflexive, or weak) partial order. In these contexts a strict (or irreflexive) partial order "<" is a binary relation that is irreflexive and transitive
Transitive relation
In mathematics, a binary relation R over a set X is transitive if whenever an element a is related to an element b, and b is in turn related to an element c, then a is also related to c....

, and therefore asymmetric
Asymmetric relation
Asymmetric often means, simply: not symmetric. In this sense an asymmetric relation is a binary relation which is not a symmetric relation.That is,\lnot....

. In other words, asymmetric (hence irreflexive) and transitive.

Thus, for all a, b, and c in P, we have that:
• ¬(a < a) (irreflexivity);
• if a < b then ¬(b < a) (asymmetry); and
• if a < b and b < c then a < c (transitivity).

There is a 1-to-1 correspondence between all non-strict and strict partial orders.

If "≤" is a non-strict partial order, then the corresponding strict partial order "<" is the reflexive reduction given by:
a < b if and only if (ab and ab)

Conversely, if "<" is a strict partial order, then the corresponding non-strict partial order "≤" is the reflexive closure given by:
ab if and only if a < b or a = b.

This is the reason for using the notation "≤".

Strict partial orders are useful because they correspond more directly to directed acyclic graph
Directed acyclic graph
In mathematics and computer science, a directed acyclic graph , is a directed graph with no directed cycles. That is, it is formed by a collection of vertices and directed edges, each edge connecting one vertex to another, such that there is no way to start at some vertex v and follow a sequence of...

s (dags): every strict partial order is a dag, and the transitive closure
Transitive closure
In mathematics, the transitive closure of a binary relation R on a set X is the transitive relation R+ on set X such that R+ contains R and R+ is minimal . If the binary relation itself is transitive, then the transitive closure will be that same binary relation; otherwise, the transitive closure...

of a dag is both a strict partial order and also a dag itself.

## Inverse and order dual

The inverse or converse ≥ of a partial order relation ≤ satisfies xy if and only if yx. The inverse of a partial order relation is reflexive, transitive, and antisymmetric, and hence itself a partial order relation. The order dual of a partially ordered set is the same set with the partial order relation replaced by its inverse. The irreflexive relation > is to ≥ as < is to ≤.

Any one of these four relations ≤, <, ≥, and > on a given set uniquely determine the other three.

In general two elements x and y of a partial order 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 (none of the other three). A totally ordered
Total order
In set theory, a total order, linear order, simple order, or ordering is a binary relation on some set X. The relation is transitive, antisymmetric, and total...

set is one that rules out this fourth possibility: all pairs of elements are comparable and we then say that trichotomy holds. The natural number
Natural number
In mathematics, the natural numbers are the ordinary whole numbers used for counting and ordering . These purposes are related to the linguistic notions of cardinal and ordinal numbers, respectively...

s, the integer
Integer
The integers are formed by the natural numbers together with the negatives of the non-zero natural numbers .They are known as Positive and Negative Integers respectively...

s, the rationals
Rational number
In mathematics, a rational number is any number that can be expressed as the quotient or fraction a/b of two integers, with the denominator b not equal to zero. Since b may be equal to 1, every integer is a rational number...

, and the real
Real number
In mathematics, a real number is a value that represents a quantity along a continuum, such as -5 , 4/3 , 8.6 , √2 and π...

s are all totally ordered by their algebraic (signed) magnitude whereas the complex number
Complex number
A complex number is a number consisting of a real part and an imaginary part. Complex numbers extend the idea of the one-dimensional number line to the two-dimensional complex plane by using the number line for the real part and adding a vertical axis to plot the imaginary part...

s are not. This is not to say that the complex numbers cannot be totally ordered; we could for example order them lexicographically via x+iy < u+iv if and only if x < u or (x = u and y < v), but this is not ordering by magnitude in any reasonable sense as it makes 1 greater than 100i. Ordering them by absolute magnitude yields a preorder in which all pairs are comparable, but this is not a partial order since 1 and i have the same absolute magnitude but are not equal, violating antisymmetry.

## Number of partial orders Sequence [ A001035] in OEIS
On-Line Encyclopedia of Integer Sequences
The On-Line Encyclopedia of Integer Sequences , also cited simply as Sloane's, is an online database of integer sequences, created and maintained by N. J. A. Sloane, a researcher at AT&T Labs...

gives the number of partial orders on a set of n labeled elements:
The number of strict partial orders is the same as that of partial orders.

If we count only up to
Up to
In mathematics, the phrase "up to x" means "disregarding a possible difference in  x".For instance, when calculating an indefinite integral, one could say that the solution is f "up to addition by a constant," meaning it differs from f, if at all, only by some constant.It indicates that...

isomorphism, we get 1, 1, 2, 5, 16, 63, 318, … .

## Linear extension

A partial order ≤* on a set X is an extension of another partial order ≤ on X provided that for all elements x and y of X, whenever x ≤y, it is also the case that x ≤* y. A linear extension
Linear extension
In order theory, a branch of mathematics, a linear extension of a partial order is a linear order that is compatible with the partial order.-Definitions:...

is an extension that is also a linear (i.e., total) order. Every partial order can be extended to a total order (order-extension principle).

In computer science
Computer science
Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...

, algorithms for finding linear extensions of partial orders (represented as the reachability
Reachability
In graph theory, reachability is the notion of being able to get from one vertex in a directed graph to some other vertex. Note that reachability in undirected graphs is trivial — it is sufficient to find the connected components in the graph, which can be done in linear time.- Definition :For a...

orders of directed acyclic graph
Directed acyclic graph
In mathematics and computer science, a directed acyclic graph , is a directed graph with no directed cycles. That is, it is formed by a collection of vertices and directed edges, each edge connecting one vertex to another, such that there is no way to start at some vertex v and follow a sequence of...

s) are called topological sorting
Topological sorting
In computer science, a topological sort or topological ordering of a directed graph is a linear ordering of its vertices such that, for every edge uv, u comes before v in the ordering...

.

## In category theory

Every poset (and every preorder
Preorder
In mathematics, especially in order theory, preorders are binary relations that are reflexive and transitive.For example, all partial orders and equivalence relations are preorders...

) may be considered as a category
Category (mathematics)
In mathematics, a category is an algebraic structure that comprises "objects" that are linked by "arrows". A category has two basic properties: the ability to compose the arrows associatively and the existence of an identity arrow for each object. A simple example is the category of sets, whose...

in which every hom-set has at most one element. More explicitly, let hom(x, y) = {(x, y)} if xy (and otherwise the empty set) and (y, z)o(x, y) = (x, z). Posets are equivalent
Equivalence of categories
In category theory, an abstract branch of mathematics, an equivalence of categories is a relation between two categories that establishes that these categories are "essentially the same". There are numerous examples of categorical equivalences from many areas of mathematics...

to one another if and only if they are isomorphic. In a poset, the smallest element, if any, is an initial object
Initial object
In category theory, an abstract branch of mathematics, an initial object of a category C is an object I in C such that for every object X in C, there exists precisely one morphism I → X...

, and the largest element, if any, a terminal object. Also, every preordered set is equivalent to a poset. Finally, every subcategory of a poset is isomorphism-closed.

A functor from a poset category (a diagram
Diagram (category theory)
In category theory, a branch of mathematics, a diagram is the categorical analogue of an indexed family in set theory. The primary difference is that in the categorical setting one has morphisms. An indexed family of sets is a collection of sets, indexed by a fixed set; equivalently, a function...

indexed by a poset category) is a commutative diagram
Commutative diagram
In mathematics, and especially in category theory, a commutative diagram is a diagram of objects and morphisms such that all directed paths in the diagram with the same start and endpoints lead to the same result by composition...

.

## Partial orders in topological spaces

If P is a partially ordered set that has also been given the structure of a topological space
Topological space
Topological spaces are mathematical structures that allow the formal definition of concepts such as convergence, connectedness, and continuity. They appear in virtually every branch of modern mathematics and are a central unifying notion...

, then it is customary to assume that is a closed subset of the topological product space . Under this assumption partial order relations are well behaved at limits
Limit of a sequence
The limit of a sequence is, intuitively, the unique number or point L such that the terms of the sequence become arbitrarily close to L for "large" values of n...

in the sense that if , and ai ≤ bi for all i, then a ≤ b.

## Interval

For ab, the closed interval
Interval (mathematics)
In mathematics, a interval is a set of real numbers with the property that any number that lies between two numbers in the set is also included in the set. For example, the set of all numbers satisfying is an interval which contains and , as well as all numbers between them...

[a,b] is the set of elements x satisfying axb (i.e. ax and xb). It contains at least the elements a and b.

Using the corresponding strict relation "<", the open interval (a,b) is the set of elements x satisfying a < x < b (i.e. a < x and x < b). An open interval may be empty even if a < b. For example, the open interval (1,2) on the integers is empty since there are no integers i such that 1 < i < 2.

Sometimes the definitions are extended to allow a > b, in which case the interval is empty.

The half-open intervals [a,b) and (a,b] are defined similarly.

A poset is locally finite
Locally finite poset
In mathematics, a locally finite poset is a partially ordered set P such that for all x, y ∈ P, the interval [x, y] consists of finitely many elements....

if every interval is finite. For example, the integers are locally finite under their natural ordering.

This concept of an interval in a partial order should not be confused with the particular class of partial orders known as the interval order
Interval order
In mathematics, especially order theory,the interval order for a collection of intervals on the real lineis the partial order corresponding to their left-to-right precedence relation—one interval, I1, being considered less than another, I2, if I1 is completely to the left of I2.More formally, a...

s.

• antimatroid
Antimatroid
In mathematics, an antimatroid is a formal system that describes processes in which a set is built up by including elements one at a time, and in which an element, once available for inclusion, remains available until it is included...

, a formalization of orderings on a set that allows more general families of orderings than posets
• causal set
• comparability graph
Comparability graph
In graph theory, a comparability graph is an undirected graph that connects pairs of elements that are comparable to each other in a partial order...

• directed set
Directed set
In mathematics, a directed set is a nonempty set A together with a reflexive and transitive binary relation ≤ , with the additional property that every pair of elements has an upper bound: In other words, for any a and b in A there must exist a c in A with a ≤ c and b ≤...

In mathematics, in the branch of combinatorics, a graded poset, sometimes called a ranked poset , is a partially ordered set P equipped with a rank function ρ from P to N compatible with the ordering such that whenever y covers x, then...

• semilattice
Semilattice
In mathematics, a join-semilattice is a partially ordered set which has a join for any nonempty finite subset. Dually, a meet-semilattice is a partially ordered set which has a meet for any nonempty finite subset...

• lattice
Lattice (order)
In mathematics, a lattice is a partially ordered set in which any two elements have a unique supremum and an infimum . Lattices can also be characterized as algebraic structures satisfying certain axiomatic identities...

• ordered group
Ordered group
In abstract algebra, a partially-ordered group is a group equipped with a partial order "≤" that is translation-invariant; in other words, "≤" has the property that, for all a, b, and g in G, if a ≤ b then a+g ≤ b+g and g+a ≤ g+b.An element x of G is called positive element if 0 ≤ x...

• poset topology
Poset topology
In mathematics, the poset topology associated with a partially ordered set S is the Alexandrov topology on the poset of finite chains of S, ordered by inclusion.Let V be a set of vertices...

, a kind of topological space that can be defined from any poset
• semiorder
Semiorder
In order theory, a branch of mathematics, a semiorder is a type of ordering that may be determined for a set of items with numerical scores by declaring two items to be incomparable when their scores are within some threshold of each other and otherwise using the numerical comparison of their scores...

• series-parallel partial order
Series-parallel partial order
In order-theoretic mathematics, a series-parallel partial order is a partially ordered set built up from smaller series-parallel partial orders by two simple composition operations....

• strict weak ordering
Strict weak ordering
In mathematics, especially order theory, a strict weak ordering is a binary relation In mathematics, especially order theory, a strict weak ordering is a binary relation ...

- strict partial order "<" in which the relation "neither a < b nor b < a" is transitive.
• complete partial order
Complete partial order
In mathematics, directed complete partial orders and ω-complete partial orders are special classes of partially ordered sets, characterized by particular completeness properties... 