6. Set Theory for the Natural Numbers -Order

Assignment: Study the material in 1.2 of the text.

Measurement by "Ordinality"

6.1 Definition:

A Set, $\QTR{Large}{S}$ is said to be partially ordered or a poset if there is a binary relation " $\QTR{Large}{\leq }$ " defined on $\QTR{Large}{S}$ satisfying the following three properties

For all
For all and
For all and It is (totally)ordered if it also satifies
For all or

6.2 Definition:

Given a partially ordered set $\QTR{Large}{S}$ , we call a chain of $\QTR{Large}{S}$ if it is totally ordered.

6.3 Lemma:

Let . It is a simple matter to check that any a partial/total order on $\QTR{Large}{S}$ , restricts to a partial/total order on $\QTR{Large}{T}$ .

Proof: Verify for yourself.

6.4 Definition:

Given partially ordered sets and $\QTR{Large}{C}$ , a one to one onto map is called an order isomorphism if

for all

6.4.1 Lemma:Let be ordered and be a poset. Suppose we are given a one to one onto map such that for all then:

1. is ordered

2. is an order isomorphism.

3.If is Well Ordered so is

Proof:

1. Let and be such that and

Since is ordered or and thus or

2. We need only show that for all . Since is ordered or

But and by hypothesis so and, $\QTR{Large}{f\ }$ since is one to one, $\QTR{Large}{a=b.}$

Thus we have

3. Let . Since is Well Ordered let $\QTR{Large}{l}$ be the least element of

Check that $\QTR{Large}{f(l)}$ is the least element of $\QTR{Large}{A.}$

Examples:

and are all ordered by the usual binary relations.
Let . Let $\QTR{Large}{(}$ m,nr,s $\QTR{Large}{)}$ iff m $\QTR{Large}{\leq }$ r and n $\QTR{Large}{\leq }$ s. This is partial ordering but not a total ordering. Compare $\QTR{Large}{(}$ 1,2 $\QTR{Large}{)}$ and $\QTR{Large}{(}$ 2,1 $\QTR{Large}{)}$
Let be the subset $\QTR{Large}{\{}$ 1,n $\QTR{Large}{\}}$ all n. $\QTR{Large}{C}$ is a chain.
Let and 2,4,6,....,2n... $\QTR{Large}{\}}$ then $\QTR{Large}{f(}$ n $\QTR{Large}{)=}$ 2n is an order isomorphism.

6.5 Definition:

Let $\QTR{Large}{S}$ be Ordered. Let Define, , called the segment defined by $\QTR{Large}{a}$ as follows.

If is finite it will be convenient to use the notation for the number of member in $\QTR{Large}{S(a)}$ .

Example: In with the usual ordering $\QTR{Large}{S(}$ n $\QTR{Large}{)=n-1}$ and $\QTR{Large}{|S(}$ nn-1.

Well Ordered Sets

6.6 Definition: A Set, $\QTR{Large}{S}$ is said to be Well Ordered (WO) if it is Ordered and every subset has a least member. That is there exists an such that for all . Note that by 6.1.2. above, we know that $\QTR{Large}{l}$ is unique.

It is enough to assume that $\QTR{Large}{S}$ is partially ordered and every subset has a least element?

Any subset of a Well Ordered Set is Well Ordered, using the same order.Why?

Examples:

Any Ordering of a finite set is a Well Ordering.

Assignment: Due Feb. 9: Show that any two orderings of a given finite set are order isomorphic.

is Well Ordered by the usual binary relation. Absent any qualifications, when we use the symbol this is the order that is implied.
Let 0,1,2,3,4,5,..n,... $\QTR{Large}{\}}$ with the usual order. Then $\QTR{Large}{g:}$ defined by the
formula $\QTR{Large}{g(}$ x $\QTR{Large}{)=\ }$

x $\QTR{Large}{+\ }$ 1 is an order isomorphism.This is what we "mean" when we say the Natural Numbers can be defined either as or .
and are not Well Ordered by the usual binary relation.

6.7 Theorem:

Suppose that we have a proposition n $\QTR{Large}{)}$ .

Suppose 1 $\QTR{Large}{)}$ is true

and

for all n, nn $\QTR{Large}{+}$ 1 $\QTR{Large}{)}$ is true .

Then,

for all nn $\QTR{Large}{)}$ is true .

Proof:

Let be the set of all n for which n $\QTR{Large}{)}$ is not true. Suppose $\QTR{Large}{B}$ were not empty. Then it has a least element, l . Since 1 $\QTR{Large}{)}$ is true, l $\QTR{Large}{>\ }$ 1. We know that l $\QTR{Large}{-\ }$ 1 $\QTR{Large}{)}$ is true. But l $\QTR{Large}{-\ }$ 1l $\QTR{Large}{).}$ Therefore l $\QTR{Large}{)}$ is true. Hence $\QTR{Large}{B}$ is empty.

6.8 Theorem:

a. Given , for any , $\QTR{Large}{S(a)}$ is finite.

Moreover,

b. either $\QTR{Large}{S\ }$ is finite or for any integer n $\QTR{Large}{\geq }$ 0 we can find a unique with n.

Hence.

c. There exists an order isomorphism

Proof:

a. Is immediate from the observation that since , $\QTR{Large}{S(a)}$ is a subset of the segment of $\QTR{Large}{a}$ in , which is finite.

b. Is a simple induction argument. Let to be the least element of $\QTR{Large}{S.}$

Since we have 0 . Moreover uniqueness follows from the fact that for any and

Hence 1.

Assume that for 0 $\QTR{Large}{\leq }$ i n we can find a unique with i.

Since by assumption $\QTR{Large}{S}$ is not finite, let be the least element of

We need to verify that

hence n+1.

First note that , since if then

On the other hand if

and then . thus

Again uniqueness follow from the fact that since for any

and we conclude that

we can now apply the principal of mathematical induction.

c. follows from b.

First define by the formula $\QTR{Large}{h(}$ n

Clearly $\QTR{Large}{h}$ is one to one. If it were not onto let and

Suppose m. Then contradicting the uniqueness of

Finally, let $\QTR{Large}{f=hg}$ where is defined by the formula $\QTR{Large}{h(}$ nn-1

6.9 Theorem:

Let be an order isomorphism. . Then

1. for all

2. if (or ) is Well Ordered

so is (or )

Assignment: Due Feb. 9: Prove this

Solution: See 6.4.1 above.

Example:

Let where .Define an ordering on the as follows: $\QTR{Large}{=}$ $\QTR{Large}{\leq }$ ,the usual ordering, on and for all n we have $\$ n .

Assignment: Due Feb. 9: Show that

1. There exist a one to one onto set map $\QTR{Large}{.}$

2. is a Well Ordering

3. is not order isomorphic to with the usual ordering.

(Hint:) Use 6.8 and 6.9 to prove 3.

Solution: We give the details for 3.

Let be an order isomorphism. Suppose $\QTR{Large}{f(}$ n By 6.9.3 $\QTR{Large}{f(S(}$ n ,which is not possible since $\QTR{Large}{S(}$ n $\QTR{Large}{)}$ contains a finite number of elements and does not.

Finally, we gather results above to state the following theorem, which characterizes Set Theory for the Natural Numbers.

6.10 Theorem:

For any

1. There exists an n and an order isomorphism

2. There exists an order isomorphism

Examples:

While the set of fractions greater than 0, is not well ordered by the usual ordering, it is not hard to put a non-standard well ordering on .

Referring back to Page 0, consider the function 23Check that this is 1 to 1, hence inherits a well ordering from . This is certainly not the usual ordering since 12 and 108. hence 2 $\QTR{Large}{\leq }$ (). Note as well that inherits a form of mathematical induction from this well ordering albeit not a particularly useful one.