\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}
\newcommand{\ord}{\ord}

\theoremstyle{plain}
\newtheorem{theorem}{Theorem}[section]
\newtheorem{cor}[theorem]{Corollary}
\newtheorem{prop}[theorem]{Proposition}
\newtheorem{lemma}[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}{3}
\section{Well-Ordered Sets}

\subsection{Well-Ordered Sets}

\begin{defn}
A partially ordered set $S$ is \emph{well-ordered} iff every nonempty subset of $S$ has a first element.
\end{defn}


\begin{example}
Both $\mathbb{P}$ and $\mathbb{P}^* \equiv \{1, 3, 5, \dots; 2, 4, 6, \dots\}$ are well-ordered; $\mathbb{P}^* \sim \mathbb{P}$ but $\mathbb{P}^* \not \simeq\mathbb{P}$.
\end{example}

\begin{xbox}
\begin{example}
$\emptyset? \: \mathbb{Z}? \:\mathbb{Q}? \: \mathbb{R}?$ (under the usual orders)  [Also, provide an example of a totally ordered set that has a first element but is not well-ordered.]
\end{example}
\end{xbox}


\begin{prop}
\hfill
\begin{enumerate}
\item A well-ordered set is totally ordered.
\item Every subset of a well-ordered set is well-ordered.
\item  If $A$ is well-ordered and $B \simeq A$, then $B$ is well-ordered.
\item If a totally ordered set is finite, then it is well-ordered.
\item If two finite, well-ordered sets are equipotent, then they are order-isomorphic.
\end{enumerate}
\end{prop}

\begin{xbox}
\begin{proof} (\emph{Hint for} (4).  Use induction on the cardinality of the finite set.  What is/are the base case/s? The inductive hypothesis is that every totally ordered set of cardinality $n$ is well-ordered.  Let $A$ be a totally ordered set of cardinality $n +1$.  Let $B$ be a nonempty subset of $A$; we must show that $B$ has a first element.  If $B$ is a proper subset, then......  If $B=A$, then let $b_0 \in B$ and consider $B\backslash \{b_0\}$.  Now what?

\emph{Hint for} (5).  This can also be done by induction. What is/are the base case/s? The inductive hypothesis is that any two well-ordered sets of cardinality $n$ are order-isomorphic.  Now let $A$ and $B$ be two well-ordered sets of cardinality $n+1$.)
\end{proof}
\end{xbox}


\begin{prop}
Let $\mathcal{A}=\{A_i \, | \, i\in I\}$ be a well-ordered collection of disjoint well-ordered sets.  Then $S = \bigcup \{A_i\, | \, i \in I\} $ with the concatenation order is well-ordered. 
\end{prop}


\begin{xbox}
\begin{proof}
We know  $S$ is totally ordered by the concatenation order.  Let $T$ be a nonempty subset of $S$. Let $J = \{i \in I \, | \, A_i \cap T \neq \emptyset \}$; that is, $J$ records {\it which} well-ordered sets in the collection contain an element of $T$. ...
\end{proof}
\end{xbox}

\begin{theorem}
Every element in a well-ordered set has an immediate successor, except the last element, if it has one.  This is not true of immediate predecessors.
\end{theorem}

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


\begin{defn}
An element $a$ of a well-ordered set $A$ is a  {\it limit element} iff $a$ is not the first element of $A$ and $a$ has no immediate predecessors.
\end{defn}

\begin{xbox}
\begin{example}
Give the limit element(s) of $\mathbb{P},\mathbb{P}^*$, if any, and give an example of a well-ordered set having countably infinitely many limit elements. [{\it Hint.} Let $A_p = \{n \in \mathbb{P} \mid p \text{ is the smallest prime such that } p \mid n \}$, for each prime $p \in \mathbb{P}$. ]\end{example}
\end{xbox}


\begin{xbox}
\begin{prop}
Let $f:A \to B$ be an order-isomorphism of well-ordered sets.  Then $a$ is a limit element of $A$ if and only if $f(a)$ is a limit element of $B$.
\end{prop}
\end{xbox}

\subsection{Initial Segments}


\begin{defn} 
Let $a$ be an element of a well-ordered set $A$. Then the \emph{initial segment of} $a$ \emph{in} $A$ is given by $s(a) = \{x \in A \, | \, x \prec a\}$.  When there is ambiguity about the ambient set $A$, we will denote this by $s_A(a)$. The set $ \{s(a) \, | \, a \in A \}$ of all initial segments in $A$, ordered by set inclusion, is denoted by $s(A)$.
\end{defn}


\begin{xbox}
\begin{example}
For any nonempty well-ordered set $A$, $\emptyset \in s(A)$.
\end{example}
\end{xbox}

\begin{xbox}
\begin{example}
In $\mathbb{P}^*$,  $s(2) = \dots$; $s(8) = \dots$.
\end{example}
\end{xbox}


\begin{note}
By Proposition 4.1(2), any initial segment in a well-ordered set is itself a well-ordered set (under the same order).
\end{note}


\begin{lemma}
Let $a,a^\prime$ be distinct elements of a well-ordered set $A$. 
Then $a \prec a^\prime$ if and only if $s_A(a)$ is an initial segment of $s_A(a^\prime)$.
\end{lemma}

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

\begin{lemma}
If $f:A \to B$ is an order-isomorphism, then for all $a \in A$, $s_A(a) \simeq  s_B \big( f(a) \big)$.
\end{lemma}

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

\begin{prop}\label{prop:s(A)woset}
For any well-ordered set $A$, $A \simeq s(A)$.
\end{prop}

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


\begin{note}
This proposition together with Proposition 4.1(3) implies that $s(A)$ is itself a well-ordered set.  Thus, any nonempty subset of $s(A)$ has a first element; that is, any nonempty collection of initial segments in $A$ has one initial segment that is contained in all of the others.
\end{note}

\begin{theorem}[Principle of Transfinite Induction]\label{wellordind}
 Let $S$ be a subset of a well-ordered set $A$ with the property that for all $a \in A$, $s(a) \subseteq S$ implies $a \in S$.  Then $S = A$.
 \end{theorem}

\begin{xbox}
\begin{proof}
Let $T = A \backslash S$.  If $T \neq \emptyset$, then $T$ must have a first element $t_0$. (\emph{Hint.}  Show that $t_0$ must be in both $T$ and $S$, a contradiction.)
\end{proof}
\end{xbox}

The next result shows that the familiar Principle of Mathematical Induction is just the Principle of Transfinite Induction applied to the familiar well-ordered set $\mathbb{P}$.


\begin{cor}%[Principle of Mathematical Induction on $\mathbb{P}$]
Let $S$ be a subset of $\mathbb{P}$ satisfying (i) $1 \in S$ and (ii) for all $n \in \mathbb{P}$, if $n \in S$ then $n+1 \in S$.  Then $S = \mathbb{P}$.
\end{cor}

\begin{xbox}
\begin{proof}

[Show that any subset $S \subseteq \mathbb{P}$ satisfying (i) and (ii) satisfies the subset property in Theorem \ref{wellordind}.]
\end{proof}
\end{xbox}

\subsection{Comparison of Well-Ordered Sets}
\begin{example}
The function $f:\mathbb{P} \to \mathbb{E}$ given by $f(n)=2n$ is an order-isomorphism of $\mathbb{P}$ onto a subset of itself.  Observe that for all $n \in \mathbb{P}$, $n \preceq f(n)$ (where $\preceq$ denotes the usual order on $\mathbb{P}$).
\end{example}


\begin{theorem}
Let $A$ be a well-ordered set, with $B \subseteq A$ and let $f:A\to B$ be an order-isomorphism.  Then for all $a \in A$, $a \preceq f(a)$.
\end{theorem}

\begin{xbox}
\begin{proof}
Let $C = \{a \in A \, | \, f(a) \prec a \}$ and assume $C \neq \emptyset$. (\emph{Hint.} Show that if $c \in C$, then $f(c) \in C$.  Why does this lead to a contradiction?)
\end{proof}
\end{xbox}


\begin{cor}
If $A$ and $B$ are order-isomorphic well-ordered sets, then there is a unique order-isomorphism from $A$ to $B$.
\end{cor}

\begin{xbox}
\begin{proof}
Let $f, g:A \to B$ be distinct order-isomorphisms.  Then by definition, there exists $a \in A$ such that $f(a) \neq g(a)$.  Without loss of generality, assume $f(a) \prec g(a)$. (\emph{Hint.}  Consider the order-isomorphism $(g^{-1}\circ f):A \to A$.)
\end{proof}
\end{xbox}

\begin{xbox}
\begin{note}  This corollary does not apply in general to order-isomorphic partially ordered sets.
\end{note}
\end{xbox}
  
\begin{cor}
A well-ordered set cannot be order-isomorphic to one of its initial segments.
\end{cor}

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

\begin{cor}
Two distinct initial segments of a well-ordered set cannot be order-isomorphic.
\end{cor}

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

Compare the next theorem to Theorem \ref{wellordind}.

\begin{theorem}
Let $S$ be a subset of a well-ordered set $A$ with the property that for all $a \in A$, $a \in S$  implies $s(a) \subseteq S$.  Then either $S = A$ or $S$ is an initial segment of $A$.
\end{theorem}

\begin{xbox}
\begin{proof}  Assume $S \neq A$ and let $T = A \backslash S$.  Since $T$ is a nonempty subset of a well-ordered set, it has a first element, call it $t_0$. [Now show that $S=s(t_0)$.]
\end{proof}
\end{xbox}


\begin{prop}
Let $A$ and $B$ be well-ordered sets that have a pair of order-isomorphic initial segments; that is, there exist $a \in A, \: b \in B$ such that $s_A(a) \simeq s_B(b)$.
\begin{enumerate}
\item For all $b \neq b^\prime \in B$, $s_A(a) \not \simeq s_B(b^\prime)$.
\item For all $a^\prime \prec a$, there exists $b^\prime \in B$ such that $b^\prime \prec b$ and  $s_A(a^\prime) \simeq s_B(b^\prime)$; that is, every initial segment of $s_A(a)$ is order-isomorphic to an initial segment of $s_B(b)$. 
\end{enumerate}
\end{prop}

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

\begin{prop}\label{segsets}
Let $A$ and $B$ be well-ordered sets, and let $S = \{a \in A \, | \, s_A(a) \simeq s_B(b) \text { for some } b\in B\}$.  
\begin{enumerate}
\item Either $S = A$ or $S$ is an initial segment of $A$.  
\item If $T  = \{b \in B \, | \, s_B(b) \simeq s_A(a) \text { for some } a\in A\}$, then $S \simeq T$.
\end{enumerate}
\end{prop}

\begin{xbox}
\begin{proof}
(\emph{Hint.} For (1), use the previous two results.  For (2), define $f:S \to T$ as follows.  For each $a \in S$, by definition $s(a) \simeq s(b)$ for some $b \in B$.  Let $f(a)$ equal \emph{that} $b$.  More precisely, $f(a)=b \iff s(a) \simeq s(b)$.  By Proposition 4.15(1), this definition is not ambiguous, so $f$ really is a function.  We must now show that it is an order-isomorphism.)
\end{proof}
\end{xbox}

\begin{xbox}
\begin{note}
If $A$ and $B$ are nonempty, then $S$ and $T$ (as defined in in Proposition 4.16) are nonempty.
\end{note}
\end{xbox}

\begin{defn}
Let $A$ and $B$ be well-ordered sets.  Then $A$ \emph{is shorter than} $B$ iff  $A$ is order-isomorphic to an initial segment of $B$; that is, iff $A \simeq s_B(b)$ for some $b \in B$.
\end{defn}

\begin{notation}
$A \lessdot B$.
\end{notation}

\begin{xbox}
\begin{example}
$\mathbb{P} \lessdot \mathbb{P}^*$.
\end{example}
\end{xbox}

\begin{prop}\label{prop:toset}
Let $A, \, B$ and $C$ be well-ordered sets.  If $A \lessdot B$ and $B \lessdot C$, then $A \lessdot C$.
\end{prop}

\begin{xbox}
\begin{proof}  By assumption, there exist order-isomorphisms $f:A \to s_B(b)$ and $g:B \to s_C(c)$, for some $b \in B$ and some $c \in C$.  \end{proof}
\end{xbox}

\begin{figure}[hbt] 
   \centering
   \includegraphics[width=2.5in]{segment-trans.pdf} 
\end{figure}



\begin{cor}
The relation $\lessdot$ is a quasi-order on any collection of well-ordered sets.
\end{cor}

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


\begin{theorem}
If $A$ and $B$ are well-ordered sets, then either they are order-isomorphic or one is shorter than the other.
\end{theorem}

\begin{xbox}
\begin{proof}
Let $S$ and $T$ be defined as in Proposition \ref{segsets}.  Then we know $S \simeq T$, and that either $S=A$ or $S$ is an initial segment of $A$, and that either $T=B$ or $T$ is an initial segment of $B$.   (\emph{Hint.} Consider all possible cases.  When assuming $S=s_A(a)$ and $T=s_B(b)$, consider whether  $a \in S = s_A(a)$.)
\end{proof}
\end{xbox}


\begin{theorem}
Let $\mathcal{A}$ be a nonempty collection of pairwise non-order-isomorphic well-ordered sets.  Then there exists some $A_0 \in \mathcal{A}$ that is shorter than every other well-ordered set in $\mathcal{A}$.
\end{theorem}

\begin{xbox}
\begin{proof}
Since $\mathcal{A}$ is nonempty, we can fix some $B \in \mathcal{A}$; let $\mathcal{B} = \{ A \in \mathcal{A} \, | \, A \lessdot B \}$.  If $\mathcal{B} = \emptyset$, then let $A_0 = B$ and we are done. [Why?]   If $\mathcal{B} \neq \emptyset$ , then each $A \in \mathcal{B}$ is order-isomorphic to a unique initial segment $s_B(b)$ of $B$. This can be used to define  $f: \mathcal{B} \to B$.....[ Don't forget to consider $C \in \mathcal{A} \backslash \mathcal{B}$.])
\end{proof}
\end{xbox}


\end{document}