\documentclass{amsart}
\usepackage[parfill]{parskip}   
\usepackage{graphicx}
\usepackage{amssymb, latexsym}
\usepackage{epstopdf}
\usepackage{color}
\DeclareGraphicsRule{.tif}{png}{.png}{`convert #1 `dirname #1`/`basename #1 .tif`.png}

\textwidth = 6.5 in
\textheight = 9 in
\oddsidemargin = 0.0 in
\evensidemargin = 0.0 in
\topmargin = 0.0 in
\headheight = 0.0 in
\headsep = 0.0 in
\parskip = 0.2in
\parindent = 0.0in
\pagestyle{plain}


\newsavebox{\savepar}
\newenvironment{xbox}{\begin{lrbox}{\savepar}
\begin{minipage}[c]{\textwidth}}
{\end{minipage}\end{lrbox}\fcolorbox{black}{green}{\usebox{\savepar}}}

\renewcommand{\baselinestretch}{1.3}

\theoremstyle{plain}
\newtheorem{theorem}{Theorem}[section]
\newtheorem{cor}[theorem]{Corollary}
\newtheorem{prop}[theorem]{Proposition}
\newtheorem{lem}[theorem]{Lemma}


\theoremstyle{definition}
\newtheorem*{definition}{Definition}
\newtheorem*{defn}{Definition}
\newtheorem{example}{Example}

\theoremstyle{remark}
\newtheorem*{notation}{Notation}
\newtheorem*{note}{Note}



\begin{document}
\setcounter{section}{2}
\section{Ordered Sets}

\subsection{Ordered Sets}

\begin{defn}
A \emph{partial order} on a set $S$ is a relation $P$ that is reflexive, transitive and \emph{antisymmetric}, meaning that for all $x, y \in S$, if $x \, P \, y$ and $y \, P \, x$, then $x = y$.  A set  together with a partial order is called a \emph{partially ordered set}.
\end{defn}


\begin{xbox}
\begin{example}
Set inclusion $\subseteq$ defines a partial order on any collection of sets.
\end{example}
\end{xbox}


\begin{xbox}
\begin{example}
Divisibility ({\it i.e.} $a \mid b \iff b=ak$ for some $k \in \mathbb{Z}$) defines a partial order on $\mathbb{P}$ but not on $\mathbb{Z}$.
\end{example}
\end{xbox}


\begin{xbox}
\begin{example}
The ordering defined in Chapter 2 is a partial order on the collection of cardinal numbers.
\end{example}
\end{xbox}

\begin{defn}
A \emph{quasi-order} on a set $S$ is a relation $Q$ that is transitive and \emph{irreflexive}, meaning that for all $x \in S$, it is \emph{not} the case that $x \, Q \, x$.
\end{defn}

\begin{prop}
Let $S$ be a set.
\begin{enumerate}
\item If $P$ is a partial order on $S$, then $x \, Q \, y \iff (x \, P \, y$ and  $x \neq y$) defines a quasi-order on $S$.  
\item If $Q$ is a quasi-order on $S$, then $x \, P \, y \iff (x \, Q \, y$ or  $x = y$) defines a partial order on $S$.
\end{enumerate}
\end{prop}

\begin{xbox}
\begin{proof}
\end{proof}
\end{xbox}


\begin{notation}
A partial order is usually denoted by $\preceq$, and the corresponding quasi-order by $\prec$.  For $x, y \in S$,  $x \preceq y$ is read ``$x$ precedes $y$",  $x \prec y$ is read ``$x$ strictly precedes $y$" and  $x \succeq y$ is read ``$x$ succeeds $y$".
\end{notation}


\begin{defn}
If $x$ and $y$ are distinct elements in a partially ordered set, then $x$ and $y$ are \emph{comparable} iff either $x \prec y$ or $y \prec x$.  A \emph{totally ordered} (or \emph{linearly ordered}) set is a partially ordered set in which every pair of distinct elements is comparable.  A \emph{chain} is a totally ordered subset of a partially ordered set.
\end{defn}

\begin{xbox}
\begin{example}
The ordering defined in Chapter 2 is a total order on the collection of cardinal numbers.
\end{example}
\end{xbox}

\begin{xbox}
\begin{example}
The set $\wp(\{a, b, c\})$ is not totally ordered by set inclusion because..... A 4-element chain in this partially ordered set is ...
\end{example}
\end{xbox}


\begin{example}
If $S$ and $T$ are partially ordered sets, then the \emph{product order},  given by 
\[
(s, t) \preceq (s^\prime, t^\prime) \iff s \preceq s^\prime \text{ and }  t \preceq t^\prime,
\]
 is a partial order on the Cartesian product $S \times T$.  Since the partial orders on $S$ and $T$ are each reflexive, $s \preceq s$ in $S$ and $t \preceq t$ in $T$, and so $(s,t) \preceq (s, t)$ in $S \times T$.  
 Suppose  $(s, t) \preceq (s^\prime, t^\prime)$ and  $(s^\prime, t^\prime)\preceq (s^{\prime \prime}, t^{\prime \prime})$.  Then by definition, $s \preceq s^\prime$ and $s^\prime \preceq s^{\prime\prime}$ in $S$, and $t \preceq t^\prime$ and $t^\prime \preceq t^{\prime\prime}$ in $T$.  
 Since the partial orders on $S$ and $T$ are each transitive, we can conclude 
 $s \preceq s^{\prime\prime}$ in $S$ and $t \preceq t^{\prime\prime}$ in $T$,
 and so $(s, t) \preceq (s^{\prime\prime}, t^{\prime\prime})$.
 Finally, suppose $(s, t) \preceq (s^\prime, t^\prime)$ and $(s^\prime, t^\prime) \preceq (s, t)$.  
 Then by definition, $s \preceq s^\prime$ and $s^\prime \preceq s$ in $S$, and $t \preceq t^\prime$ and $t^\prime \preceq t$ in $T$.  Since the partial orders on $S$ and $T$ are each antisymmetric, $s = s^\prime$ and $t = t^\prime$, and so $(s, t) = (s^\prime, t^\prime)$.
\end{example}


\begin{xbox}
\begin{example}
If $S$ and $T$ are totally ordered sets, then the \emph{lexicographic order}  given by 
\[
(s, t) \prec (s^\prime, t^\prime) \iff  s \prec s^\prime \text{ or } [s = s^\prime \text{ and } t \prec t^\prime]
\]
 is a total order on $S \times T$.
 [\emph{Hint.} Show that this defines a quasi-order on $S \times T$, then use Proposition 3.1.]
\end{example}
\end{xbox}


\begin{xbox}
\begin{example}
Let $\mathbb{P}$ be the set of positive integers with the usual order, and let $\mathbb{A}$ be the alphabet with the usual order.   [Find all maximal (\emph{i.e.} longest possible) chains of the following subset of  $\mathbb{P} \times \mathbb{A}$, first under the product order and then under the lexicographic order: $ \big \{(2,z), (1, c), (2, c), (1, y), (4, b), (4, z), (3, b), (2, a) \big \}$.]
\end{example}
\end{xbox}

\begin{xbox}
\begin{defn}
A \emph{totally ordered collection of disjoint totally ordered sets} is a collection $\mathcal{A} = \{A_i \mid i \in I\}$, where $I$ is a totally ordered set,  $A_i$ is a totally ordered set for each $i \in I$ and $A_i \cap A_j = \emptyset$ for $i \neq j$. The \emph{concatenation order} on $S = \bigcup \{A_i \mid i \in I \}$ is given by
\[
s \prec t \iff
\begin{cases}
s \in A_i \text{ and } t \in A_j \text{ and } i \prec j \text{ in } I, \text{ or }\\
s, t \in A_i \text{ and } s \prec t \text { in } A_i.
\end{cases}
\]
[Show that this defines a total order on $S$.]
\end{defn}
\end{xbox}

\begin{notation}
If $I=\{1, 2, \dots, n\}$, then $S = A_1 \cup \dots \cup A_n$ together with the concatentation order is denoted by $S = \{ A_1 \, : \, A_2 \, : \dots : A_n\}$.
\end{notation}

\begin{example}
In the totally ordered set $\mathbb{P}^* \equiv \{1, 3, 5, \dots: 2, 4, 6, \dots\}$, every odd positive integer strictly precedes every even positive integer.
\end{example}


\begin{defn}
Let  $s$  and $t$ be elements of a partially ordered set $S$.  Then $s$ is an \emph{immediate predecessor} of $t$, and $t$ is an \emph{immediate successor} of $s$, iff $s \prec t$ and there does not exist $u \in S$ such that $s \prec u \prec t$. 
This is denoted by  $s \prec \prec t$.
\end{defn}

\begin{xbox}
\begin{example}
(Give examples of partially ordered sets such that (a) every element has an immediate predecessor; (b) no element has an immediate predecessor; (c) some elements do and some elements don't have immediate predecessors.)
\end{example}
\end{xbox}


\begin{xbox}
\begin{example}
Using this new terminology, the Continuum Hypothesis can be rephrased as: ...
\end{example}
\end{xbox}


\begin{xbox}
\begin{defn} Let $S$ be a partially ordered set. Then $s \in S$ is:
\begin{enumerate}
\item  \emph{minimal} iff it is not strictly preceded by any other element; that is, for all $x \in S$, $ x \preceq s \Rightarrow x = s$;
\item  \emph{maximal} iff....;
\item a \emph{first} element iff for all $x \in S$, $s \preceq x$;
\item a \emph{last} element iff...
\end{enumerate}
\end{defn}
\end{xbox}

\newpage
\begin{prop}
\hfill
\begin{enumerate}
\item If a partially ordered set has a first element, then it is unique, but it may have more than one minimal element.
\item Any first element in a partially ordered set  is minimal, but the converse is false.
\item In a totally ordered set, any minimal element is a first element.
\end{enumerate}
Analogous statements hold for last and maximal elements.
\end{prop}

\begin{xbox}
\begin{proof}
\end{proof}
\end{xbox}

\begin{xbox}
\begin{example}
Let $\mathbb{P}$ be the positive integers, $\mathbb{A}$ the alphabet,  and $\mathbb{B} = \{ \dots, -3, -2, -1 \}$, all with the usual order. Suppose $S = \{ \mathbb{P} : \mathbb{A} : \mathbb{B}\},\, T = \{ \mathbb{A} : \mathbb{B}  : \mathbb{P} \}, \,U = \{\mathbb{B} : \mathbb{P} : \mathbb{A}\}$ and $V=\{ \mathbb{B} : \mathbb{A} : \mathbb{P} \}$. [For each of these concatenated sets: does it have a first element? a last element? \emph{other than} first/last elements,  which element(s), if any, have no immediate predecessor? no immediate successor?]
\end{example}
\end{xbox}

\begin{defn}
Let $S$ be a partially ordered set and let $A \subseteq S$.  Then $u\in S$ is an \emph{upper bound} on $A$ iff $a \preceq u$ for all $a \in A$.  Note that $u$ may or may not itself be an element of $A$.  Similarly, $l$ is a lower bound on $A$ iff $l \preceq a$ for all $a \in A$.
\end{defn}


\begin{example}
Let $\mathcal{T}$ be a collection of sets, partially ordered by set inclusion and  let $\mathcal{A}$ be a subcollection of $\mathcal{T}$.  If $U \in \mathcal{T}$ is an upper bound on $\mathcal{A}$, then $A \subseteq U$ for all $A \in \mathcal{A}$.  Moreover, the set $B = \bigcup \{A\, | \, A \in \mathcal{A}\}$ is an upper bound on $\mathcal{A}$, {\it provided} $B \in \mathcal{T}$.
\end{example}

\begin{example}
The \emph{completeness property} of $\mathbb{R}$ is an order property.  Specifically, it states that if a nonempty subset $A$  of $\mathbb{R}$ has an upper bound,  then it has a least upper bound (a \emph{supremum}).  If we let  $U(A)$  denote the set of upper bounds of  $A$, then the completeness property says that if  $U(A)$  is nonempty, then it has a first element. 
\end{example}
 
\subsection{Order-preserving Functions}

\begin{defn}
A function $f:S \to T$ from one partially ordered set to another is called \emph{order-preserving} iff for all $s, s^\prime \in S$, $\left [ s \preceq s^\prime \iff f(s) \preceq f(s^\prime) \right ]$.  
An order-preserving bijection $f:S \to T$ is called an \emph{order-isomorphism}; in this case, the sets $S$ and $T$ are called \emph{order-isomorphic}, denoted by $S \simeq T$.
\end{defn}



\begin{lem}
Let $f:S \to T$ be a function from one partially ordered set to another.
\begin{enumerate}
\item If $f$ is an injection, then $f$ is order-preserving if and only if for all $s, s^\prime \in S$, $ \left [s \prec s^\prime  \iff f(s) \prec f(s^\prime) \right ]$.
\item If  $f$ is order-preserving and $S$ is totally ordered, then $f$ is injective.  This need not be the case if $S$ is not totally ordered.
\item If $f$ is a bijection, $S$ is totally ordered and for all $s, s^\prime \in S, s \prec s^\prime$ implies $ f(s)  \prec f(s^\prime)$, then $f$ is an order-isomorphism.
\item If $f$ is an order-isomorphism and $C \subseteq S$, then $f \mid_C :C \to f(C)$ is also an order-isomorphism.
\end{enumerate}
\end{lem}

\begin{xbox}
\begin{proof}
\end{proof}
\end{xbox}

\begin{xbox}
\begin{example}
The function $f:\mathbb{P} \to \mathbb{E}$ given by $f(n)=2n$ is an order-isomorphism, but the function $g:\mathbb{P} \to \{\dots, -3, -2, -1\}$ given by $g(n) = -n$ is not (where these sets are all ordered in the usual way).
\end{example}
\end{xbox}

\begin{prop}
Order-isomorphism is an equivalence relation on any collection of partially ordered sets.
\end{prop}

\begin{xbox}
\begin{proof}
\end{proof}
\end{xbox}


\begin{theorem}
Let $f:S \to T$ be an order-isomorphism of partially ordered sets.  Then
\begin{enumerate}
\item $S$ is totally ordered if and only if $T$ is totally ordered;
\item$s \in S$ is a first/minimal/last/maximal element of $S$ if and only if $f(s) \in T$ is a first/minimal/last/maximal element of $T$;
\item for all $s, s^\prime \in S$, $s \prec \prec s^\prime$ iff $f(s) \prec \prec f(s^\prime)$. 
\end{enumerate}
\end{theorem}

\begin{xbox}
\begin{proof} 

[For (2), prove the statement \emph{only} for first and minimal elements.]
\end{proof}
\end{xbox}


\begin{prop}
Let $S$ and $T$ be partially ordered sets.  If $S \simeq T$, then $S \sim T$, but the converse is false.
\end{prop}

\begin{xbox}
\begin{proof}
\end{proof}
\end{xbox}

\framebox[\textwidth][c]{
\parbox{.9\textwidth}{
\begin{defn}
Each \emph{totally} ordered set is assigned a symbol in such a way that two totally ordered sets are assigned the same symbol if and only if they are order-isomorphic.  This symbol is called the \emph{order type} of the totally ordered set.  In other words, an order type is an equivalence class of totally ordered sets.
\end{defn}
}
}

\begin{note}
By Proposition 3.5, totally ordered sets of the same order type have the same cardinality.
\end{note}

\begin{notation}
The order type of $\mathbb{P}$ is denoted by $\omega$. Less commonly, $\pi$ denotes the order type of $\mathbb{Z}$ and $\eta$ denotes the order type of $\mathbb{Q}$.
\end{notation}

\begin{xbox}
\begin{example}
The order types $\omega$, $\pi$ and $\omega$ are distinct (even though $|\mathbb{P}| = |\mathbb{Z}| = |\mathbb{Q}| = \aleph_0$).
\end{example}
\end{xbox}

\begin{xbox}
\begin{example}
The set $\mathbb{R}$ does/does not have order type $\eta$.
\end{example}
\end{xbox}



\end{document}