Counting to infinity

     Riddle me this: if you have the collection of all the positive integers (1, 2, 3, 4, 5, and so on) and you remove all of the odd numbers, is the remaining set of even numbers (2, 4, 6, 8, and so on) smaller than your old set?

     I've spent the last three weeks or so thinking hard about infinity. It's a required portion of one of my second year classes, and although we have covered the material and moved on I am still haunted by paradoxes and strange dreams. Heads up: this article may get a little technical and thought provoking.

     In the 19th century, a German mathematician named Georg Cantor founded a field of math known as set theory. His new ideas were met with criticism, and he was repeatedly institutionalized for mental illness. (After studying just a few of his ideas, I don't blame him. This stuff would drive anyone mad.) However, David Hilbert welcomed Cantor's revolutionary ideas, and stated that "No one will drive us from the paradise that Cantor has created." The logic used in set theory has been used to prove remarkable results in modern mathematics.

      I'd like to share some really interesting ideas with you. Let's suppose that we have an infinite set of objects and some way to count them. For example, if our collection was the set of positive integers (1, 2, 3, 4, 5, and so on), we could agree that there are infinitely many and that we could count them. We would say that this set was countably infinite. If we included 0 and the negative integers as well, we could still count the set. (0, -1, 1, -2, 2, -3, 3, -4, 4, and so on). As long as the set can be put in some sort of list, all elements are guaranteed to appear in the list, and the list goes on forever, then we consider the set to be countably infinite. (Note: some sets of numbers, such as the real numbers, cannot be ordered in such a list. We call these sets uncountable, but we will not deal with these sets here.)

     We can find the size of a finite set by counting the number of objects. For example, the set {a, b, c, d, e} has five elements in it, so it has size 5. But what size does an infinite set have? Can there be different sizes of infinities? What does "infinite size" even mean?

     Cantor suggested that we could consider two sets to have the same size if we could pair up each element from the first set with a unique element from the second. If each element had a partner and no elements were left over, then the sets are the same size. So if you have a crowd of people boarding a train and each person takes a seat and all seats are taken, then the number of seats is equal to the number of people. Now imagine that the train has infinitely many seats and the line of people is infinitely long. Cantor supposed that we could use the same logic on infinite sets; if there is exactly one seat per person then there are the same number of seats as there are people. (Author's note: I have not yet accepted the use of this logic on infinite sets, but I'll share some results with you anyways.)

     Let's look back at our original question. Consider the set of positive integers {1, 2, 3, ...}. Suppose we removed all of the odd numbers from this list. We would be left with the evens {2, 4, 6, ...}.  If you take any number from the first list and multiply it by 2, you will get a number from the second list. Also, each integer when multiplied by two will produce a unique even integer. Furthermore, for every even number, you can divide it by two to get a number from the first list. We are pairing up our lists like so:

{1, 2, 3, 4, 5, ...}
{2, 4, 6, 8, 10, ...}  => (1,2) (2,4) (3,6) (4,8) (5,10),...

We pair each element from the first set with a unique element from the second set, and no elements are left over. By Cantor's logic, these sets are the same size.The number of positive integers is equal to the number of positive even integers. Oh dear.

     This means that you can take a countably infinite set, remove infinitely many objects, and the set will be the same size. In fact, you could add a countably infinite number of objects and the set would be the same size. You could add a countably infinite number of objects a countably infinite number of times, and the set would still be the same size. Holy paradox, Batman!

      Some people are not bothered by this result. After all, infinity is infinity, right? Doesn't it make perfect sense that infinity as the same size as infinity? Well, not quite. It gets weirder. I'll leave you with one more strange thought.

     It turns out (for reasons that I will not address in this post) that there are different sizes of infinity. Some infinities are bigger than others. For example, there are more numbers between 0 and 1 (including decimals like 0.5, 0.111234, and 0.101010...) than there are integers (0, -1, 1, -2, 2, etc.)

     Stay tuned for more insomnia fueled posts about infinity. I'd like to address my issues with Cantor's logic, sets that should be the same size but aren't, and Hilbert's infinite hotel. Check your intuition at the door. It will serve no purpose when discussing infinity.