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\le a$.
• $a\le b,b\le a⟹a=b$.
• $a\le b,b\le c⟹a\le c$.

A poset is a set $A$ equipped with a partial order.

e.g. The real numbers $\mathbb{R}$ with their usual ordering $x\le y$ form a partially ordered set that is also linearly ordered: either $x\le y$ or $y\le x$ for any $x,y$.

Monotone Poset Function

A function $m:A\to B$ with posets $(A,{\le }_A)$ and $(B,{\le }_B)$ is monotone if $a{\le }_{A}b⟹m(a){\le }_{B}m(b).$

Total Order

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

Upper Bound

Let $X$ be a nonempty partially ordered set and $A\subset X$ is a totally ordered subset. An upper bound for $A\subset X$ is an element $z\in X$ such that $x\le z$ for all $x\in A$.

Def Maximal Element
A maximal element in a partially ordered set $X$ is an element $x\in X$ such that $y\ge x$ for some $y\in X$ implies $y=x$.

Zorn's Lemma

Let $X$ be a nonempty partially ordered set. If every totally ordered subset of $X$ has an upper bound in $X$, then $X$ 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.