Next: Cantor's Power Set Theorem; Up: Finiteness09february2012 Previous: Criteria for finiteness of

## Countable sets

A set is said to be countable, if and only if it is either finite, or there is a bijection from to .
In the latter case, is said to be countably infinite.
If a set is not countable, then is said to be uncountable.
Using this concept we may summarize some of our above results as follows, for a non-empty set .
• There is an injection , if and only if is countable.
• There is a surjection , if and only if is countable.
• A countably infinite set is not finite.
We also have the following results relating countable sets.
Let and be non-empty sets and be a map.
• If is an injection and is countable, then so is .
• If is an injection and is uncountable, then so is .
• If is a surjection and is countable, then so is .
• If is a surjection and is uncountable, then so is .
The set is countably infinite.
A quick way to map injectively into is to map to the positive integer , for each .
By prime factorization, this is an injection into , so is countable.
But is not finite, since it is not empty and there is an injection from to , given by for each .
So is countably infinite, as required. Then we have the theorem:
• A countable union of countable sets is countable.
Let be a non-empty countable set and let be a countable set, given for each .
Let .
Then is countable.
We may assume that is non-empty and that each is non-empty, at the cost of replacing by a subset, still countable and non-empty.
Since is countable, there is a surjection .
Then we have:

So without loss of generality, we may assume that and we have:

Here each is countable and non-empty.
Next for each choose a surjection .
Finally define a map from to , by the formula: , for any . Then is well-defined. Also if , then , for some . Then we have , for some , which gives , so is surjective and is countable and we are done.

If denotes the integers, and and the positive and negative integers, respectively, then , so is countably infinite. Also the map , for any , gives a bijection from to , so is countably infinite. Also the set is countable, having one element.
So the set , being a countable union of countable sets, is countably infinite.

If and denote the positive and negative rationals, respectively, then there are surjections (automatic, by definition of ) from , which map any to the rational .
So and are each countably infinite (being not finite, since they each contain an infinite number of integers as subsets).
So the set is countably infinite.

Next: Cantor's Power Set Theorem; Up: Finiteness09february2012 Previous: Criteria for finiteness of
George A. J. Sparling 2012-02-09