I hope you all had a great Thanksgiving! I took a break from blogging last week because of the holiday, but I'm back, and I have some exciting content for you today. We're going to talk about infinity!
When you think about infinity, what do you think about? Do you consider the ever-expanding universe, the eternity of time or the fact that no matter how high you count, there seems to never be a "last" integer?
All of these ideas are completely mind-boggling, and today I'm going to give you a taste of the weird way infinity behaves with a thought experiment.
Imagine you're the owner of a hotel with an infinite hallway and an infinite number of rooms, each numbered with a given number: 1,2,3,4, etc.
One day, you have a new guest show up, but the hotel is already full. There is a guest in every single one of your infinite rooms, so where do you make room for your new guest?
Simple. You move the guest in Room 1 to Room 2, the guest in Room 2 to Room 3, and each guest in Room n to Room n+1, and you put your new guest in Room 1. Each of your infinite guests still has a room and the new guest does too! If there were a finite number of rooms, the last guest would have nowhere to go, but you don't have a last guest so everybody finds a room!
This scheme actually works for any finite number of guests. If ten new people show up, move the guest in Room 1 to Room 11, the guest in Room 2 to Room 12 and every guest in Room n to Room n+10. If a million guests show up, move the guest in Room 1 to Room 1,000,001, the guest in Room 2 to Room 1,000,002 and every guest in Room n to a million and n.
In this way, it seems like you accommodate any number of guests in your infinite hotel, but what if an infinite number of guests arrive?
The next day, an infinite bus rolls up to your hotel. All the people line up outside your hotel and ask for rooms. Can you deal with this?
The trick this time is to move your infinite number of guests in such a way that there are now an infinite number of empty rooms. Let's do this. Move the guest in Room 1 to Room 2, the guest in Room 2 to Room 4, and every guest in Room n to Room 2n. These leaves all the even numbers filled and all the odd numbers open, so you can simply assign each new guest to each odd number in order.
Each old guest has a room assignment, and each new guest also has a room assignment! So you can accommodate an infinite number of guests too!
At this point, your hotel seems invincible, but let me throw another challenge at you. What if an infinite number of buses, each with an infinite number of guests, drive up to your hotel?
This is going to require a bit more brilliance, so I want to give you a chance to reflect on this before you continue reading this blog post. Remember that you have to give each guest a concrete instruction as to what room they need to end up in. It also helps if you number each bus Bus 1, Bus 2, etc and each seat in each bus Seat 1, Seat 2, etc. Go ahead! Think about it!
Have you come up with a solution? I'm going to talk you through two potential answers, but there are several different ways to do this, and you may have come up with something entirely different (but still valid) to what I'm going to show here.
Solution 1: Primes!
First, let's go ahead and move the infinite guests that are already in the hotel to the even numbers like we did before. The guest in Room n moves to Room 2n, and we're left the infinite number of odd rooms to work with.
For the first bus, assign the guest in Seat 1 to Room 3, the guest in Seat 2 to Room 3^2=9, the guest in Seat 3 to Room 3^3 = 27, and every guest in Seat n to Room 3^n. All these rooms are open because they're all odd, so every guest in the bus gets a room.
For the second bus, assign the guest in Seat 1 to Room 5, the guest in Seat 2 to Room 5^2=25, the guest in Seat 3 to Room 5^3=125, and every guest in Seat n to Room 5^n. All these rooms are open because they're all odd and they are powers of five, not powers of three, so they're available.
We repeat this same scheme for every single bus with a new prime number, giving the third bus the assignment 7^n for seat n, the fourth bus the assignment 11^n for seat n, and so on. In general, you give Bus M the assignment p^n where p is the (M+1)st prime number. The powers of one prime are unique from the powers of another, so all these seats are open.
We know that we're not duplicating any rooms because of the Fundamental Theorem of Arithmetic, which says that every integer has a unique prime factorization. We're giving our guests integers with the prime factorization that is the power of a prime, and they're all different, so all of our integers are different.
There are an infinite number of primes, so there will be an assignment for every bus! (I don't have room to show you the proof of the infinitude of primes here, but it's actually one of my favorite bits of math of all time, so I'm hoping to include it in my next blog post!) For now, check out this link: https://www.youtube.com/watch?v=ctC33JAV4FI
There are some interesting things about this particular solution. It turns out that you're not filling every room. For the odd rooms, you're only filling the rooms that represent powers of primes, not those that have more than one prime as a factor. For example, Room 15, 21 and 35 are never filled, and it turns out Room 1 is not either, but somehow this idea still works, and everybody gets a concrete assignment!
There is however something a little unsatisfying about this solution because some rooms are left empty, so let me give you an alternative idea.
Solution 2: Let's Draw It!
What if there's a way to assign the infinite buses and their seats in an order that gives them labels of 1,2,3,4, etc? Then, all we'd have to do is repeat the process we originally had for an infinite number of guests showing up at our hotel: move the current guests to the even numbers and have the new guests fill in the odd numbers!
It turns out there is a way to do that with a diagonal set-up and I made this visual for you to show you how that works. (Sorry if it's a bit messy!)
The buses and their infinite seats essentially form an infinite grid with bus number on one side and seat number on the other. We start at the top left corner and zigzag our way across the diagonals to give each person a number. You can imagine this strategy continuing across the whole grid.
There is actually a way to give a formula for this in terms of bus number and seat number but I think it's a lot more satisfying to just look at the visual.
Now, all we have to do is move our current guests to the even numbers and give each of these guests an odd seat assignment!
Each guest now has a room number, and even more satisfyingly, every single room is filled with a guest!
We can even continue this to more levels of infinity. There's a way to extend both of these strategies towards this situation: What if an infinite number of ships arrive, each carrying an infinite number of buses, each of which has an infinite number of guests? The infinite hotel can accommodate three layers of infinity in this way. It can even stretch to hold four layers, five layers and any number of finite layers.
We unfortunately can't always hold an infinite number of layers of infinity, but hey, this hotel is still pretty incredible! (As long as we ignore the fact we can't possibly fit this hotel on the planet, let alone get all these people room service and free WiFi)
This thought experiment was devised by the famous mathematician, David Hilbert, who paved the direction of mathematics into the nineteenth century by posing a list of important problems for mathematicians to tackle, and he also worked with many neat branches of the subject, including infinite geometries! For that reason, you'll often see this problem called Hilbert's Hotel.
Now that I've laid the groundwork and given you a bit of intuition for the wacky world of infinity through the hotel thought experiment, I'm going to continue this subject next week! We're going to discuss some of the most fascinating and beautiful proofs associated with infinity from Euclid's infinitude of primes to the fact that some infinities are different sizes than others. It turns out that if you had a guest labeled with every possible fraction, they would fit in this infinite hotel, but if you had a guest with every possible real number, they couldn't fit! Make sure to come by next week and check that out! (Who knows? I might even discuss the problem that made infinity pioneer Georg Cantor go insane!)
Here are some great resources on Hilbert's Hotel that may just explain it better than I did:
Here's another video: https://www.khanacademy.org/partner-content/wi-phi/wiphi-metaphysics-epistemology/wiphi-metaphysics/v/sizes-of-infinity-part-1-hilberts-hotel
And this is the best article I've found about this problem: https://plus.maths.org/content/hilberts-hotel
There's also an absolutely wonderful book written by Eugenia Cheng, one of my favorite authors, called Beyond Infinity: An Expedition to the Outer Limits of Infinity, so check that out if you want to learn even more!
If you have any questions, just ask in the comments section! Infinity can get pretty abstract, so I'd love to clarify anything about this post or answer any questions in general!