A set is countable if and only if each of its elements can be associated with a different positive integer. Every finite set is countable. For example, the set {2, 3, 5, 7, 11} is countable.
1↔2
2↔3
3↔5
4↔7
5↔11
Infinite sets can also be countable. For example, the set of all prime numbers is countable.
1↔2
2↔3
3↔5
4↔7
5↔11
6↔13
7↔17
8↔19
9↔23
10↔29
...
1. Is the set of all integers countable?
2. Is the set of all positive rational numbers countable?
3. Is the set of all rational numbers countable?
4. Is the set of all positive real numbers countable?
5. Is the set of all real numbers countable?
There is a discussion of this in one of Ian Stewart's books, where he gives various examples in relation to Hilbert's Hotel.
In one of them, an infinite number of coaches, each containing an infinitely large number of passengers, arrives at the hotel seeking lodgings. They are all put up for the night.
Now, the number of subsets of a set with n elements is 2^n. If there are infinitely many (I) elements, then that set has 2^I subsets.
Let's assume for the moment that 2^I is somehow greater than I. But then it must be less than 3^I, 4^I and so on. In particular, 2^I must be less than I^I.
But in the Hilbert example, there were infinitely many, or I, coaches, each containing infinitely many, or I, passengers, for a total of I^I passengers. Nevertheless, all of them were accommodated.
So we have the paradox that 2^I>I^I.
Now consider Cantor's diagonal argument, in the context of the same example. We start by chopping up the number line at each integer. There's clearly a 1 to 1 correspondence between the occupants of the first coach and the integers. So we assign each passenger to one integer, with the remark (Coach1) in front. Now we assign the occupants of the second coach to all those numbers that are rational, not forgetting to add (Coach2) in front, so we can keep track; we know we can do this already.
Now we can assign Coach 3 to, say, the algebraic numbers, for example, and so on. It is of course true that there are infinitely many numbers left over in the gaps between those already assigned. On the other hand, we have an infinite supply of coaches, each with its own identifying number, to work with. If, as in the diagonal argument, we find a number that is different from all those we have already dealt with, we simply call in another coach, not forgetting to add its identifying number at the front, so we don't get mixed up.
Finally, when each and every real, imaginary, complex and other number is accounted for, we use Hilbert's method to accommodate all the passengers in the hotel....
Correction: It should be I*I passengers, not I^I passengers.
Edited on March 16, 2016, 11:07 am

Posted by broll
on 20160316 08:51:25 