Partially ordered set

In mathematics, especially order theory, a partial order on a set is an arrangement such that, for certain pairs of elements, one precedes the other. The word partial is used to indicate that not every pair of elements needs to be comparable; that is, there may be pairs for which neither element precedes the other. Partial orders thus generalize total orders, in which every pair is comparable.

Formally, a partial order is a homogeneous binary relation that is reflexive, antisymmetric, and transitive. A partially ordered set (poset for short) is an ordered pair $P=(X,\leq )$ consisting of a set $X$ (called the ground set of $P$ ) and a partial order $\leq$ on $X$ . When the meaning is clear from context and there is no ambiguity about the partial order, the set $X$ itself is sometimes called a poset.

Notation[edit]

Given a set $P$ and a partial order relation, typically the non-strict partial order $\leq$ , we may uniquely extend our notation to define four partial order relations $\leq ,$ $<,$ $\geq ,$ and $>$ , where $\leq$ is a non-strict partial order relation on $P$ , $<$ is the associated strict partial order relation on $P$ (the irreflexive kernel of $\leq$ ), $\geq$ is the dual of $\leq$ , and $>$ is the dual of $<$ . Strictly speaking, the term partially ordered set refers to a set with all of these relations defined appropriately. But practically, one need only consider a single relation, $(P,\leq )$ or $(P,<)$ , or, in rare instances, the non-strict and strict relations together, $(P,\leq ,<)$ .^[5]

The term ordered set is sometimes used as a shorthand for partially ordered set, as long as it is clear from the context that no other kind of order is 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. Some authors use different symbols than $\leq$ such as $\sqsubseteq$ ^[6] or $\preceq$ ^[7] to distinguish partial orders from total orders.

When referring to partial orders, $\leq$ should not be taken as the complement of $>$ . The relation $>$ is the converse of the irreflexive kernel of $\leq$ , which is always a subset of the complement of $\leq$ , but $>$ is equal to the complement of $\leq$ if, and only if, $\leq$ is a total order.^[a]

Alternative definitions[edit]

Another way of defining a partial order, found in computer science, is via a notion of comparison. Specifically, given $\leq ,<,\geq ,{\text{ and }}>$ 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 can be represented by a function ${\text{compare}}:P\times P\to \{<,>,=,\vert \}$ that returns one of four codes when given two elements.^[8]^[9] This definition is equivalent to a partial order on a setoid, where equality is taken to be a defined equivalence relation rather than set equality.^[10]

Wallis defines a more general notion of a partial order relation as any homogeneous relation that is transitive and antisymmetric. This includes both reflexive and irreflexive partial orders as subtypes.^[1]

A finite poset can be visualized through its Hasse diagram.^[11] Specifically, taking a strict partial order relation $(P,<)$ , a directed acyclic graph (DAG) may be constructed by taking each element of $P$ to be a node and each element of $<$ to be an edge. The transitive reduction of this DAG^[b] is then the Hasse diagram. Similarly this process can be reversed to construct strict partial orders from certain DAGs. In contrast, the graph associated to a non-strict partial order has self-loops at every node and therefore is not a DAG; when a non-strict order is said to be depicted by a Hasse diagram, actually the corresponding strict order is shown.

The , or in general any totally ordered set, ordered by the standard less-than-or-equal relation ≤, is a partial order.

real numbers

On the real numbers $\mathbb {R}$ , the usual relation < is a strict partial order. The same is also true of the usual greater than relation > on $\mathbb {R}$ .

less than

By definition, every is a strict partial order.

strict weak order

The set of of a given set (its power set) ordered by inclusion (see Fig. 1). Similarly, the set of sequences ordered by subsequence, and the set of strings ordered by substring.

subsets

The set of equipped with the relation of divisibility. (see Fig. 3 and Fig. 6)

natural numbers

The vertex set of a ordered by reachability.

directed acyclic graph

The set of of a vector space ordered by inclusion.

subspaces

For a partially ordered set P, the containing all sequences of elements from P, where sequence a precedes sequence b if every item in a precedes the corresponding item in b. Formally, $\left(a_{n}\right)_{n\in \mathbb {N} }\leq \left(b_{n}\right)_{n\in \mathbb {N} }$ if and only if $a_{n}\leq b_{n}$ for all $n\in \mathbb {N}$ ; that is, a componentwise order.

sequence space

For a set X and a partially ordered set P, the containing all functions from X to P, where f ≤ g if and only if f(x) ≤ g(x) for all $x\in X.$

function space

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

fence

The set of events in and, in most cases,^[c] general relativity, where for two events X and Y, X ≤ Y if and only if Y is in the future light cone of X. An event Y can be causally affected by X only if X ≤ Y.

special relativity

a is related to b when a ≤ b. This does not imply that b is also related to a, because the relation need not be . For example, $\{x\}$ is related to $\{x,y\},$ but not the reverse.

symmetric

a and b are if a ≤ b or b ≤ a. Otherwise they are incomparable. For example, $\{x\}$ and $\{x,y,z\}$ are comparable, while $\{x\}$ and $\{y\}$ are not.

comparable

A or linear order is a partial order under which every pair of elements is comparable, i.e. trichotomy holds. For example, the natural numbers with their standard order.

total order

A is a subset of a poset that is a totally ordered set. For example, $\{\{\,\},\{x\},\{x,y,z\}\}$ is a chain.

chain

An is a subset of a poset in which no two distinct elements are comparable. For example, the set of singletons $\{\{x\},\{y\},\{z\}\}.$

antichain

An element a is said to be strictly less than an element b, if a ≤ b and $a\neq b.$ For example, $\{x\}$ is strictly less than $\{x,y\}.$

An element a is said to be by another element b, written a ⋖ b (or a <: b), if a is strictly less than b and no third element c fits between them; formally: if both a ≤ b and $a\neq b$ are true, and a ≤ c ≤ b is false for each c with $a\neq c\neq b.$ Using the strict order <, the relation a ⋖ b can be equivalently rephrased as "a < b but not a < c < b for any c". For example, $\{x\}$ is covered by $\{x,z\},$ but is not covered by $\{x,y,z\}.$

covered

Subposets[edit]

A poset $P^{*}=(X^{*},\leq ^{*})$ is called a subposet of another poset $P=(X,\leq )$ provided that $X^{*}$ is a subset of $X$ and $\leq ^{*}$ is a subset of $\leq$ . The latter condition is equivalent to the requirement that for any $x$ and $y$ in $X^{*}$ (and thus also in $X$ ), if $x\leq ^{*}y$ then $x\leq y$ .

If $P^{*}$ is a subposet of $P$ and furthermore, for all $x$ and $y$ in $X^{*}$ , whenever $x\leq y$ we also have $x\leq ^{*}y$ , then we call $P^{*}$ the subposet of $P$ induced by $X^{*}$ , and write $P^{*}=P[X^{*}]$ .

Linear extension[edit]

A partial order $\leq ^{*}$ on a set $X$ is called an extension of another partial order $\leq$ on $X$ provided that for all elements $x,y\in X,$ whenever $x\leq y,$ it is also the case that $x\leq ^{*}y.$ A linear extension is an extension that is also a linear (that is, total) order. As a classic example, the lexicographic order of totally ordered sets is a linear extension of their product order. Every partial order can be extended to a total order (order-extension principle).^[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.

For a ≤ b, the closed interval $[a, b]$ is the set of elements x satisfying a ≤ x ≤ b (that is, a ≤ x and x ≤ b). 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 $(0, 1)$ on the integers is empty since there is no integer $x$ such that $0 < x < 1$ .

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

A convex set in a poset P is a subset $I$ of P with the property that, for any x and y in $I$ and any z in P, if x ≤ z ≤ y, then z is also in $I$ . This definition generalizes the definition of intervals of real numbers. When there is possible confusion with convex sets of geometry, one uses order-convex instead of "convex".

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. 7b), the set {1, 2, 4, 5, 8} is convex, but not an interval.

An interval $I$ is bounded if there exist elements $a,b\in P$ such that $I \subseteq [a, b]$ . Every interval that can be represented in interval notation is obviously bounded, but the converse is not true. For example, let $P = (0, 1) \cup (1, 2) \cup (2, 3)$ as a subposet of the real numbers. The subset $(1, 2)$ is a bounded interval, but it has no infimum or supremum in P, so it cannot be written in interval notation using elements of P.

A poset is called locally finite if every bounded interval is finite. For example, the integers are locally finite under their natural ordering. The lexicographical order on the cartesian product $\mathbb {N} \times \mathbb {N}$ is not locally finite, since $(1, 2) \leq (1, 3) \leq (1, 4) \leq (1, 5) \leq ... \leq (2, 1)$ . Using the interval notation, the property "a is covered by b" can be rephrased equivalently as $[a,b]=\{a,b\}.$

This concept of an interval in a partial order should not be confused with the particular class of partial orders known as the interval orders.