Order

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$.

Total Order (Linear order)

A total order or linear order is a partial order that is also connected. Equivalently, $⟨X,\le ⟩$ is a linear ordering if it is a partial ordering such that for every $a,b\in X$ either $a\le b$ or $b\le a$ (note both are true precisely when $a=b$). Equivalently, if for every $a,b\in X$ with $a\ne b$, either $a<b$ or $b<a$.

Well Ordering

A (nonempty) linear ordering $⟨L,<⟩$ is a well-ordering if every nonempty subset of $L$ contains a least element.

Order-preserving function

If $⟨L,<⟩$ and $⟨L^{\prime },{<}^{\prime }⟩$ are linear orderings, a function $f:L\to L^{\prime }$ is order-preserving, or equivalently is increasing, if $x<y$ implies $f(x)<f(y)$. If $f:L\to L^{\prime }$ is bijective (one-one and onto) and both $f$ and its inverse $f^{-1}$ are order-preserving, then $f$ is an isomorphism. If the function $f:L\to L$ is an isomorphism onto itself it is an automorphism of $⟨L,<⟩$.

Lemma

If $⟨L,<⟩$ is a well-ordering and $f:L\to L$ is an order-preserving function, then $x\le f(x)$ for all $x\in L$.

$Proof$. If not, consider the least z such that $z\nleqq f(z)$, or equivalently $f(z)<z$, and let $w=f(z)$. Then $f(f(z))<f(z)$, that is $f(w)<w$. Since w $(:=f(z))<z$, this contradicts $z$ is the least element of $L$ such that of $L$ such that $f(z)<z.$

Corollary

• If $⟨L,<⟩$ is a well-ordering and $f:L\to L$ is an automorphism, then $f$ is the identity function.
• If $⟨L,<⟩$ and $⟨L^{\prime },{<}^{\prime }⟩$ are isomorphic well-orderings then the isomorphism is unique.

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$.

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