All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars    
perplexus dot info

Home > Just Math
Countable sets (Posted on 2016-03-15) Difficulty: 3 of 5
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.


Infinite sets can also be countable. For example, the set of all prime numbers is countable.


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?

No Solution Yet Submitted by Math Man    
No Rating

Comments: ( Back to comment list | You must be logged in to post comments.)
Interesting | Comment 5 of 8 |

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 2016-03-16 08:51:25

Please log in:
Remember me:
Sign up! | Forgot password

Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (4)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Copyright © 2002 - 2018 by Animus Pactum Consulting. All rights reserved. Privacy Information