The above writeups, that define a
set to be countable if it has a one to one correspondence with the
naturals (or a subset of it) are of course correct, but aren't terribly helpful to the layman. For once Webster provides more insight than you might think.
Counting
If I were to ask you to count the socks in a draw you will go through them in some order, counting "one", "two", "three" etc... (or the equivalent in the language of your choice) Subconsciously, you are doing 2 things:
-
You are picking a first element.
-
For each element, you define a next element.
Both of these 2 things can be completely arbitrary. It doesn't matter which sock you count first or which order you count them in, what matters is that you can do this.
From counting to countable
If you read some of the excellent writeups in natural number you will find that this is how one can define the natural numbers. Briefly there is a first natural number, and each natural number has a successor, i.e. a natural number that is after it, and this defines the natural numbers.
It should be trivial that any finite set is countable: you could just put each element of the set on the floor and point your finger at them each in turn (given a big enough floor of course). Technically you have just defined a bijection between your set and a subset of the naturals (for example {1,2,..,n}, where n is the number of elements in the set).
Infinite sets can also be countable, it's just that you will never finish the counting. If you start counting the natural numbers, you will keep on going for ever, but it's a perfectly well defined thing to do. Saying that an infinite set is countable is basically saying that it is like the natural numbers, that it has the same number of elements as the natural numbers. When dealing with infinite sets, the way to define the property of "having the same number of elements" is to look for a bijection (one to one correspondance) between the two sets. In our particular case it means that we want to be able to take an element of our set and put it together with 1, and then find the next element which we'll associate with 2 and so on. You must of course be careful not to miss out any elements of the set.
There are sets that are uncountable. An example would be the the real line. At first you might think that this is because of all the fractions or numbers like √2, but in fact the bulk of the real numbers are the transcendental numbers, which are rather harder to pin down.(a proof of the uncountability of the reals is here).
Examples of countable sets:
-
The integers: one can use the ordering 0,1,-1,2,-2,...
a bijection would be f(n)=(-1)nfloor(n/2), where floor is the function that gives you the greatest integer smaller than its argument (so floor(2)=2, floor(1.5)=1).
-
The odd, positive integers: take f(n) to be 2n-1
-
The rationals: a complete proof is here
-
The algebraics: this is the set of roots of polynomial equations with integer coefficients (or equivalently rational coefficients). For example √2 is an algebraic number as it is a solution of the equation x2=2. Proving this by explicitly finding a bijection is rather more difficult.
This can be counterintuitive, as one might expect that the set of odd naturals would be smaller than the naturals or that the set of rationals or algebraics would be bigger.
A useful theorem
The following theorem, due to Cantor, is useful for proving that a set is countable: A countable union of countable sets is finite.
One could use this to prove that the algebraics are countable:
-
Define the height of a polynomial to be the sum of the absolute values of its coefficients and its degree. It should be immediate that there are finitely many polynomials of a given height.
-
A polynomial of degree n has at most n roots, so the set of roots of polynomials of given height is also finite.
- The height of a polynomial is an natural number, so we have split the algebraics into finite sets, of which there are countably many. So the set of algebraics is a countable union of countable sets, and so is countable.
Thanks to krimson for some most helpful comments.