Exercise 10.8

Question

\begin{enumerate}[label=(\alph*)]
\item Let $A_1$ and $A_2$ be disjoint sets, well-ordered by $<_1$ and $<_2$, respectively.
Define an order relation on $A_1 \cup A_2$ by letting $a < b$ either if $a,b \in A_1$ and $a <_1 b$, or if $a,b \in A_2$ and $a <_2 b$, or if $a \in A_1$ and $b \in A_2$.
Show that this is a well-ordering.
\item Generalize (a) to an arbitrary family of disjoint well-ordered sets, indexed by a well-ordered set.
\end{enumerate}

Dan Whitman · Accepted Answer

\def\W{\Omega}
\def\a{\alpha}
\def\b{\beta}
\def\g{\gamma}
\def\va{\mathbf{a}}
\def\vb{\mathbf{b}}

ewcommand\seqinf[1]{\left(#1_1, #1_2, \ldotsight)}

ewcommand\seqfin[2]{\left(#1_1, \ldots, #1_{#2}ight)}

(a)
\begin{proof}
It is easy but tedious to show that $<$ is actually an order on $A_1 \cup A_2$, so we shall skip that proof and jump straight to the proof that it is a well-ordering.

So consider any nonempty subset $A$ of $A_1 \cup A_2$.

Case: $A_1 \cap A 
eq \varnothing$.
Then clearly $A_1 \cap A$ is a nonempty subset of $A_1$ so that it has a smallest element $a$ according to $<_1$ since it is a well-ordering.
We then claim that $a$ is the smallest element of $A$ according to $<$.
So consider any $x \in A$ so that clearly also $x \in A_1 \cup A_2$.
Hence $x \in A_1$ or $x \in A_2$.
If $x \in A_1$ then obviously $x \in A_1 \cap A$ so that $a \leq_1 x$ since $a$ is the smallest element of $A_1 \cap A$.
Then also $a \leq x$ by definition since $a$ and $x$ are both in $A_1$.
On the other hand, if $x \in A_2$ then we again have that $a < x$ since $a \in A_1$ and $x \in A_2$.
Therefore $a \leq x$ no matter what so that $a$ is the smallest element of $A$ since $x$ was arbitrary.

Case: $A_1 \cap A = \varnothing$.
Then it has to be that $A_2 \cap A 
eq \varnothing$ since $A$ is nonempty and $A = A_1 \cup A_2$.
Thus $A_2 \cap A$ is a nonempty subset of $A_2$ so that it has a smallest element $a$ by $<_2$ since it is a well-ordering.
We claim that $a$ is the smallest element of $A$.
So consider any $x \in A$.
It has to be that $x \in A_2$ since $A_1 \cap A$ is empty and $A = A_1 \cup A_2$.
Therefore $x \in A_2 \cap A$ so that $a \leq_2 x$ since $a$ is the smallest element of $A_2 \cap A$.
Then, by definition, $a \leq x$ since both $a$ and $x$ are elements of $A_2$.
This shows that $a$ is the smallest element of $A$ since $x$ was arbitrary.

In either case, we have shown that $A$ has a smallest element so that $<$ is a well-ordering of $A_1 \cup A_2$ since $A$ was arbitrary.
\end{proof}

Note that well-ordering a union of two well-ordered sets like this is analogous to the addition of two ordinal numbers.
In particular if $A_1$ has order type $\a_1$ and $A_1$ has order type $\a_2$ where $\a_1$ and $\a_2$ are an ordinal numbers, then $A_1 \cup A_2$ with the above well-ordering has order type $\a_1 + \a_2$.

(b) Suppose that $J$ is well-ordered by $<_J$ and $\left\{A_\aight\}_{\a \in J}$ is a collection of well-ordered sets where $A_\a$ is well-ordered by $<_\a$ for each $\a \in J$.
Now define an order $<$ on $A = \bigcup_{\a \in J} A_\a$ as follows.
For any $x$ and $y$ in $A$ there are clearly $\a$ and $\b$ in $J$  where $x \in A_\a$ and $y \in A_\b$, noting that $\a$ and $\b$ are unique since the collection is mutually disjoint.
So set $x < y$ if and only if either $\a = \b$ and $x <_\a y$, or else $\a <_J \b$, noting that these are clearly mutually exclusive.
We then claim that $<$ is a well-ordering of $A$.
\begin{proof}
Let $B$ be any nonempty subset of $A$ and $I$ be the set of $\a \in J$ such that there is an $x \in B$ where $x \in A_\a$.
Now, since $B$ is nonempty, there is a $z \in B$.
Since $B \subset A = \bigcup_{\a \in J} A_\a$, there is an $\g \in J$ where $z \in A_\g$.
Then clearly $\g \in I$ so that $I$ is a nonempty subset of $J$.
Then $I$ has a smallest element $\a$ since it is well-ordered by $<_J$.
By the definition of $I$ there is a $w \in B$ where $w \in A_\a$.
Then clearly $w \in A_\a \cap B$ so that it is a nonempty subset of $A_\a$.
It then follows that $A_\a \cap B$ has a smallest element $a$ according to $<_\a$ since it is a well-ordering on $A_\a$.
We claim that $a$ is the smallest element of $B$ by $<$.

So consider any $x \in B$ so that there is a $\b \in J$ where $x \in A_\b$ since $B \subset A$.

Case: $\b = \a$.
Then both $a$ and $x$ are in $A_\a \cap B = A_\b \cap B$ so that $a \leq_\a b$ since $a$ is the smallest element of $A_\a \cap B$.
It then follows from the definition of $<$ that $a \leq x$.

Case: $\b 
eq \a$.
Clearly then $\b \in I$ so that $\a \leq_J \b$ since $\a$ is the smallest element of $J$.
Since we know that $\b 
eq \a$ it must be that $\a <_J \b$.
From this, it follows that $a < x$ by definition.

Hence in either case it is true that $a \leq x$, which shows that $a$ is the smallest element of $B$.
Since $B$ was an arbitrary nonempty subset of $A$, this shows that $A$ is well-ordered by $<$.
\end{proof}

Exercise 10.8

Answers

Comments

Exercise 10.8

Answers

Comments

Add answer