5. Set Theory for the Natural Numbers - Cardinality

.

Set Theory for Working Mathematicians:

For the most part, working mathematicians take an informal point of view about Set Theory, as if the Tentative Definition presented earlier was not as problematic as in fact they know it to be. However, when proper care is exercised, this provides a more manageable framework for mathematical discourse than strict adherence to the formalism of Axiomatic Set Theory. This is the point of view that we will take for the remainder of this course. In the same vein, we will also use the terms such as "function" ("map"), "union", "intersection", "empty set", etc. with their usual informal meaning.

We begin the discussion of this "Informal Set Theory" by reviewing the Set Theory of finite Sets and MATH, the Natural numbers. The Natural numbers will provide a foundation for our general considerations about sets because many of the issues that we will have to consider appear as soon as one passes from the finite subsets of MATH to MATH itself, beginning with the measurement of the size of a Set. We use the following,

Notation:

We use the symbol $\QTR{Large}{n}$ to denote the subsets {1,2,....,n} of MATH

Mathematical Induction for the Natural Numbers : Suppose that we have a proposition MATHn$\QTR{Large}{)}$ on MATH. Suppose MATH1$\QTR{Large}{)}$ is true and MATHnMATHn+1$\QTR{Large}{)}$ is true for all n. Then, MATHn$\QTR{Large}{)}$ is true for all n.

Here is a link to Doctor Hilary Priestley's notes on Set Theory which he has been kind enough to make available for this course.

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 MATH , or there exists a 1 to 1 function MATH.

Proof:

This is a simple induction argument. Pick some x $\QTR{Large}{\in S}$ and define $\QTR{Large}{f(}$1$\QTR{Large}{)=}$x$\QTR{Large}{.}$ Suppose we have defined a 1 to 1 function MATH ,if $\QTR{Large}{f}$ is onto we are done, if not we can extend it to $\QTR{Large}{n+1}$ by defining

$\QTR{Large}{f(}$n+1$\QTR{Large}{)=\ }$y MATH.

5.2 Lemma:

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

a 1 to 1 function MATH.

Proof:

The proofs of the two statements are simple induction arguments.The first, is an induction on $\QTR{Large}{n}$ .

Clearly if 1 $\QTR{Large}{<}$ m there are no onto functions MATH. Now suppose we know this holds for n-1 Assume we have MATH onto with n $\QTR{Large}{<}$ m. By permuting $\QTR{Large}{m}$ we can assume $\QTR{Large}{f(}$n$\QTR{Large}{)=}$m.

Consider the inclusion MATH and the composition MATH

There are two cases to consider. Either $\QTR{Large}{fi}$ is onto or MATH is onto. (Why?)

In either case, this is not possible by induction. The proof of the second statement similar, beginning the induction with MATH.

Assignment: Complete the Proof. (To be turned in Feb. 2.)

Solution:

Either $\QTR{Large}{fi}$ is onto or MATH is onto because either there is some i $\QTR{Large}{<}$ n with $\QTR{Large}{f(}$i$\QTR{Large}{)=}$m in which case

MATH or MATH

To prove the second statement.

If 1 $\QTR{Large}{<}$ m there are no one to one functions MATH.

Next suppose there are no one to one functions MATH for i $\QTR{Large}{<}$ m and i $\QTR{Large}{<}$ n. Assume we are given a one to one function MATH with n $\QTR{Large}{<}$ m. By induction we can assume that $\QTR{Large}{g}$ is onto since if i MATH we can transpose i and n to give MATH one to one which contradicts the induction hypothesis.

Hence MATH is 1 to 1 and onto. Again, by a transposition, we can assume $\QTR{Large}{g(}$m$\QTR{Large}{)=}$n but again since is one to one

so is MATH ,again a contradiction.

5.3 Definition: A Set, $\QTR{Large}{S}$ is said to be "finite" if every function MATH 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 MATHand MATH , then $\QTR{Large}{f}$ and $\QTR{Large}{g}$ are also onto.

Proof:

$\QTR{Large}{fg}$ is a 1 to 1 self-map for a finite set, hence it is onto. So $\QTR{Large}{f}$ must be onto. Similarly since $\QTR{Large}{gf}$ is a 1 to 1 self-map, $\QTR{Large}{g}$ must be onto.

5.5 Theorem:

The following three statements are true:

  1. The subsets $\QTR{Large}{n}$ are finite.

  2. There exist functions MATH such that MATH is 1 to 1 but not onto and $\QTR{Large}{f}_{2}$is onto but not 1 to 1.

  3. Let $\QTR{Large}{S}$ be a finite set, then there exists an $\QTR{Large}{n}$ and a 1 to 1 onto function MATH

Proof:

1. Suppose that we have a 1 to 1 function MATH that is not onto. Again, by permuting the range we can assume that there does not exist an m$\QTR{Large}{\in n}$ with MATHm$)\QTR{Large}{=}$ n. Hence, we can assume we have a 1 to 1 function

MATH contradicting 5.2 . More or less the same argument works for $\QTR{Large}{f}$ onto but not 1 to 1.

2. Let MATHx$)$= x+1 and

3. Restating 5.1, either one can find some 1 to 1 onto function MATH ,or, by induction one can construct a

1 to 1 function MATH Letting $\QTR{Large}{f}_{1}$ and $\QTR{Large}{f}_{2}$ be the functions defined in 2. above, if $\QTR{Large}{f}$ is also onto then

use $\QTR{Large}{f}$ $\QTR{Large}{f}_{1}$ MATH or $\QTR{Large}{f}$ $\QTR{Large}{f}_{2}$ MATHto show that $\QTR{Large}{S}$ is not finite. If $\QTR{Large}{f}$ is not onto, the previous argument still works extending

$\QTR{Large}{f}$ $\QTR{Large}{f}_{1}$ MATH or $\QTR{Large}{f}$ $\QTR{Large}{f}_{2}$ MATH to all of $\QTR{Large}{S}$ by defining it to be the identity map on MATH.