Order

Partial Order

Partial Order

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

• .
• .
• .

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 .

Thrm 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. Proof 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.