Partially ordered set

In mathematics, especially order theory, a partially ordered set (also 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 indicating that, for certain pairs of elements in the set, one of the elements precedes the other in the ordering. The relation itself is called a “partial order.”

The word partial in the names “partial order” and “partially ordered set” is used as an indication that not every pair of elements needs to be comparable. That is, there may be pairs of elements for which neither element precedes the other in the poset. Partial orders thus generalize total orders, in which every pair is comparable.

Fig.1 The Hasse diagram of the set of all subsets of a three-element set {\displaystyle {x,y,z},}{\displaystyle {x,y,z},} ordered by inclusion. Sets connected by an upward path, like {\displaystyle \emptyset }\emptyset and {\displaystyle {x,y}}{x,y}, are comparable, while e.g. {\displaystyle {x}}{x} and {\displaystyle {y}}{y} are not.

1 Informal definition

A partial order defines a notion of comparison. 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.[1][2]

A set with a partial order is called a partially ordered set (also called a poset). The term ordered set is sometimes also used, 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.

A poset can be visualized through its Hasse diagram, which depicts the ordering relation.[3]

2 Partial order relation

2.1 Non-strict partial order

2.2 Strict partial order

2.3 Correspondence of strict and non-strict partial order relations

2.4 Dual orders

3 Notation

4 Examples

4.1 Orders on the Cartesian product of partially ordered sets

4.2 Sums of partially ordered sets

5 Derived notions

5.1 Extrema

6 Mappings between partially ordered sets

7 Number of partial orders

8 Linear extension

9 Directed acyclic graphs

10 In category theory

11 Partial orders in topological spaces

12 Intervals

13 See also