What does countable mean?
A set having infinitely many elements is countable if its elements can be arranged into an infinite list.
Here are some examples of inifinte sets that are countable:
The set of natural numbers is countable. It can be arranged into a list as follows:
1, 2, 3, 4, 5, .....
The set of integers is countable. It can be arranged into a list as follows:
0, 1, -1, 2, -2, 3, -3, 4, -4, 5, -5, ......
The set of all positive fractions is countable. It can be arranged into a list as follows:
1/1,
1/2, 2/1,
1/3, 2/2, 3/1,
1/4, 2/3, 3/2, 4/1,
1/5, 2/4, 3/3, 4/2, 5/1, ..........
You will have to admit that every fraction that you can think of will be in this list.
Another, but equivalent, way of defining a countable set is to say that there exists a one-to-one correspondence between the elements of that set and the natural numbers. After all, that is exactly what is being done when the elements of the set are arranged into a list. Such a one-to-one correspondence is called a bijection.
In the example above, where the set of positive fractions are arranged into a list, you may have noticed that there are duplicates. (For example, 1/2 is the same as 2/4.) That's ok.
If you prefer, you can remove all the duplicates. Then, the bijection that remains will be with an infinite subset of the natural numbers. As long as you can set up a bijection between the elements of a set and an infinite subset of the natural numbers, then the set is countable.
An infinite set whose elements cannot be arranged into a list is uncountable. Equivalently, we can say that an infinite set is uncountable if there does not exist any bijection between it and the set of natural numbers.
Here are some examples of infinite sets that are uncountable:
The set of all real numbers.
The set of all real numbers in the unit interval [0,1].
The set of all points in the unit square [0,1]X[0,1].
The set of all subsets of the unit interval [0,1].
The method that is normally used to prove that a set is uncountable is called diagonalization.
The mathematician Georg Cantor was able to prove that there are an infinite number of levels of infinity. The smallest level of infinity is the countable infinity. Then, there are infinitely many uncountable infinities of different sizes.
Of the four examples above of uncountable sets, the first three are of the same size. To prove that any two sets are of the same size, all you need to do is to show that there is a bijection between them. (To show that the unit square [0,1]X[0,1] and the unit interval [0,1] are at the same level of infinity, you can use the Peano Curve as the bijection between them.)
The fourth example (the set of all subsets of the unit interval) also has an uncountably infinite number of elements, but this infinity is larger than the infinite number of elements in the first three examples. This can be proved by showing that there does not exist any bijection between the points of the unit interval and all the subsets of the unit interval. The method of proof is very reminiscent of the diagonalization method.
The proof goes like this: Suppose A is the set of all points in the interval [0,1], and suppose B is the set of all subsets of A. For sake of contradiction, suppose that we actually can find a bijection f between A and B. Then, define the set X as follows: X = {x ∈ A | x ∉ f(x)}. Then, X is a subset of A so therefore it must be an element of B. But, X does not match any of the elements of B to which f maps the elements of A. In other words, when f was constructed, the element X of B was somehow missed. Hence, f cannot be a bijection between A and B, showing that the infinite number of elements of B is a bigger infinity than the infinite number of elements in A.
Diagonalization is the method that is normally used to prove that one infinity is larger than another infinity. Interestingly enough, that was not the first method that was discovered.
What happened was, that one day Georg Cantor was doing a lot of thinking about sequences of numbers taken from the unit interval. In one instance, he imagined that he listed all of the points of the unit interval [0,1] as an infinite sequence of real numbers. (At this time, no one had yet discovered countable and uncountable sets, so Cantor may very well have imagined that doing this is possible.) Then, from this sequence, he very cleverly and judiciously constructed two subsequences which converged to a point that could not be on the list. This is very nicely explained in a video.
An uncoutable set is much bigger than a countable set. However, you really don't get a really good appreciation for how much enormously bigger it is until you study Measure Theory.
The measure of an interval is just its length. The measure of a single point is zero because it has zero length. In Measure Theory you learn that the measure of a countable set of points is also zero. So, for example, if you start with the unit interval [0,1] and remove from it any countable set of points (such as all the rational numbers), then what you're left with is something of measure one. When you think about this, then this means that the countable infinity is very tiny, miniscule, and insignificant when compared with the uncountable infinity!
On the Home page of this website, it says that Alan Turing used his Turing Machine to prove "that most numbers can never be calculated or even imagined by any machine or human."
A Computable Number is any number that you could normally think of and maybe write it down, or at least explain a method by which it could be computed. They are precisely those numbers that can be computed by a Turing Machine (or any other computer).
However, every Turing Machine has a Turing Machine Number associated with it. This means, that there are only a countable number of Turing Machines. It also means that there can be only a countable number of algorithms. Furthermore, it means that there are only a countable number of Computable Numbers. Above all, this means that most of the numbers in existence can never be computed!
If the human mind is a Turing Machine (as many people believe), then we as humans have absolutely no hope at all of ever imagining any of the vast, enormous, and immense majority of numbers!
The set of natural numbers is countable. It can be arranged into a list as follows:
1, 2, 3, 4, 5, .....
The set of integers is countable. It can be arranged into a list as follows:
0, 1, -1, 2, -2, 3, -3, 4, -4, 5, -5, ......
The set of all positive fractions is countable. It can be arranged into a list as follows:
1/1,
1/2, 2/1,
1/3, 2/2, 3/1,
1/4, 2/3, 3/2, 4/1,
1/5, 2/4, 3/3, 4/2, 5/1, ..........
You will have to admit that every fraction that you can think of will be in this list.
If you prefer, you can remove all the duplicates. Then, the bijection that remains will be with an infinite subset of the natural numbers. As long as you can set up a bijection between the elements of a set and an infinite subset of the natural numbers, then the set is countable.
The set of all real numbers.
The set of all real numbers in the unit interval [0,1].
The set of all points in the unit square [0,1]X[0,1].
The set of all subsets of the unit interval [0,1].
Of the four examples above of uncountable sets, the first three are of the same size. To prove that any two sets are of the same size, all you need to do is to show that there is a bijection between them. (To show that the unit square [0,1]X[0,1] and the unit interval [0,1] are at the same level of infinity, you can use the Peano Curve as the bijection between them.)
The fourth example (the set of all subsets of the unit interval) also has an uncountably infinite number of elements, but this infinity is larger than the infinite number of elements in the first three examples. This can be proved by showing that there does not exist any bijection between the points of the unit interval and all the subsets of the unit interval. The method of proof is very reminiscent of the diagonalization method.
The proof goes like this: Suppose A is the set of all points in the interval [0,1], and suppose B is the set of all subsets of A. For sake of contradiction, suppose that we actually can find a bijection f between A and B. Then, define the set X as follows: X = {x ∈ A | x ∉ f(x)}. Then, X is a subset of A so therefore it must be an element of B. But, X does not match any of the elements of B to which f maps the elements of A. In other words, when f was constructed, the element X of B was somehow missed. Hence, f cannot be a bijection between A and B, showing that the infinite number of elements of B is a bigger infinity than the infinite number of elements in A.
Version 1.0 -- April 23, 2017