Interlude, a Natural Numbers Cheat Sheet

.

Measurement by Cardinality:

5.1 Lemma:

Let $\QTR{Large}{S}$ be a given set. Either, for some n there exists a 1 to 1 and onto function , or there exists a 1 to 1 function .

5.2 Lemma:

Let n $\QTR{Large}{<}$ m. There does not exist an onto function . There does not exist

a 1 to 1 function .

5.3 Definition: A Set, $\QTR{Large}{S}$ is said to be "finite" if every function is onto iff it is 1 to 1.

5.4 Theorem:

Suppose I have two finite sets $\QTR{Large}{S}_{1}$ and $\QTR{Large}{S}_{2}$ and 1 to 1 maps and , then $\QTR{Large}{f}$ and $\QTR{Large}{g}$ are also onto.

5.5 Theorem:

The following three statements are true:

The subsets $\QTR{Large}{n}$ are finite.
There exist functions such that is 1 to 1 but not onto and $\QTR{Large}{f}_{2}$ is onto but not 1 to 1.
Let $\QTR{Large}{S}$ be a finite set, then there exists an $\QTR{Large}{n}$ and a 1 to 1 onto function

Measurement by "Ordinality"

Well Ordered Sets

6.8 Theorem:

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

Moreover,

b. either 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

6.9 Theorem:

Let be an order isomorphism. . Then

1. for all

Suppose (or ) is Well Ordered

2. so is (or )

6.10 Theorem:

For any

1. There exists an n such that $\QTR{Large}{S}$ and an order isomorphism

or

2. There exists an order isomorphism

More Examples , Calculations, and Observations:

Define $\QTR{Large}{f:}$ by the formula $\QTR{Large}{f(}$ n $\QTR{Large}{)=(}$ -1r $\QTR{Large}{)}$

where n $\QTR{Large}{=\ }$ 2 MATH r, (division by 2 with remainder r ). $\QTR{Large}{f}$ is one to one and onto.

Check 00

$\QTR{Large}{f(}$ 1 $\QTR{Large}{)=\ }$ -1

$\QTR{Large}{f(}$ 21

$\QTR{Large}{f(}$ 3 $\QTR{Large}{)=\ }$ -2

$\QTR{Large}{f(}$ 42

and so on.

Define by the formulam,n $\QTR{Large}{))=}$ 23 again, $\QTR{Large}{\ g}$ is one to one. Letting

, we can apply 6.10 to find an order isomorphism giving which is one to one and onto. It is not

an order isomorphism!

One can actually get an explicit map

We want to compare the nature of the previous two calculations.
Define a binary relation on as follows

m,nm',n' $\QTR{Large}{)}$ iff (m $\QTR{Large}{<\ }$ m') or (if (m $\QTR{Large}{=\ }$ m') then (n n'))

Check that this is an Order. It is called "Alphabetic Order"

Here is a picture of Alphabetic Order.

It is also a Well Order!

Proof:

We use the projection where m,n $\QTR{Large}{))=\ }$ m.

Given a non-empty , consider and let $\QTR{Large}{l}$ be its least

member. Check that every member of is strictly less than every member

of $\QTR{Large}{S-L}$ since $\QTR{Large}{(}$ m,nm',n' $\QTR{Large}{)}$ if m $\QTR{Large}{<\ }$ m'

We now use where m,n $\QTR{Large}{))=\ }$ n to choose the least

member of Note that is one to one on $\QTR{Large}{L}$ .