Re:What Is the Most Surprising Result in Mathematics?
by ColinWright on Saturday July 06, 2013 @05:46PM
(#6000182)
It is a precise term with a precise meaning. You can look it up and found many, many explanations online, some of which will be right, few of which will be truly helpful.
Let me add to them.
If you can put a set into one-to-one correspondence with the counting number (which are 1, 2, 3, and so on) then we call the set "countable" or "countably infinite". Examples include (but are not limited to):
* The even counting numbers: 2, 4, 6, 8, 10, and so on;
* The integer squares: 0, 1, 4, 9, 16, 25, and so on;
* The primes: 2, 3, 5, 7, 11, 13, 17, 19, 23, and so on;
* The rational numbers (fractions);
* Finite strings made from a finite collection of symbols;
... and more. You may choose to think about how matchings can be made between each of these and the counting numbers, or each with the others - some ingenuity required.
However, there are infinite collections that cannot be put into one-to-one correspondence with the counting numbers. Examples include:
* Infinite non-terminating strings of 0s and 1s;
* The reals;
* All sets (finite and infinite) of counting numbers;
... and more.
Such infinite collections, since they cannot be matched up with the counting numbers, are called "Uncountably Infinite Sets".
To prove that such collections can never be matched up with the counting numbers is a typical exercise for 1st year undergrads in mathematics, or for precocious mathematics enthusiasts. I first met it when I was about 8 years old and reading Martin Gardner. The usual proof is Cantor's "Diagonalisation Argument"[0][1], and you can find a version of that here:
That includes a genuine proof of the existence of a set that is infinite, and cannot be put in one-to-one correspondence with the counting numbers.
Still, many people find that unconvincing. I personally prefer Cantor's first argument that there exist transcendental numbers, which is equivalent. Here it is, adapted to show that any list of numbers is incomplete. You'll need to concentrate:
Take any list of numbers: c_0, c_1, c_2, etc.
Take any interval [a0,b0], and cross out numbers from your list until you find one, say, c_i, in the interval (including an endpoint). Take some strict sub-interval [a1,b1] within [a0,b0] such that a0<a1, b1<b0, and c_i is not in [a1,b1]. Now continue crossing off numbers, and each time you find one in your current interval, take a sub-interval to exclude it.
The left hand end-points, a0, a1, a2, etc, form a strictly increasing sequence of points. This sequence is bounded above, so it has an upper bound. Consider the least upper bound.
This cannot be on your original list, because everything was, at some point, excluded. Hence your original list cannot be complete.
And in case you think I can only ever construct one missing number, I can actually construct infinitely many missing numbers. At each stage instead of taking just one sub-interval, I take two subintervals, each excluding the number from your list.
I'm intending to write all this up soon, so if you're interested, I can let you read a draft as a way of improving your understanding, and giving me an attentive proof-reader.
[0] Not to be confused with the diagonal path in the argument that the fractions are countable.
Let me add to them.
If you can put a set into one-to-one correspondence with the counting number (which are 1, 2, 3, and so on) then we call the set "countable" or "countably infinite". Examples include (but are not limited to):
* The even counting numbers: 2, 4, 6, 8, 10, and so on;
* The integer squares: 0, 1, 4, 9, 16, 25, and so on;
* The primes: 2, 3, 5, 7, 11, 13, 17, 19, 23, and so on;
* The rational numbers (fractions);
* Finite strings made from a finite collection of symbols;
... and more. You may choose to think about how matchings can be made between each of these and the counting numbers, or each with the others - some ingenuity required.
However, there are infinite collections that cannot be put into one-to-one correspondence with the counting numbers. Examples include:
* Infinite non-terminating strings of 0s and 1s;
* The reals;
* All sets (finite and infinite) of counting numbers;
... and more.
Such infinite collections, since they cannot be matched up with the counting numbers, are called "Uncountably Infinite Sets".
To prove that such collections can never be matched up with the counting numbers is a typical exercise for 1st year undergrads in mathematics, or for precocious mathematics enthusiasts. I first met it when I was about 8 years old and reading Martin Gardner. The usual proof is Cantor's "Diagonalisation Argument"[0][1], and you can find a version of that here:
http://www.solipsys.co.uk/new/CantorVisitsHilbertsHotel.html
That includes a genuine proof of the existence of a set that is infinite, and cannot be put in one-to-one correspondence with the counting numbers.
Still, many people find that unconvincing. I personally prefer Cantor's first argument that there exist transcendental numbers, which is equivalent. Here it is, adapted to show that any list of numbers is incomplete. You'll need to concentrate:
Take any list of numbers: c_0, c_1, c_2, etc.
Take any interval [a0,b0], and cross out numbers from your list until you find one, say, c_i, in the interval (including an endpoint). Take some strict sub-interval [a1,b1] within [a0,b0] such that a0<a1, b1<b0, and c_i is not in [a1,b1]. Now continue crossing off numbers, and each time you find one in your current interval, take a sub-interval to exclude it.
The left hand end-points, a0, a1, a2, etc, form a strictly increasing sequence of points. This sequence is bounded above, so it has an upper bound. Consider the least upper bound.
This cannot be on your original list, because everything was, at some point, excluded. Hence your original list cannot be complete.
And in case you think I can only ever construct one missing number, I can actually construct infinitely many missing numbers. At each stage instead of taking just one sub-interval, I take two subintervals, each excluding the number from your list.
I'm intending to write all this up soon, so if you're interested, I can let you read a draft as a way of improving your understanding, and giving me an attentive proof-reader.
[0] Not to be confused with the diagonal path in the argument that the fractions are countable.
[1] http://en.wikipedia.org/wiki/Cantor%27s_diagonal_argument