12. Well Ordered Sets

12.1 Theorem:

Let $\QTR{Large}{A}$ be Well Ordered

If n then $\QTR{Large}{A}$ is order isomorphic to $\QTR{Large}{n}$ .

or
$\QTR{Large}{A\ }$ is order isomorphic to

or
For some ,is order isomorphic to .

Proof:

By induction, if 1 then the Theorem is immediate. Suppose the result holds for n-1. Let be the top element. The is an order isomorphism Extend $\QTR{Large}{f}$ to $\QTR{Large}{n}$ by setting $\QTR{Large}{f(}$ n $\QTR{Large}{)=t}$ .
Again, by induction, one shows that for n there a unique such thatn. Hence by 1. one has order isomorphisms . Checking that we have an order isomorphism . Either .

or
where $\QTR{Large}{a\ }$ is the least element of

In more generality.

12.2 Theorem:

Let $\QTR{Large}{A}$ be Well Ordered then the only self-order isomorphism is the identity map.

Proof:

Suppose $\QTR{Large}{f}$ is not the identity map. Let $\QTR{Large}{s}$ be the least member of $\QTR{Large}{A}$ such that .

The segment mapping formula tell us that

but by assumption hence and thus by 11.1.1

12.2 Corollary:

Let $\QTR{Large}{A}$ and $\QTR{Large}{B}$ be Well Ordered and order isomorphic then the order isomorphism is unique.

Let be two order isomorphisms. is a self-order isomorphism, hence the identity map, . Thus .

12.3 Theorem:

Let $\QTR{Large}{A}$ be Well Ordered and let , $\$ there is no order isomorphism .

Proof:

Suppose there was an order isomorphism

Since there exists some $\QTR{Large}{s<a}$ such that In particular

Let . Since $\QTR{Large}{A[a]}$ is Well Ordered let

Thus $\QTR{Large}{[l]}$ is the identity map. Restated $\QTR{Large}{[l].}$ But

. Thus , contradicting the definition of $\QTR{Large}{l}$ .

12.4 Lemma:

Let $\QTR{Large}{A}$ be Well Ordered. Let be an Ideal Cut, then $\QTR{Large}{I=A}$ or for some , ,

Proof:

If , let

12.5 Theorem:

Let $\QTR{Large}{A\ }$ and $\QTR{Large}{B}$ be Well Ordered then

$\QTR{Large}{A}$ is order isomorphic to a segment of $\QTR{Large}{B}$ .

or
$\QTR{Large}{B\ }$ is order isomorphic to a segment of $\QTR{Large}{A}$ .

or
$\QTR{Large}{A}$ and $\QTR{Large}{\ B\ }$ are order isomorphic.

Proof:

Notes and Observations

Consider the Set of triples where and are Ideal Cuts and, is an order isomorphism.

We let if

Exercise(due Wed. March 29) Show that this is an ordered Set. (Hint: use 12.2).

Assuming this, Consider the triple MATH where . Again, one checks that this is an order isomorphism.

Clearly the triple is maximal with respect to the three bullets. In particular, and MATH are Ideal Cuts (11.1.2). Thus by 12.4 , , MATH or both are segments and we can then extend $\QTR{Large}{f,}$ a contradiction.

On the next Page we will want a "constructive" version of the material just presented. In particular, we will extract Well Ordered subsets of posets. Here are the details.

We are given a poset $\QTR{Large}{)}$ . We restrict attention to , the Well Ordered subsets.

Definition 12.6:

A subset is called "complete" if and implies

. That is if a Well Ordered subset is in so are all its segments. Clearly itself is complete.

Note: Implicit in the definition is the assumption that is Well Ordered, "vacuously".

If you are uncomfortable with this assumption, just define "complete" on .

Note: One also finds these subsets called "good" or "special."

Theorem 12.7:

Fix Let be the set of Well Ordered subsets with least element Let be complete and such that there exists a function with the property that for all and then MATH .

Proof:

One needs to show that to show that if and are in then , for some , or for some .

As we noted before, in that case, MATH is Well Ordered

Let be the set of common Ideal Cuts of and . From the hypothesis

is not empty. Hence is common Ideal Cut of and . Hence or or both, or $\QTR{Large}{I}$ is a segment of both. But, suppose

there exists and such that .

But a contradiction since then would be a common Ideal Cut.

Examples:

1. For , let 2. Let $\QTR{Large}{\{}$ finite sequences of all even numbers beginning with 2 and ending with 2n for some n $\QTR{Large}{\}.}$ Clearly is complete. Let $\QTR{Large}{F}$ be any finite set. Define Exercise Check that satisfies the hypothesis of 12.7 for Compute $\QTR{Large}{U.}$

2. where iff and . Let $\QTR{Large}{F}$ be a chain. Define Exercise Find the appropriate Compute $\QTR{Large}{U.}$

Ordinal Arithmetic

In discussing ordinal arithmetic it will be helpful to use a more precise notation for Well Ordered Sets.

12.8 Definition: Let $\QTR{Large}{)}$ and $\QTR{Large}{)}$ be two Well Ordered sets with , . We define a Well Ordering $\QTR{Large}{)}$ by the following three properties.

for and .

One checks

12.9 Theorem:

Let be well ordered with n and m, then, under the appropriate assumptions of disjointness, is order isomorphic to .
Let be order isomorphic to , be order isomorphic to , , and , then is order isomorphic to

12.10 Observation:

As we have seen, in general, is not order isomorphic to

Look at and

12.11 Definition: Let $\QTR{Large}{)}$ and $\QTR{Large}{)}$ be two Well Ordered sets. We define a Well Ordering $\QTR{Large}{)}$ using "alphabetic order" as follows:

$\QTR{Large}{(s,t}$ $\QTR{Large}{)}$

and if $\QTR{Large}{)}$
$\QTR{Large}{\ }$ if $\QTR{Large}{)}$

Exercise: Check that this is a Well Order (Due Wed. March 29)

12.12 Observation:

In general, is not order isomorphic to

Look at and

Exercise: How about $\QTR{Large}{(}$

(Due Wed. March 29)

Solution:

The strategy is to write down the two definitions of order and observe that they are equivalent.

$\QTR{Large}{(}$

if

and if $\QTR{Large}{)}$

$\QTR{Large}{\ }$ if $\QTR{Large}{)}$

if

and if $\QTR{Large}{)}$

if

and if and

if $\QTR{Large}{)}$

$\QTR{Large}{\ }$ if

and if

if

if

and if

if

and if $\QTR{Large}{)}$

$\QTR{Large}{\ }$ if $\QTR{Large}{)}$