Countable

The elements of a finite set can be listed, say {a₁,a₂,...,a_n}. However, not all sets are finite: for instance, the set of all natural numbers or the set of all real numbers. It might then seem natural to divide the sets into different classes: put all the sets containing one element together; all the sets containing two elements together;...;finally, put together all infinite sets and consider them as having the same size. This view is not tenable, however, under the natural definition of size.

To elaborate this we need the concept of a bijection. Do the sets {1,2,3} and {a,b,c} have the same size? "Obviously, yes" you may reply. But how do we know? Again, you may answer "Well it's obvious. Look, they've both got 3 elements". But what if you have no prior knowledge of the number 3, or of any other number [This may seem a strange situation but, although a "bijection" seems a more advanced concept than a "number", in the usual set-theoretic development functions are defined before numbers, as they are based on much simpler sets.] This is where the concept of a bijection comes in: define the correspondence

   a ↔ 1,  b ↔ 2,  c ↔ 3

Since every element of {a,b,c} is paired with precisely one element of {1,2,3} (and vice versa) this defines a bijection.

We now generalise this situation and define two sets to be of the same size precisely when there is a bijection between them. For all finite sets this gives us the usual definition of "the same size". What does it tell us about the size of infinite sets?

Consider the sets A = {1,2,3,...}, the set of positive integers and B = {2,4,6,...}, the set of even positive integers. We claim that, under our definition, these sets have the same size. Recall that to prove this we need to exhibit a bijection between them. But this is easy: 1 ↔ 2, 2 ↔ 4, 3 ↔ 6, 4 ↔ 8, ...

As in the earlier example every element of A has been paired off with precisely one element of B, and vice versa. Hence they have the same size. This gives an example of a set which is of the same size as one of its proper subsets, a situation which is impossible for finite sets.

We now define a set to be countable if it is either finite or the same size as N (the set of positive integers). So the above constitutes a proof that the set of even integers is countable.

What about sets being "larger than" N? An obvious place to look would be Q, the set of all rational numbers, which is "clearly" much bigger than N. But looks can be deceiving, for we assert

THEOREM 1: Q is countable

To prove this we first need to prove

THEOREM 2: The union of countably many countable sets is countable.

This page is still under construction. I would be very grateful for any feedback. In particular, is any of this comprehensible to non-mathematicians

/Talk