Preorder, Partial Order and Posets

Partial Order

Partial Order

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

• .
• .
• .

A poset is a set equipped with a partial order.

e.g. The real numbers with their usual ordering form a partially ordered set that is also linearly ordered: either or for any .

Monotone Poset Function

A function with posets and is monotone if

Total Order

A total order or linear order is a partial order that is also connected.

Upper Bound

Let be a nonempty partially ordered set and is a totally ordered subset. An upper bound for is an element such that for all .

Def Maximal Element A maximal element in a partially ordered set is an element such that for some implies .

Zorn's Lemma

Let be a nonempty partially ordered set. If every totally ordered subset of has an upper bound in , then has a maximal element.

Remark

Zorn’s lemma is equivalent to the axiom of choice: for any collection of nonempty sets, it is possible to form a new set consisting of one element from each member of the collection.