Some "Eurekas" of Mathematics - Part One

Sizes of Infinity

Most of the interesting parts of mathematics happen out at infinity. For example, the entire study of calculus would arguably not be possible without the concept of infinity. In order to talk about the sizes of infinity, we first have to establish what we mean by size. Thanks to Georg Cantor, mathematicians have a nice method for comparing the size of sets of infinity. We'll look at just two "sizes": countable and uncountable.

In any mathematical set, its cardinality is the number of elements that set has. Countable sets are based around the set that we are all most familiar with: the natural numbers. The natural numbers is the set of numbers that we first started to learn about: {1,2,3,4,...}. As you could probably guess, the natural numbers the cardinality of this set is infinite, that is countably infinite. The method that Cantor established had to do with mapping elements of the set to the natural numbers. For example, the set of whole numbers, {0,1,2,3,...} has the same cardinality as the natural numbers. The map between the two sets would look like this:

f(n)=n - 1,

where each natural number that you input, outputs the number before it. So the important thing about this map is that it is one-to-one and onto. That is, no elements in the domain (natural numbers) or range (whole numbers) are missed. Whatever whole number you can think of, I can tell you a natural number that will map to it. This might seem counter-intuitive that you can add one number to a set and not change its size. But that's just how bizarre infinity is.

If that didn't surprise you, maybe what we're about to show next will: the set of all integers, {...,-2,-1,0,1,2,...}, is also countably infinite. It has the same "size" as the set of natural numbers. The following function showing the needed mapping:

f(n)=n/2 for even n;
f(n)= - (n - 1)/2 for odd n.

So we send all of the even natural numbers to the positive integers, and the odd natural numbers to the negative integers. And this map is in fact one-to-one and onto. Every imaginable natural number gets mapped, and every imaginable integer gets mapped to.

So maybe now you can see why Cantor picked the name "countable". If you can match each number in the set to a natural number (which are the "counting" numbers), then this means you could sit down and count every single number in the set. In the case that a set is countably infinite, it'll take an eternity to count them all, but an algorithm for counting them all, without missing an element, exists. Now even more surprising is the fact that all rational numbers are countably infinite. The function is pretty complicated, but if you're interested in seeing the counting algorithm, it's here.

So what's the other size of infinity? That's where the irrational numbers come into play. There exists no map from the natural numbers to the irrational numbers. They are uncountable. So the set of irrational numbers, which includes some classics such as π, e, or √2, is bigger than any countable set.

So in sum, sets of countably infinite cardinality/size are "smaller than" sets of uncountably infinite cardinality/size. And it mostly boils down to the pesky irrationals that make sets uncountable. The set of all numbers from 0 to 1 have an infinite amount of irrationals, so that set of numbers is bigger than the set of all integers. It's in moments like this where our mathematical intuition can really fail us...