\documentclass{article}

\usepackage[english]{babel}

\usepackage{amsmath}
% for symbols such as /implies
\usepackage{amssymb}
% for symbols such as /subsetneq
\usepackage{amsthm}
% for commands such as \newtheorem

\theoremstyle{definition}
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{definition}{Definition}
\newtheorem{example}{Example}
\newtheorem{axiom}{Axiom}

\begin{document}

\section{Ordered Sets}

\subsection{Partially Ordered Sets}

% partial order relation
\begin{definition}
  A relation $R$ on a set $A$ is a \emph{partial order relation} if $R$ is reflexive, antisymmetric, and transitive. Partial order relations are often denoted by $\leq$. If $\leq$ is a partial order relation on a set $A$, then $(A, \leq)$ is called a \emph{partially ordered set}, or \emph{poset}.
\end{definition}

% strict partial order relation
\begin{definition}
  A relation $R$ on a set $A$ is a \emph{strict partial order relation} if $R$ is irreflexive, asymmetric, and transitive. Strict partial order relations are often denoted by $<$. If $<$ is a strict partial order on a set $A$, then $(A, <)$ is called a \emph{strictly partially ordered set}.
\end{definition}

\begin{theorem}
  If $(A, \leq)$ is a partially ordered set, then the relation $<$ defined by
  $$
    \forall a,b\in A \quad a < b \iff (a \leq b) \land (a \neq b)
  $$
  is a strict partial order on $A$. In particular, every partially ordered set admits a strict partial order.
  \begin{proof}
    Let $(A, \leq)$ be a partially ordered set and define the relation $<$ on $A$ as above. Let $a,b,c\in A$. Since $a=a$
    $$
      \lnot (a < a)
    $$
    and $<$ is irreflexive. Suppose $a < b$. Then $a \leq b$ and $a \neq b$. Since $\leq$ is antisymmetric $\lnot (b \leq a)$. Hence
    $$
      \lnot (b < a)
    $$
    and $<$ is asymmetric. Suppose $a < b$ and $b < c$. Then $a \leq b$, $a \neq b$, $b \leq c$, and $b \neq c$. Since $\leq$ is transitive, $a \leq c$. Since $\leq$ is antisymmetric, $a \neq c$ (if $a=c$, then $a\leq b$ and $b \leq a$, but $a \neq b$.) It follows that 
    $$
      a < c
    $$
    and $<$ is transitive. Then $<$ is a strict partial order relation on $A$.
  \end{proof}
\end{theorem}

% minimal/maximal/smallest/largest elements
\begin{definition}
  Let $(A, \leq)$ be a partially ordered set. Let $m\in A$. If
  $$
    \lnot (\exists a\in A \quad a < m)
  $$
  then $m$ is called a \emph{minimal element} of $A$. If
  $$
    \forall a\in A \quad m \leq a
  $$
  then $m$ is called a \emph{smallest element} of $A$. If
  $$
    \lnot (\exists a\in A \quad m < a)
  $$
  then $m$ is called a \emph{maximal element} of $A$. If
  $$
    \forall a\in A \quad a \leq m
  $$
  then $m$ is called a \emph{largest element} of $A$.
\end{definition}

\begin{theorem}
  Let $(A, \leq)$ be a partially ordered set. If $A$ has a smallest element, then it is unique. If $A$ has a largest element, then it is unique.
  \begin{proof}
    Suppose $m\in A$ and $M\in A$ are smallest elements of $A$. Then $m \leq M$ and $M \leq m$. Since $\leq$ is antisymmetric, $m = M$. Likewise suppose $m\in A$ and $M\in A$ are largest elements of $A$. Then $M \leq m$ and $m \leq M$. Since $\leq$ is antisymmetric, $m = M$.
  \end{proof}
\end{theorem}

\subsection{Totally Ordered Sets}

% total order relation
\begin{definition}
  A partial order relation $\leq$ on a set $A$ is a \emph{total order relation}, or \emph{linear order relation}, if $\leq$ is strongly connected. That is
  $$
    \forall a,b\in A \quad (a \leq b) \lor (b \leq a).
  $$
  If $\leq$ is a total order relation on a set $A$, we call $(A, \leq)$ a \emph{totally ordered set}, or \emph{linearly ordered set}.
\end{definition}

% strict total order relation
\begin{definition}
  A strict partial order relation $<$ on a set $A$ is a \emph{strict total order relation}, or \emph{strict linear order relation}, if $<$ is connected. That is
  $$
    \forall a,b\in A \quad a\neq b \implies (a < b) \lor (b < a).
  $$
  If $<$ is a strict total order relation on a set $A$, we call $(A, <)$ a \emph{strictly totally ordered set}, or \emph{strictly linearly ordered set}.
\end{definition}

\begin{theorem}
  Let $(A, \leq)$ be a totally ordered set. The following hold.
  \begin{enumerate}
    \item If $x,y\in A$, then $x < y \iff \lnot (y\leq x)$.
    \item If $m\in A$ is a minimal element of $A$, then $m$ is the smallest element of $A$.
    \item If $M\in A$ is a maximal element of $A$, then $M$ is the largest element of $A$.
  \end{enumerate}
  \begin{proof}
    Let $x,y\in A$. Suppose $x < y$. Then $x\leq y$ and $x\neq y$. Since $\leq$ is antisymmetric, $\lnot (y\leq x)$. On the other hand, suppose $\lnot (y\leq x)$. Since $\leq$ is strongly connected, $x \leq y$. Since $\leq$ is reflexive, $x\neq y$. It follows that $x < y$.

    Let $m\in A$ be a minimal element of $A$. Suppose $m$ is not the smallest element of $A$. Then there is $a\in A$ such that $\lnot (m \leq a)$. Then $a < m$, contradicting the assumption that $m$ is a minimal element of $A$.

    Let $M\in A$ be a maximal element of $A$. Suppose $M$ is not the largest element of $A$. Then there is $a\in A$ such that $\lnot (a \leq M)$. Then $M < a$, contradicting the assumption that $M$ is a maximal element of $A$.
  \end{proof}
\end{theorem}

% intervals
\begin{definition}
  Let $(A, \leq)$ be a totally ordered set. For any $a,b\in A$, we define \emph{intervals} as the following sets.
  \begin{align*}
    [a,b] &= \{x\in A : a \leq x \leq b\} \\
    (a,b) &= \{x\in A : a < x < b\} \\
    [a,b) &= \{x\in A : a \leq x < b\} \\
    (a,b] &= \{x\in A : a < x \leq b\}
  \end{align*}
\end{definition}

\subsection{Well-Ordered Sets}

% well-ordered set
\begin{definition}
  A totally ordered set $(A, \leq)$ is \emph{well-ordered} if for each $B \subseteq A$, there is $m\in B$ such that $m$ is a minimal element of $B$.
\end{definition}

\begin{corollary}
  If $(A, \leq)$ is well-ordered, then there is $m\in A$ such that $m$ is the smallest element of $A$. We denote $m$ by $0_A$.
  \begin{proof}
    Let $(A, \leq)$ be a well-ordered set. Since $A \subseteq A$, there is $m\in A$ such that $m$ is a minimal element of $A$. Since $\leq$ is a total order, $m$ is the smallest element of $A$.
  \end{proof}
\end{corollary}

% initial segment
\begin{definition}
  Let $(A, \leq)$ be a well-ordered set. We call $S \subseteq A$ an \emph{initial segment} of $A$ if
  $$
    \forall s \in S \ \forall a \in A \quad a < s \implies a \in S.
  $$
\end{definition}

% order homomorphism/isomorphism
\begin{definition}
  Let $(A,\leq_A)$ and $(B,\leq_B)$ be partially ordered sets. An \emph{order homomorphism} is a function $\varphi : A \to B$ such that
  $$
    \forall x,y\in A \quad x \leq_A y \implies \varphi(x) \leq_B \varphi(y).
  $$
  An \emph{order isomorphism} is a bijective function $\varphi : A\to B$ such that
  $$
    \forall x,y\in A \quad x \leq_A y \iff \varphi(x) \leq_B \varphi(y).
  $$
  If $\varphi : A \to B$ is an order isomorphism, we call $(A, \leq_A)$ and $(B, \leq_B)$ \emph{order isomorphic} and write $A \cong B$.
\end{definition}

\begin{lemma}
  Suppose $(A, \leq)$ and $(B, \leq)$ are well-ordered. If $\varphi: A \to B$ is an order isomorphism, then the following hold.
  \begin{enumerate}
    \item $\varphi(0_A) = 0_B$.
    \item $\forall a\in A \quad \varphi([0_A, a]) = [0_B, \varphi(a)] \land \varphi([0_A, a)) = [0_B, \varphi(a))$.
  \end{enumerate}
  \begin{proof}
    Let $\varphi : A\to B$ be an order isomorphism. Since $\varphi$ is bijective, it is surjective.
    
    Since $\varphi$ is surjective, there is $z\in A$ such that $\varphi(z)=0_B$. 
    Since $0_A$ is the smallest element of $A$, we have $0_A \leq z$. If $0_A < z$, then $\varphi(0_A) < \varphi(z) = 0_B$, contradicting that $0_B$ is the smallest element of $B$. It follows that $\varphi(0_A) = 0_B$.

    Let $a\in A$. 

    Let $x\in [0_A,a]$. Then $0_A \leq x \leq a$. Since $\varphi$ is an order isomorphism, we have $\varphi(0_A) \leq \varphi(x) \leq \varphi(a)$. 
    Since $\varphi(0_A) = 0_B$, we have $\varphi(x)\in [0_B,\varphi(a)]$. Then $\varphi([0_A,a])\subseteq [0_B,\varphi(a)]$.

    Let $y\in [0_B,\varphi(a)]$. Then $0_B \leq y \leq \varphi(a)$. Since $\varphi$ is surjective, there is $x\in A$ such that $\varphi(x)=y$.
    Since $\varphi(0_A) = 0_B$, we have $\varphi(0_A) \leq \varphi(x) \leq \varphi(a)$. Since $\varphi$ is an order isomorphism, we have $0_A \leq x \leq a$.
    Then $x\in [0_A,a]$ and $y=\varphi(x)\in\varphi([0_A,a])$. Then $[0_B,\varphi(a)]\subseteq \varphi([0_A,a])$.

    It follows that $\varphi([0_A,a]) = [0_B,\varphi(a)]$. The proof that $\varphi([0_A,a)) = [0_B,\varphi(a))$ is nearly identical.
  \end{proof}
\end{lemma}

\begin{theorem}
  If $(A, \leq_A)$ and $(B, \leq_B)$ are nonempty well-ordered sets, then there is a unique order isomorphism from one of the sets onto an initial segment of the other.
  \begin{proof}
    (Existence) WIP

    (Uniqueness) Without loss of generality, suppose there is an order isomorphism from $A$ onto an initial segment of $B$.
    Let $S_1,S_2$ be initial segments of $B$ and suppose $f:A\to S_1$ and $g:A\to S_2$ are order isomorphisms. Let
    $$
      C = \{x\in A : f(x)\neq g(x)\}.
    $$
    Suppose towards a contradiction that $C$ is nonempty. Since $C\subseteq A$ is nonempty and $A$ is well-ordered, there is a minimal element $c\in C$.
    Let $x\in [0_A,c)$. Then $0_A \leq x < c$. Then $x\notin C$ since $c$ is a minimal element in $C$. Then $f(x)=g(x)$. 
    It follows that $f([0_A,c)) = g([0_A,c))$. Since $f$ and $g$ are order isomorphisms
    $$
      [0_B, f(c)) = f([0_a,c)) = g([0_A,c)) = [0_B,g(c)).
    $$
    Let $b\in B$. Let $I = B\setminus [0_B,f(c))$. Then $b\in I \iff \lnot (b<f(c))$. Since $B$ is a totally ordered set, $b\in I \iff f(c)\leq b$.
    Since $[0_B, f(c)) = [0_B,g(c))$, we have $I = B\setminus [0_B,g(c))$. Then $b\in I \iff \lnot (b<g(c))$. Since $B$ is a totally ordered set, $b\in I \iff g(c)\leq b$. It follows that $f(c)\in I$, $g(c)\in I$, and both are smallest elements of $I$. Since smallest elements are unique, we have $f(c)=g(c)$.
    This contradicts $c\in C$. It follows that $C$ is empty.

    Then $f(x)=g(x)$ for all $x\in A$. Since $f$ and $g$ are surjective, $S_1 = f(A) = g(A) = S_2$. It follows that $f=g$. 
  \end{proof}
\end{theorem}

\end{document}