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

,

≤

)

{\displaystyle P=(X,\leq )}

consisting of a set

X

{\displaystyle X}

(called the ground set of

P

{\displaystyle P}

) and a partial order

≤

{\displaystyle \leq }

on

X

{\displaystyle X}

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

X

{\displaystyle X}

itself is sometimes called a poset.

Partial order relations

The term partial order usually refers to the reflexive partial order relations, referred to in this article as non-strict partial orders. However some authors use the term for the other common type of partial order relations, the irreflexive partial order relations, also called strict partial orders. Strict and non-strict partial orders can be put into a one-to-one correspondence, so for every strict partial order there is a unique corresponding non-strict partial order, and vice versa.

Partial orders

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

P

{\displaystyle P}

that is reflexive, antisymmetric, and transitive.