Characterisations of countability

Ponder...

For a set these are equivalent: is countable; there is an injection ; there is a surjection , or .

Theorem 6.4

The following statements are equivalent for a set :

Proof

. An injection bijects with its image . Any subset of is countable, so is countable.

. This is clear if . If is countably infinite, take a bijection ; its inverse is a surjection.

. Suppose and let be a surjection. Define by

which is well-defined since is surjective. If then

so ; hence is an injection.