Conceptually, countable infinity is an infinity you can "count". If you could theoretically list all the elements of the set in some chart or table, then count them up, then the set is countably infinite. Imagine the set of all natural numbers. You start with 1, then 2, 3, 4, 5, 6, .... Eventually, (theoretically - remember that infinity is a size, not a number) you would reach "infinity". Or think of all positive even numbers: {2, 4, 6, 8, ...}. Again, theoretically I could list all elements. What about all positive multiples of 3: {3, 6, 9, ...}? Again, I can list all elements in the set. Some sets can't be written out this way, as we'll see later.
The definition of a Countably Infinite (also known as denumerably infinite) set, denoted \[\aleph_0\] is any set that can be put into a one-to-one correspondence with the set of natural numbers. That means that for every natural number there is a unique element of the set that can be paired with it.
Let's look at those examples again.
How can we map the positive even numbers onto the natural numbers? Let n \[\in\] N and e be an even number in the set E of even numbers. By setting each e = 2n, we can relate each natural number n with a unique member of E. Every even number has a natural number, and there are no natural numbers with multiple even numbers.
For S as the set of positive multiples of 3, we can set each s \[\in\] S as s = 3n. Notice again that every natural number n has a unique element of S.
But wait! Does that mean that there are just as many even numbers as natural numbers? And just as many multiples of 3 as multiples of 2 as natural numbers? Even though the natural numbers contain elements like 7, 13, and countless others that aren't even or aren't multiples of 3? Yes. Although it seems a bit counterintuitive, yes. The size of the evens is the same as the size of the evens and odds together. This is where we have to rely on our math instead of our intuition. Even though one set clearly contains more elements than the other, they are still the same size infinity because they can be put into a one-to-one correspondence.
Rational Numbers and Countable Infinity
The rational numbers ( \[\mathbb{Q}\] ) are defined as \[\{ \frac{m}{n} | m, n \in Z \} \] As it turns out, the rational numbers are also countably infinite - the same size as the natural numbers. Unlike the sets in our previous examples, we can't write out a nice, neat formula to show that there is a one-to-one correspondence between the rationals and the naturals. But we can write out all the rationals in a table:
Then count them up like this:
However, notice that some numbers will be counted twice: 2/2 is the same as 3/3 which is the same as 1/1. That means that there will be a lot of empty rooms.
To resolve this problem, we can only use the elements that are in their simplest form. Since 2/2 can be reduced to 1/1, we throw it out. Using this method will eliminate the repeating elements. This technique is demonstrated in the video below.
Some sets can't be put into this one-to-one correspondence. These sets are called Uncountably Infinite.
Next: Uncountable Infinity Back to Semester Project