9. Cardinal Numbers

The size of sets:

We want to extend the notion of size of finite sets that is provided by the natural numbers so that we can compare the "size" of any two sets. It is worth noting that the following definition requires some reassurance that we are on mathematically firm ground since we are certainly on the edge of Russell territory. We will discuss this further when we consider alternatives to ZF set theory.

9.1 Definitions:

  1. Let $\QTR{Large}{o()}$ be the equivalence relation on the "class" of all set defined by setting MATH if there exists a 1 to 1 onto map MATH. This is the books notation.

  2. We define a second equivalence relation MATH on the class of all set by setting MATH if there exists a 1 to 1 map MATH and a 1 to 1 map MATH.

  3. Finally, we write MATH if the exist a 1 to 1 map MATH .

Exercise: Check that 1. and 2. are equivalence relations. For reference, you need to verify that

MATH

MATH MATH

and

MATHand MATH MATH

Observation:

For MATH and its subsets, we have essentially shown, that MATH iff MATH

We used this to also show that MATHNote that if we only wanted to show that

MATH, it would have sufficed to present two one to one maps,

MATH defined by $\QTR{Large}{f((}$m,n$\QTR{Large}{))=}$2MATH3$^{\text{n}}$

and

MATHdefined by $\QTR{Large}{g(}$m$\QTR{Large}{)=(}$m,1$\QTR{Large}{)}$

Goals:

  1. We show that, in general, for any pair of sets MATH iff MATH

  2. We also will show that for any pair of sets, MATH or MATH

First, the following useful theorem.

9.2 The Tarski Fixed Point Theorem.

Let $\QTR{Large}{S}$ be a partially ordered set in which every non-empty sub-set has a least upper bound and a greatest lower bound. If MATH is order-preserving, that is

MATH implies MATH, then $\QTR{Large}{f}$ has a fixed point ( MATH ).

Proof.

Before proceeding with the proof. We look at two examples:

Examples:

1. MATH - The map $\QTR{Large}{f(}$n$\QTR{Large}{)=}$ n+1 has no fixed point. On the other hand, MATH ,itself a subset, does not have a least upper bound.

2. MATH $\ $- where,again,MATH MATH, MATH and MATH $\QTR{Large}{=}$ $\QTR{Large}{\leq }$ ,the usual ordering, on MATH and n MATH MATHfor all nMATH

First, note that MATH $\ $satifies the hypothesis of Tarski. To see this let MATH. If MATH then it is the least upper bound (and the top element). If MATH and $\QTR{Large}{A}$ is finite then it, as a finite subset of MATH, has a least upper bound( and again a top element). Finally, if MATH and $\QTR{Large}{A}$ is not finite, MATH is the least upper bound, in fact the only upper bound( but not the top element)

Next, to see that the conclusion of Tarski holds, let MATH be order preserving. If MATH MATH we have our fixed point. If MATH $\QTR{Large}{=\ }$n for some n then MATH MATH,since $\QTR{Large}{f}$ is assumed to be order preserving.

Finally, an induction argument shows that, in general, any order preserving map MATH has a fixed point.



Let MATH. Then by definition, MATH. Let MATH Since MATH, $\QTR{Large}{A}$ is

non-empty. Hence MATH exists. For any MATH we have MATH

and MATH, so MATH is an upper bound for $\QTR{Large}{A}$ . Thus MATH and MATH

But, in general, if MATHthen MATHbecause

MATH implies MATH . Thus MATH and MATH

Finally, we conclude that MATH.

9.3 Theorem(Schroder-Bernstein)

For any pair of sets MATH iff MATH

Proof.

By hypothesis, there exist one-to-one functions

MATH and MATH. We apply the Fixed Point Lemma to the poset MATH and the function MATH where $\QTR{Large}{E}$ MATH $\QTR{Large}{A}$ . Here the exponent $\QTR{Large}{C}$ signifies Set complement.

Note that $\QTR{Large}{i}$ is order-preserving

MATH

Hence, by the Tarski Fixed Point Theorem, there is a set MATH such that MATH

Specifically ,MATH MATH

We can now define a 1 to 1 onto map MATH by MATH , MATH and MATH for MATH.

Two Computations:

9.3.1 Lemma: In the setting of the Proof of 9.3 MATH , the union being disjoint.

Proof.

That the union is disjoint simply follows from the fact that MATH. In addition, since $\QTR{Large}{g}$ is one to one we also can write

MATH , with MATH . Intersecting both sides with MATH gives

MATH

But MATH

and thus

MATH

or, taking the complements of both sides

MATH

9.3.2 Theorem:

In the setting of the Proof of 9.3, then MATH MATH $\QTR{Large}{)}$,

where MATHMoreover the union is a disjoint union of non empty sets.

Proof.

From 9.3.1

MATH

MATH

That the sets are disjoint follows from the fact that $\QTR{Large}{f}$ and $\QTR{Large}{g}$, hence $\QTR{Large}{h}$ ,are one to one

More Computations:

The hierarchy of cardinals:

We are now about ready to move to a more general discussion of set theory and cardinals. We begin by noting that a more general discussion is appropriate by showing that there are other cardinalities to be considered other than that of MATH and its finite subsets .

9.4 Theorem:

For any set $\QTR{Large}{S}$ ,there is no onto map MATH.

Proof A:( yet another diagonal argument. This is just Russell's argument in a non-paradoxical setting)

Let MATH. Since $\QTR{Large}{f}$ is onto there is some MATH with MATH.

As usual, by definition if MATH then MATH and if MATH then MATH.

Proof B:( yet another diagonal argument. This is just a disguised version of A.)

Let $\QTR{Large}{B=\{}$0,1$\QTR{Large}{\}}$. Let MATH be the set of all maps from $\QTR{Large}{S}$ to $\QTR{Large}{B.}$ . There is an obvious 1 to 1 onto map MATHSpecifically,

MATH1$\QTR{Large}{\}}$ . Hence to prove 9.4 we can show that for any set $\QTR{Large}{S}$ ,there is no onto map MATH.

Suppose there was such a map. Define MATH by the formula

$\vspace{1pt}$ The rest of the proof is standard. Suppose there was some MATH such that MATH MATH Compute

MATH MATHIf MATH MATH 0 then by definition MATH 1 and so on.....

Proof C:( yet another fixed point theorem. )

We first prove the following lemma, which is really a generalization of B.

9.4.1 Lemma : For sets $\QTR{Large}{S}$ and $\QTR{Large}{T}$, suppose there exists an onto map MATH, then every self-map MATHhas a fixed point.

Proof:

Consider the "evaluation" map MATH defined by the formula MATH

Like in B, above define MATH by the formula MATH

Again, since $\QTR{Large}{f}$ is onto there is some MATH such that MATH MATH

We have

MATH

on the other hand, by definition,

MATH MATH

Thus MATH is a fixed point for $\QTR{Large}{h.}$

Now, to complete the proof of 9.4, Let MATH0,1$\QTR{Large}{\}}$ and note that $\QTR{Large}{B}$ has a fixed point free self-map. In particular, let MATH be define by the formula

$\QTR{Large}{h(}$0$\QTR{Large}{)=}$1 and $\QTR{Large}{h(}$1$\QTR{Large}{)=}$0 .

Notation:

  1. The standard notation for MATH is MATH .

  2. For $\QTR{Large}{i=0,1}$, if MATH is a set with MATH we use multiplicative notation MATH for MATH Check that this is well defined.

  3. If $\QTR{Large}{S}$ is a set with MATH, the standard notation for MATH is MATH, as suggested by the second proof of 9.2 .

  4. The standard notation for MATH is MATH

We will be very interested in MATH We end this Page with a Theorem that is in fact a special case of a general result about infinite cardinals.

9.4 Theorem:

MATH

Proof:

Let MATH and MATH be the odd and even natural numbers respectively. In full detail,

Again, letting $\QTR{Large}{B=\{}$0,1$\QTR{Large}{\}}$ We invoke Lemma a. on the Background Page to observe that there is a one-one onto map.

MATH

Hence,

MATH

MATH

9.5 Theorem: Assignment to be turned in:

Let $\QTR{Large}{D}$ be a finite set with MATH, then MATH

Hint:

Use Lemma 0.3 b. on the Background Page and 9.4 above to prove the theorem by induction for MATH2MATH .

Next use 9.3 to prove the result when 2MATH2MATH

Solution

One verifies that

MATH2

and

MATH2MATH

By induction, suppose we have shown that MATH

The map MATH is one to one and onto.

Similarly

MATH is one to one and onto.

Thus

MATH is one to one and onto.

Now assume

2MATH2MATH and choose one to one maps MATH and MATH These induce one to one maps.

MATH and MATH

Finally, apply Schroder-Bernstein to MATH and MATH .