When I was in elementary school, I had a teacher who told us there were fewer even numbers than whole numbers, because half of all whole numbers are even, and the other half are odd. I argued that there must be same amount because there an inifinite amount of whole numbers and an infinite amount of even number, and infinity equals infinity.

Well, it turns out, my conclusion was correct, but my reasoning wasn't.

That probably seems really strange. Surely, if you take the set of all even numbers, and then you add all the odd numbers, it would end up bigger than it started, right?

To answer that, we need to talk about what it means for two sets to be the same size. For finite sets, it's simple; just count how many elements there are. But you can't count to infinity, so that doesn't work for infinite sets.

You can say that if set A contains all the elements of B, but set B doesn't contain all the elements of set A, then set B must be smaller, but that won't work for every pair of sets.

So, mathematicians came up with the concept of cardinality, which works for every set. The way it works is that two sets have the same size if you can come up with a mapping between the two sets, such that every element in each set is associated with exactly one element in the other set.

Here's an example. Let's say you have the two sets {Red, Green, Blue} and {Circle, Square, Triangle}. We can make this mapping:
Red ⇔ Circle
Green ⇔ Square
Blue ⇔ Triangle

Every element in the first set is associated with exaclty one in the second set, and every element in the second set is associated with exactly one in the first, so those two sets have the same cardinality. And, because they're finite, we can also just count them and that works too.

In fact, you could even say that this is actually the same process as counting. You're making a mapping between the set you're counting and the set {1, 2, 3...n}.

And this same concept can be applied to infinite sets. Here's a mapping between all integers and all even integers: For every integer N, N ⇔ 2N

This mapping associated every single integer with exactly one even integer and every single even integer with exactly one integer. Therefore, the two sets have the same cardinality.

You can even make such a mapping between all integers and all positive integers, or between all integers and all rationals, so all of those different sets have the same cardinality too.

Does that mean every infinite set is the same size as every other infinite set?


It turns out that the set of all real numbers is bigger than the set of all integers.

Here's how can show that. First, assume that there is such a mapping, so you can associate every real number with exactly one integer. That means you can put those real numbers in an ordered list, so you can talk about the first number in the list, the second one, and so on.

But there's a real number that's nowhere on the list. To find it, we need to build it, digit by digit, based on the numbers in the list. Here's an example list:
#1: 0.40396...
#2: 0.09714...
#3: 0.73175...
#4: 0.90453...
#5: 0.97491...

I've bolded some digits, because those are the ones we're looking at. The first digit of the first number, the second digit of the second number, and so on, along the diagonal.

For each digit, we'll add one to it (Or if it's nine, subtract one. What matters is that we get a different number than what's already there.)

By doing that, we'll get a number that starts 0.58262...

This number can't be equal to the first number, because the first digit is different. It can't be equal to the second number, because the second digit is different. And so on, for every single number in the list. And notice that this works for every possible list of real numbers, not just this example.

Since there's a real number that's not in the list, the mapping must not include every single real number, and therefore the sets don't have the same cardinality. This is called Cantor's diagonal argument

So just because two sets are infinite doesn't mean they have the same size.