A set is considered Uncountably Infinite if it is not countably infinite. Georg Cantor (1845-1918 in Germany) proved that the set of real numbers \[\mathbb{R}\] is uncountably infinite. We can show that no matter what list we write of real numbers, there will always be some real number that is not on that list. That means that there is no one-to-one correspondence with the natural numbers.
This number is different from the first number in the first digit, different from the second number in the second digit, and different from the nth number in the nth digit.
Uncountably Infinite is often referred to as the continuum - the set of real numbers denoted by \[\mathfrak{c}\]
Hilbert's Hotel: A Helpful Illustration
David Hilbert was a German mathematician who is known as one of the fathers of proof theory and mathematical logic. Importantly, he adopted and defended Cantor's set theory with Hilbert's Hotel - first introduced in 1924.
Here's how the hotel works. Imagine a hotel with infinite rooms. Each of the rooms is numbered 1, 2, 3, 4, 5, ... n, n+1... and so on. Each of the rooms is occupied by a person named ONE, TWO, THREE,... that matches their room number. Every room has a resident; there are no empty rooms. Every resident has a room; no one is sharing or sleeping in the hallway. No Vacancy.
Let's start with an easy problem. One guest shows up seeking a room for the night. To make room for him, the hotel manager simply asks each guest to move into the room next door: ONE moves to room 2, TWO moves to room 3, and so on. Then the new guest can move into room 1. This strategy works with any finite number of new guests. If there are, say 127 new guests, ONE moves into room 238, TWO into room 239, and so forth. Therefore, we can add any finite number to a countable infinity set and still have a countably infinite set. Notice that the manager can't just place the new guests into the last rooms - there are infinite rooms and thus are no last rooms. He has to be more creative.
Now, what if all the even numbers want to stay in the hotel? This party is infinite, so the manager's previous strategy will not work. Rather, the manager asks each guest to move to the room that is twice their name - so ONE moves to 2, TWO moves to 4, THREE moves to 6, and so on with each guest N moving from room n to 2n. This leaves open all the odd numbered rooms for the new guests to move into.
What if all the rationals want a room for the night? As we saw earlier, there is no nice, neat formula for mapping the rationals onto the naturals. Instead, the manager can draw up a chart like we used earlier to show that the rational numbers are countably infinite. Then each guest can look on the chart, find himself, and then go to his room.
Therefore, as seen with rationals and all even numbers, a countably infinite set plus a countably infinite set is still a countably infinite set. The size does not change.
Now, what if the real numbers come? Here, we run into a problem. The reals are uncountably infinite. That means they are larger than the naturals, the evens, or the rationals. There are simply more of them and there is no way that all the real numbers can fit into a hotel with only countably infinite rooms without someone having to share with a roommate.
Next: The Continuum Hypothesis Back to Semester Project