S. D. V. Stephens

notes / Measure Theory / chapter 0: Prologue

0.3 Cardinality

For and we use and .

  • there is an injection ;
  • there is a bijection ;
  • there is a surjection .

and are for the strict versions: an injection (resp. surjection) but no bijection.

Proposition 0.3.1. .

Proof. Let be injective. Pick and define by if , otherwise. Then is surjective. Conversely, if is surjective, the sets , , are nonempty and disjoint, so any is an injection . ∎

Proposition 0.3.2. For any , either or .

Theorem 0.3.3 (Schröder–Bernstein). If and , then .

Proposition 0.3.4. For any , .

Definition 0.3.5. is countable if .

Proposition 0.3.6.

  1. countably infinite .
  2. countable countable (and conversely when ).
  3. If is countable and is countable for every , then is countable.

Corollary 0.3.7. and are countable.

is said to have the cardinality of the continuum if . We use as our notation for . So .

Proposition 0.3.8. .

Proof. If , define by

thus is injective. Now define by

Then is surjective, so by Schröder–Bernstein, since . ∎

Corollary 0.3.9. If then is uncountable.

Proposition 0.3.10.

  1. If and , then .
  2. If and for all , then .