Countability (Mathematics)

In mathematics, a set is called countable if it can be numbered in such a way that every element will eventually receive a number.

Examples of Countable Sets

Obviously, the numbers 1, 2, 3, etc., are countable, but so are all the integers: 0 we call first, 1, second, -1, third, 2, fourth, -2, fifth, 3, sixth, and so on, going outwards. We're sure to hit every integer this way.

Somewhat surprisingly, the rational numbers are countable as well. See the picture below:

Examples of Uncountable Sets

The real numbers are not countable, nor is any set with positive Lebesgue measure. This is because any countable set of numbers can be completely contained within a set of arbitrarily small measure. A short proof follows:

Let $\left\{{a_{1},a_{2},a_{3},...}\right\}\$ be a countable set, and let $w\$ be some arbitrarily small number. Construct the interval $[a_{1}-w/4,a_{1}+w/4]\$.

Obviously, $a_{1}\$ is contained in this interval, and this interval has length $w/4+w/4=w/2\$.

But around $a_{2}\$, we can construct the interval $[a_{2}-w/8,a_{2}+w/8]\$, around $a_{3},[a_{3}-w/16,a_{3}+w/16]\$, and in general, around $a_{k}\$, we can construct $[a_{k}-w2^{k+1},a_{k}+w2^{k+1}]\$.

The sum of all these lengths will be $w/2+w/4+w/8+w/16+...=w\$, but remember, $w\$ was chosen to be arbitrarily small, and so a countable set can be contained in a set of arbitrarily small measure.

Since the real numbers, or any set of positive measure, cannot, they must not be countable.