Partially Ordered Set

Partial Order

Definition

A partial order over a set is an arrangement such that, for each pair of elements, one precedes the other.

The word partial indicates that not every pair of elements needs to be comparable, only that adjacent ones do.

In what world would we not have every element comparable? Divisibility is probably the most intuitive relation that would have this. More info at Partially Ordered Set.

Definition

A partial order is a relation that is reflexive, antisymmetric, and transitive.

Example

The relation on a set is a partial order. That is, it fulfils the properties:

  • Reflexive:
  • Antisymmetric: if and then
  • Transitive: if and then

Strict Partial Order

Definition

A strict partial order is a relation that is irreflexive, antisymmetric, and transitive.

Example

The relation on a set is a strict partial order. That is, it fulfils the properties:

  • Irreflexive: not
  • Asymmetric: if , then not
  • Transitive: if and , then

Partially Ordered Set

Definition

A partially ordered set (poset) is a set on which a partial order is defined.

Remark

This is NOT the same as sorting a set, in case this causes confusion.

In addition, the term "partially ordered set" may cause confusion because it implies that it is a set. This isn't really true. A partially ordered set in a way refers to a pair where is some set and is some binary relation. So for example, is a partially ordered set.

However, sometimes the term partially ordered set just refers any set with the relation .

Examples

  • The real numbers (or generally any totally ordered set), ordered by the less-than-or-equal () relation is a partial order
  • The real numbers, ordered by the less-than () or greater-than () relation
  • The power set of a set, ordered by inclusion
  • The natural numbers with the relation of divisibility
  • The subspaces of a vector space ordered by inclusion

Example

The power set of a set, ordered by inclusion, is a partially ordered set.

In this example, we have the Hasse diagram of the power set of a set consisting of three elements, .
Sets connected by a path are comparable (e.g and ; or and ).
However, not all elements are comparable (e.g and ; or and ).

Example

The natural numbers with the relation of divisibility is a partially ordered set.

In this example, we have the divisibility of the numbers 1 to 4. There is a relation from 1 to every number, and a relationship from 2 to 4, but no relationship from 2 to 3 or 4 to 3.