A non-strict partial order, often simply termed partial order is a homogeneous binary relation <= on a set P that is reflexive, anti-symmetric, and transitive.

A strict partial order is a homogeneous binary relation < on a set P that is irreflexive, anti-symmetric, and transitive.

We observe that every non-strict partial order can be converted trivially into a strict partial order, and vice versa. In what follows, we use the term partial order refers to non-strict partial order.

A partially ordered set, or poset for short, is a pair (P, <=) where P is a set and <= is a partial order on P. The poset (P, <=) defines a directed graph whose vertices are the elements of P and (a,b) is a directed edge whenever a <= b holds. Conversely, a poset can be defined from a directed graph, assuming that the defined binary relation is anti-symmetric, and transitive, and, either reflexive, or irreflexive. Consequently, a poset can be given by an adjacency list or an adjacency matrix of a directed graph. In practice, it is also convenient to define its transitive reduction, see this latter term below.

We say that two posets are equal (resp. isomorphic) whenever they are equal (resp. isomorphic) as directed graphs.

The connected components of a poset are the connected components of its associated directed graph

From now on, we fix a poset (P, <=). Two elements a and b of P are said to be comparable if either a <= b or b <= a holds, otherwise a and b are said to be incomparable.

The partial order <= is said to be total whenever any two elements of P are comparable.

A subset C of P is called a chain if any two elements of C are comparable. A chain C of P is said to be maximal if P does not admit another chain D of which C would be a proper subset.

A subset C of P is called an antichain if any two distinct elements of C are incomparable. An antichain C of P is said to be maximal if P does not admit another antichain D of which C would be a proper subset. We note that any singleton of P is both a chain and an antichain.

The element a of P is strictly less than the element b of P if a <= b and a \303\242\302\211\302\240 b both hold.

The element b of P covers the element a of P if a is strictly less than b and for no element c of P, distinct from both a and b, both a <= c and c <= b hold.

The relation b covers a defines a homogeneous binary relation on P which is the transitive reduction of (P, <=). This is also a directed acyclic graph on P often refers as the Hasse diagram of (P, <=).

Let S be a subset of P and a be an element of S. We say that a is a greatest element (resp. least element) of S if for every element b of S we have b <= a (resp. a <= b). Observe that if S has a greatest element (resp. least element) then it is unique.

The element a of P is a maximal element of (P, <=) if for no element b of P the element a is strictly less than b. The element a of P is a minimal element of (P, <=) if no element b of P is strictly less than a. Observe that if P is not empty then it necessarily admits at least one maximal element and at least one minimal element. Observe also that if P admits a greatest (least) element, then this element is its unique maximal (resp. minimal) element.

Let S be a subset of P and a be an element of P. We say that a is an upper bound (resp. lower bound) of S if if for every element b of S we have b <= a (resp. a <= b). Observe that a need not be in S in order to be an upper bound (resp. lower bound) of S.

We say that a is the infimum of S, or the greatest lower bound of S, if a is the greatest element among all lower bounds of S.

We say that a is the supremum of S, or the lest upper bound of S, if a is the least element among all upper bounds of S.

From now on, we assume that P is finite.

A chain decomposition of the poset (P, <=) is a partition of P into disjoint chains. Dilworth's theorem states that the cardinality of an antichain with maximum cardinality is equal to the cardinality of a chain decomposition of minimum cardinality. This common number is by definition the width of the poset (P, <=).

An antichain decomposition of the poset (P, <=) is a partition of P into disjoint antichains. Mirsky's theorem states that the cardinality of a chain with maximum cardinality is equal to the cardinality of antichain decomposition of minimum cardinality. This common number is by definition the height of the poset (P, <=).

We call rank function on the poset (P, <=) any function r defined on P, taking integer values and so that for any two elements a and b of P, if b covers a then r(b) = r(a) + 1 holds.

The poset (P, <=) is said to be graded if it admits a rank function.

The poset (P, <=) is said to be ranked if all its maximal chains have the same cardinality.

We note that the terms graded poset and ranked poset have slightly different definitions in some textbooks, like the ones of Richard Stanley. We refer to the wikipedia pages of ranked poset and graded poset for a discussion on these terminology issues.

The poset (P, <=) is called a meet-semilattice if for any two elements a and b of P the {a, b} admits a greatest lower bound. The poset (P, <=) is called a join-semilattice if for any two elements a and b of P the {a, b} admits admits a least upper bound.

The poset (P, <=) is called a lattice if it is both a join- and a meet-semilattice. If (P, <=) is a lattice, then every non-empty subset S of P has a least upper bound and a greatest lower bound.

The faces of any polyhedral set Q, ordered by set theoretic inclusion, form a lattice L which enjoys three important properties (that are not true in general for an arbitrary lattice): (1) L is graded, (2) L is ranked, and (3) if the ranks of two faces a > b differ by 2, then there are exactly 2 faces that lie strictly between a and b.

The poset (P, <=) is called a face lattice if it is isomorphic to the lattice of the faces of a polyhedral set.