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.

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

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}.

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

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) 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 A_{1}, A_{2},... are countable
sets, then A_{1}U A_{2} U A_{3} 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 A_{q} be the set of all rational numbers that are
equal to p/q for some integer p. Since A_{q} 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 A_{1},A_{2},... , 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
A_{1},A_{2},... 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 A_{n}. This is enough to ensure, for every n,
that A does not equal A_{n}. 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).