Countable and uncountable sets

This page is intended to serve as a reference for those who are being supervised on Monday and would like to tackle questions on Sheet 4 about countability over the weekend. A general remark: in order to understand this final part of the course it is essential to be clear about the definitions and basic results about injections, surjections and bijections.

Let me start with a few basic definitions.

1. A set X is said to have cardinality or size n if there is a bijection f:X-->{1,2,...,n}. This does justice to our intuitive idea that it has size n if you can count its elements one after another and end up with the number n. If g is the inverse of f (and therefore a bijection from {1,2,...,n} to X) then you are counting g(1), then g(2), then g(3) and so on. The empty set is said to have cardinality zero.

2. A set is finite if it has cardinality n for some non-negative integer n.

3. A set is infinite if it is not finite.


Proposition

N, the set of all natural numbers, is infinite.

Proof

We must show that, for any n, there is no bijection f:N-->{1,2,...,n}. Let us show more - that there is no surjection from {1,2,...,n} to N. Let g be any function from {1,2,...,n} to N. Then the sum g(1)+...+g(n) is bigger than g(k) for every k<n, so it does not belong to the image of g. Notice that this also proves (via left and right inverses) that there is no injection from N to {1,2,...,n}.


Proposition

A set X is infinite if and only if there is an injection f from N (the set of all natural numbers) to X.

Proof

This is a good example of a result that seems fairly obvious and therefore hard to prove properly. When in that situation, you should always go back to first principles - that is the definitions of finite and infinite. Then the proof becomes easy to find.

Suppose X is finite. Then there is a bijection f from X to {1,2,...,n} for some n. But then there cannot be an injection g from N to X, since then fg would be an injection from N to {1,2,...,n}, contradicting the previous proposition (or rather the stronger statement actually proved).

Conversely, suppose that X is infinite, and build an injection f:N-->X inductively as follows. Suppose you have decided on f(1),f(2),...,f(m) in such a way that they are all different. Then {f(1),...,f(m)} is not equal to X (or there would be a bijection between X and {1,...,m} which we are given that there isn't. So we can find another element of X and call it f(m+1). Continuing in this way we get our map f. [For the cognoscenti: I have used the axiom of countable choice, because I made a countably infinite number of decisions (one for each m) without saying how I did it.]


4. A set X is countable if it is finite or if there is a bijection f from X to N.

This is supposed to capture the idea that the elements of X can be arranged in a "list". (But be careful with this way of looking at it - the idea of a bijection is more precise.) If g:N-->X is a bijection, then the list would go g(1),g(2),...


A few useful facts (especially for examples sheet questions).

(A) The following statements about a set X are equivalent:

(i) X is countable.

(ii) There is an injection f:X-->N

(iii) There is a surjection g:N-->X

I'll prove this in lectures. Notice that (ii) and (iii) follow immediately from (i). Also, (ii) and (iii) are easily seen to be equivalent if you use the fact that a function is an injection/surjection if and only if it has a left/right inverse.

(B) A union of countably many countable sets is countable. To be more precise, if A1, A2,... are countable sets, then A1U A2 U A3 U... is countable.

This is very useful for showing that sets are countable. For example, to show that the rational numbers form a countable set, let Aq be the set of all rational numbers that are equal to p/q for some integer p. Since Aq is the union of the three obviously countable sets {0}, {1/q,2/q,3/q,...} and {-1/q,-2/q,...}, it is countable. Since Q is the union of the sets A1,A2,... , Q is also countable. (In lectures I shall prove this from first principles as well.)

(C) R is uncountable.

This is proved by Cantor's famous diagonal argument. I shan't reproduce it here but it is very easy to find on the web. This is one of many expositions.

(D) The set of all subsets of N is uncountable.

This can also be proved by a diagonal argument. Given a sequence A1,A2,... of subsets of N, define a new set A by the condition that n belongs to A if and only if n does not belong to An. This is enough to ensure, for every n, that A does not equal An. Therefore A was not part of the sequence.

(E) If X is uncountable and f:X-->Y is an injection, then Y is uncountable.

This simple fact is often useful for showing that sets are uncountable. To prove it, note that if Y were countable, then there would be an injection g from Y to N (by the equivalent condition (ii) above) and then gf would be an injection from X to N, contradicting the uncountability of X (again by (ii) above).