Hello everybody! Welcome to my second article about infinity. Last week, we looked at a fun thought experiment called Hilbert's Hotel, where our hotel could somehow house an infinite number of guests! This week, we're going to investigate one of those most fascinating claims in math in recent centuries: Some infinities are larger than others!
How Many Even Integers Are There?
First, let's look at two infinities that are the same size.
Do you think there are more even integers than integers? I've talked about it a little bit already in my previous article, but we're going to discuss it again here a little more formally. The answer is no. It turns out that there are exactly the same number of even integers as all integers. Here's why.
One way a mathematician shows two sets are the same size is to match up the elements with each other. You know you have the same number of left socks as right socks if all of them are paired up and you have none left over. In the same way, we know the set with the elements {1,2,3,4} and the set with the elements {A,B,C,D} have the same number of elements because we can pair them up: 1 ↔ A, 2 ↔ B, 3 ↔ C, 4 ↔ D.
(If you don't know what a set is, it's basically just a formal way to describe what you're working with. We put all the numbers we're considering (the "elements") in brackets to make a "set.")
In the same way, we can pair up the integers with the even integers in these two rows:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 ...
2 4 6 8 10 12 14 16 18 20 22 24 26 28 30 32 34 36 38 40 ...
(We're only considering positive integers here for simplicity's sake but you can do something very similar to the negative integers.)
The rule here is just to double the first row to get the second and halve the second row to get the first. Every integer has one and exactly one corresponding even integer, and every even integer has one and exactly one corresponding integer, so they have exactly the same number of integers.
This does seem odd though. If you're looking at the number line, there are half as many even integers as integers in between 1 and 10, in between 1 and 100 and in between 1 and 1000... but the difference here is we're not looking at any given interval. We're allowed to continue our process all the way up to infinity, and that gives us the room we need to show that there are the same number of even integers and integers.
Keep in mind: We just know that these two sets have the same number of elements, but the even integers are still less dense than the integers. When you think about infinity, you have to think about correspondence and not about how it looks on a small scale.
Other Countable Infinities
The type of infinity that the integers and the even integers share is often called countable infinity. It's a kind of infinity that allows you to assign each element by some rule to a counting number 1, 2, 3, 4, 5... Any set that we can do this to is the same size of infinity as the integers and the even integers.
Here are some examples of sets we can do this to.
Negative integers: All integers: All decimals with only 1 decimal place:
1 ↔ -1 1 ↔ 0 1 ↔ 0.0
2 ↔ -2 2 ↔ 1 2 ↔ 0.1
3 ↔ -3 3 ↔ -1 3 ↔ -0.1
4 ↔ -4 4 ↔ 2 4 ↔ 0.2
5 ↔ -5 5 ↔ -2 5 ↔ -0.2
6 ↔ -6 6 ↔ 3 6 ↔ 0.3
What About the Fractions?
Here's something that might blow your mind a little bit. We can even prove that there are the same number of fractions as positive integers.
Remember: All we have to do is show that there's a systematic way to assign each fraction to the counting numbers (1,2,3,4...) so every fraction has a place. Can you come up with a good strategy?
Here's a brilliant visual argument from the pioneering days of infinity:
Do you see it? All fractions can be expressed as a ratio of two integers, so we can build a grid with all possible numerators along the top and all possible denominators along the bottom. Then, there's a way to zigzag along the array and assign each fraction to a counting number. This zigzag will hit every single spot on the grid as it stretches out to infinity, so every fraction has a corresponding space on the list.
Here's the correspondence:
1 2 3 4 5 6 7 8 9 ...
1/1 1/2 2/1 3/1 1/3 1/4 2/3 3/2 4/1 ...
One thing you might notice about this particular setup is we have some repeated fractions we must skip over. 1 = 1/1 = 2/2 = 3/3, so we give 1/1 a spot on our list (spot 1), but we skip over 2/2 and 3/3 so that we correspond each integer with a unique fraction. This rule of zigzagging and removing equivalent fractions is less straight forward than some of the ones we have earlier, but it works just as well!
One other thing you might notice is that this is the same argument as my previous article when we had an infinite number of buses each with an infinite number of guests. I said we could assign each guest to a new room in the hotel by zigzagging across a grid of the guests, and that's exactly the same principle here. Since the hotel had labeled room numbers, it represented countable infinity, and the fractions all have a home there as well. (This argument is actually where I got inspiration for that one!)
It turns out that the fractions (aka rational numbers) are the same infinity as the integers! Again this does seem a little odd. After all, the fractions are so dense that we can find a new fraction between any two we have (just average them!) This is a testament to just how odd infinity behaves.
Some Infinities Are Uncountable!
Ok, so far all we've been talking about is infinities that are the same size. We've recapped why the even integers are equivalent to the integers, which you may have seen last week, and extended it to all sorts of sets that end up being equivalent, including fractions. All of these infinities are countable, meaning they're equivalent to 1,2,3,4, etc. These infinities are also called listable because you can construct a list where every element of the set has a place on the list, as we did earlier with the negative integers and all integers.
But what if there's an infinity that isn't countable? What if no matter what list we make, we can find a number we missed?
It turns out that that's what happens with the real numbers. And that means their size is not countable infinity but a larger infinity!
The argument I'm about to show is Cantor's Diagonal Argument. Georg Cantor was a German mathematician. He was famous for work in set theory and imaginary numbers, and most importantly for us, infinity!
Here's how it goes.
First, let me just refresh your memory. A real number is any number that can be expressed with a decimal expansion. Every fraction and integer is a real number but so are irrational numbers, like the square root of 2 and pi. Fractions have a decimal pattern that repeats, whereas a real number can have any sort of decimal expansion. (Here's a link if you'd like to learn why fractions have repeating decimal patterns, but it is rather complex math so you've been warned.)
We're going to argue by contradiction. This means that we're going to assume that we can create a complete list of all the real numbers and then we're going to show that no matter how the list is constructed, we're missing a number somewhere and therefore the list isn't complete.
So here's an example of a complete list of real numbers:
1. 0.111111111111111111....
2. 0.26548653168...
3. 2.8212554125214...
4. 0.567567567567...
5. 3.1415926535897...
and so on.
We assume that somewhere on this list we have every single possible real number.
But look at this:
1. 0.111111111111111111....
2. 0.26548653168...
3. 2.8312554125214...
4. 0.51751751751751...
5. 3.1415926535897...
We formed a diagonal by looking at the 1st digit of the 1st number, the 2nd digit of the 2nd number, the 3rd digit of the 3rd number and so on. Now imagine, we took every digit we highlighted and added one to it and put it into a new number.
Here, we would get:
1.3486...
To recap, the 0 in the first number became the 1 in our new number, the 2 in the second number became the 3 in our new number, the 3 in our third number became the 4 in our new number and so forth.
Is this new number on our list?
Well, our new number is not the first entry in our list because its first digit is different than the first digit of the first entry. It's not the second entry in our list because its second digit is different than the second digit of the second entry. And it's also not the nth entry for any n because its nth digit is different than the nth digit of the nth entry.
Guess what that means? Our new number cannot be any entry on our list, so it's not on our list!
Therefore, whatever list of real numbers we decide to make, we're missing at least one element (and actually we're missing infinite elements!) Therefore, the real numbers are not listable! So their infinity is larger than the infinity of the integers!
What you've just seen was one of the most incredible realizations of math in the 19th century. Until this time, a lot of mathematicians thought that infinity was infinity and that was it. You can't go farther than forever. But it turns out you can!
The countable infinity is often called aleph-null, which looks like this:
It turns out that mathematicians don't know whether the infinity of reals is the next size of infinity or if there's a size between the reals and the integers. This, like so many questions about infinity, is an open question in mathematics.
I've having so much fun talking about infinity that I'm going to write one more article in this series! We're going to be talking about what happens when infinity meets geometry, with fractals like this one:
This is called Koch's Snowflake and it's constructed by pressing out the middle of the side of each equilateral triangle an infinite number of times. The end result: A shape that has a finite area but an infinite perimeter! This shape is actually my profile picture for this site, so that's what that is if you're wondering.
We're also going to be talking about the object that made Georg Cantor go mad! (Well maybe his insanity was a combination of things, but this certainly contributed!)
Make sure to tune in next week for that!
Also, let me know in the comments if you have any questions. I really tried to break down the more formal proof side of infinity with these famous arguments, but that is often difficult to write about, so feel free to leave me some feedback!
Here are some resources if you'd like to learn more:
This blog talks through many of the same concepts I do: https://manybutfinite.com/post/counting-infinity/
I love this video:
This video is also amazing. Vsauce goes into a lot more detail than I ever could in an eight-minute blog post, and he even discusses one of the most famous unsolved problems about infinity: The Continuum Hypothesis.
And here's another great video:
Infinity is one of the most fascinating topics to mathematicians and there are so many other resources online, so just google for more!
I'll end this article with a fun monkey "theorem":
You now know everything you need to know to figure out why this works!