\part{Fundamentals}

\chapter{Orders}

Orders are defined as a special type of  relation, and a fair amount of study can occur totally within the confines of set theoretic notions and methods. That said, the more interesting results will study how they interact with various algebraic structures and topological spaces. These results are what makes order theory so useful in fields like topology and analysis.

The reader would be experienced with working with relations that compare elements with some intuition of being 'higher' or 'lower' in some chain of comparison. In primary school one learns the relation $\leq$ on the sets $\mathbb{N},\mathbb{Z},\mathbb{Q},\mathbb{R}$ as a natural way to compare numbers, one learns $\subseteq$ to compare sets, and in number theory one studies how $|$ compares factors.

Such relations are so crucial and appear so frequently in mathematics that they form their own field of study; order theory. This chapter forms a gentle introduction to a special class of relations called orders that will dominate this book.


\section{Preorders}

Before studying orders, we will cover a relation that will serve as a strong precursor to a order; a preorder. It is very close to what we will call an order; there is one 1 property an order must have has that a preorder doesn't necesarily specify.


\begin{definition}[Preorder]
A \emph{preorder} $\leq$ is a homogeneous relation on a set $P$ that obeys the following properties.
\begin{itemize}
	\item $p \leq p$ Reflexive
	\item $p \leq q \land q \leq r \implies p \leq r$ Transitive
\end{itemize}
The ordered pair $(P,\leq)$ is called a \emph{preordered set} or \emph{preset}.
\end{definition}

Let $(P,\leq )$ be a preset and $Q \subseteq P$, then $(Q, \leq)$ is also a preset.



Under a preorder, it is possible to have elements that act the same under said preorder; we call these elements to be equivalent.
\begin{definition}[Preset equivalence class]
\[ [p] = \{q \in P : \forall r \in P [p \leq r \iff q \leq r ] \}\]
\[ p \sim q \iff [p] = [q] \]
\end{definition}

There is a more elegant way of describing when equivalence occurs, and we will often work with this definition of equivalence henceforth.

\begin{proposition}
\[ p \sim q \iff p \leq q \land q \leq p\]
\end{proposition}


The desire for this statement to hold with equality rather than equivalence is exactly the motivation that begins the deeper study of orders. Orders (also known as partial orders) are indeed preorders where this previous proposition holds with equality rather than equivalence. Ensuring equivalence in this situation gives orders many desirable properties above preorders.


\section{Partial orders}




\begin{definition}[Partial order]
A \emph{partial order} $\leq$ is a homogeneous relation on a set $P$ that obeys the following properties.
\begin{itemize}
	\item $p \leq p$ Reflexive
	\item $p \leq q \land q \leq p \implies p=q$ Antisymmetric
	\item $p \leq q \land q \leq r \implies p \leq r$ Transitive
\end{itemize}
The ordered pair $(P,\leq)$ is called a \emph{partially ordered set} or \emph{poset}.
\end{definition}


\begin{definition}[Strict partial order]
A \emph{strict partial order} $<$ is a homogeneous relation on a set $P$ that obeys the following properties.
\begin{itemize}
	\item $\neg (p < p)$ Irreflexive
	\item $p < q \implies \neg (q < p)$ Antisymmetric
	\item $p < q \land q < r \implies p < r$ Transitive
\end{itemize}
\end{definition}







\section{Total orders}

Within orders, we can identify even nicer types of orders. In posets not every pair of elements may be comparable, partial orders like $(\mathcal{P}(X),\subseteq)$ and $(\mathbb{N},|)$ have examples of noncomparable pairs of elements (set that aren't subsets nor supersets with eachother, numbers that aren't factors nor multiples of one another). Posets where all elements can be compared are especially nice and do appear in mathematics; $(\mathcbb{Z},\leq)$ has this property. This property is called \emph{connectedness}, and is what total orders are all about.

\begin{definition}[Total order]
	A \emph{total order} or \emph{linear order} $\leq$ is a partial order that is strongly connected. That is, the following expression holds.
	$ \forall p,q \in P [ p \leq q \lor q \leq p ]$
	The ordered pair $(P,\leq)$ is called a \emph{totally ordered set} or \emph{toset} or \emph{chain}.
\end{definition}

%We are familiar with the relations $\leq , <$ and what they mean with real numbers. These relations are called \emph{partial orders}; relationships which create some 'rule' of determining which numbers are 'bigger and smaller' than others. Note that $\geq , >$ are easily convertible to $\leq , <$ since $a \leq b \iff b \geq a$ and $a < b \iff b > a$.



\begin{definition}[Strict total order]
A \emph{strict total order} $<$ is a strict partial order that is strongly connected. That is the following expression holds.
$ \forall p,q \in P [ p \neq q \iff p < q \lor q < p ]$
\end{definition}















\section{Least and Minimal elements}


We are familiar with a notion of smallest element.

As it turns out



\begin{definition}[Minimal element]
\[(P,\leq)\]
\[S \subseteq P\]
\[m \in S \text{ is a minimal element of } S \iff \forall s \in S [ s \leq m \implies m \leq s ] \]
\end{definition}


\begin{definition}[Least element]
\[(P,\leq)\]
\[S \subseteq S\]
\[l \in S \text{ is the least element of } S \iff \forall s \in S [ l \leq s]\]
\end{definition}


These definitions seems similar because they often coincide on some of the orders we are familiar with. As it turns out, they are the same notion on tosets!

\begin{proposition}
Let $(P,\leq)$ be a toset and $S \leq P$, then a least element of $S$ is a minimal element of $S$ and vice versa.
\end{proposition}






\subsection{Uniqueness of least and minimal elements}

Minimal and least elements may or may not exist, and presets don't have any conditions that allow us to infer equality, hence one can prove that uniqueness may not hold.
Partial orders are nice enough to assert uniqueness for both of these notions of smallest element!

\begin{proposition}
Let $(P, \leq)$ be a partial order. The least element of a set is unique when it exist.
\end{proposition}

\begin{proposition}
Let $(P, \leq)$ be a partial order. The minimum element of a set is unique when it exists.
\end{proposition}


Since these quantities are unique, we can associate every set with its least element. This is precisely the behaviour of the \emph{minimum function}. For some reason, there isn't a standard notation for minimum elements (and the name of this function makes this even more confusing since it is defined for least elements!). The reason is probably because mathematicians using this notation usually work on tosets where the notions are the same anyways.

\begin{definition}[Minimum function]
Let $(X, \leq)$ be a poset, then the \emph{minimum function of $(X,\leq)$} is a set function $\min : U \subseteq \mathcal{P}(X) \to X$ that returns the least element of a set.
\[\min (S)= m \iff m \text{ is the least element of } (S,\leq)\]
\end{definition}


to end this section we now use our theory to introduce wosets which are extremely important structures in set theory.

\begin{definition}[Well ordering]
A \emph{well-order} is a total order $\leq$ such that all subsets $S \subseteq P$ have a least element $\min (S)$.
The ordered pair $(P,\leq)$ is called a \emph{well-ordered set} or \emph{woset}.
\end{definition}


Take any set $\{p,q\} \subseteq P$, since $(P,\leq )$ is a woset, $\{p,q\}$ must have some least element and therefore either $p \leq q$ or $q \leq p$, meaning wosets are a special type of toset.



\section{Supremums and infimums}

Least elements look for some candidate inside of $S$, and we understand that this least element may not exist. If we take a more liberal approach of allowing some variant of a least element that can be a candidate from the whole $P$ (rather than just $S$), this may be more suitable in various applications.

This finds extreme importance in real analysis as a way to actually define the real numbers!

\begin{definition}[Lower bound]
%\[u \in P \text{ is an upper bound of } S \iff \forall s \in S [ s < u \lor s=u]\]
\[l \in P \text{ is a lower bound of } S \iff \forall s \in S [ l < s \lor l=s]\]
%\[u \in P \text{ is the supremum of } S \iff u = \min \{ p \in P : p \text{ is a lower bound of } S \} \]
\end{definition}


We can probably think of many examples of sets of posets and tosets that have multiple lower bounds. The most interesting lower bound is one that gets as close to the set as possible (and sometimes in the set itself!). this element would be the greatest upper bound, or \emp{infimum}.

This is formed by considering the set of a set's lower bounds, and finding the 'greatest' element of that set (greatest element is essentially a dual notion to least element).

\begin{definition}[Infimum]
	\[i \in P \text{ is the infimum of } S \iff i \text{ is the least element of } \{ p \in P : p \text{ is a lower bound of } S \}\]
\end{definition}


\begin{proposition}
Let $(P,\leq)$ be a poset and $S \subseteq P$, then the infimum of $S$ is unique if it exists
\end{proposition}


\begin{definition}[Infimum function]
\[\inf (S)\]
\end{definition}


\begin{proposition}
Let $(P,\leq)$ be a poset and $S \subseteq P$, then the infimum of $S$ is unique if it exists
\end{proposition}



Note that in a poset with a set S that has a least element $l$ and infimum $\inf(S)$, the least element of $S$ is a lower bound of $S$, yet also in $S$ itself. If $l$ weren't the infimum, then the infimum would satisfy $l \leq \inf(S)$ since it is the greatest lower bound, but since $l\in S$ the infimum is not even a lower bound according to this inequality; a contradiction is reached.

The infimum is less than every element of S by definition, even the least element of S. so we have least less than infimum and infimum less that least; in a poset this implies they must he the same element.


\begin{proposition}
Let $(P,\leq)$ be a poset and $S \subseteq P$ where $\min (S)$ and $\inf (S)$ are both defined, then $\min (S) = \inf (S)$
\end{proposition}

We may get excited and hope that whenever we crack the least element of $S$ it is automatically the infimum. Unfortunately this isn't the case in a poset since even though the least element is never less than another lower bound, it isn't always 'greater' than every other lower bound since posets allow incomparable pairs of elements  If we consider a toset instead of a poset, the connectedness property forces every pair to have some comparison and the least element is indeed the infimum.

\begin{proposition}
Let $(T,\leq)$ be a toset and $S \subseteq T$ where $\min (S)$ is defined, then $\inf(S)$ is defined and $\min (S) = \inf (S)$
\end{proposition}






\section{Dual order}


We have used $\leq$ and $<$ as notation for orders, talked about least elements and infimums. As one may expect, there is a notion of duality so that we can talk about orders like $\geq$, $>$, greatest elements, and supremums. We could have defined everything so far in this fashion, however it turns out to be the same theory anyways, so we will define a notion of duality to represent and easily represent this pheonomenon.

\begin{definition}[Dual order]
Let $\leq$ be a preorder (or strict preorder), the \emph{dual order of $\leq$} is the order $\geq$ defined as such.
\[p \geq q \iff q \leq p\]
\end{proposition}


We can verify that this is indeed always a preorder by checking that the dual of any (strict or not) preorder is a (strict or not) preorder. Furthermore, if $\leq$ is an order we can prove that its dual always an order of the same type. Ultimately all it is really doing is swapping the function of the left argument of the order to the right and vice versa.


\subsection{Maximal and greatest elements}

\begin{definition}[Maximal element]
\[(P,\leq)\]
\[S \subseteq P\]
\[m \in S \text{ is a $(P,\leq)$ maximal element of } S \iff g \in S \text{ is a $(P,\geq)$ minimal element of } S \]
\end{definition}



\begin{definition}[Least element]
\[(P,\leq)\]
\[S \subseteq S\]
\[g \in S \text{ is a $(P,\leq)$ greatest element of } S \iff g \in S \text{ is a $(P,\geq)$ least element of } S \]
\end{definition}

\subsection{Upper bounds and supremum}


\begin{definition}[Supremum]
	\[u \in P \text{ is a $(P,\leq)$ supremum of } S \iff u \in P \text{ is a $(P,\geq)$ infimum of }S \]
\end{definition}


\begin{definition}[Supremum function]
\[\sup (S)\]
\end{definition}