Infinity and Logic

Last Saturday, we had two speakers Eric Brattain (me, our organizer) and Patrick Weed.


I spoke about a topic usually called countability. This is actual a fairly terrible name since it’s about precisely that which can’t be counted in the usual sense, infinite quantities of things. We used the classic example of the Hilbert Hotel to get a feeling for how to map infinite sets into each other.


Imagine a hotel where the rooms are numbered 1,2,3,4,… and for every whole number, there’s a room labeled with that number (maybe in very small font). Now, suppose that when you arrive, the hotel is full! Well, no problem! You can simply request that the hotel manager scoot everybody down one room, 1->2, 2->3, etc. Then, room #1 is available for you! This means that there are not more numbers in the list 1,2,3,4,… than in 2,3,4,5,… which is a little strange.


Since that worked out so well, the next time you visit the Hilbert Hotel, you bring a busload of friends. They are sitting in seats numbered 1,2,3,4,… and for every whole number there is an occupied seat with that number. The hotel manager objects, saying that he can’t possibly have all of the guests march down the hallway forever. Besides, they’d never make enough room for everybody that way! Luckily, being a mathematical enthusiast, you know there’s a simpler way. Simply have each guest double their room number and go to that room. Then, only the even-numbered rooms will be occupied, and you and your party can take the odd-numbered rooms! Hurray! Once again, it’s a bit strange that there are no more whole numbers than there are even numbers. This kind of thinking leads to one of my favorite examples of mathematical ingenuity. We appear to have reached a paradox when we say a subset of numbers has no fewer numbers in it despite leaving some out (like the first one or even all of the odd numbers). What do we do? Declare that this is the definition of an infinite set! Bam!


The next day, you find the hotel manager arguing with somebody who has just brought another infinite busload of visitors. The problem is that the seats in the bus are numbered by fractions! For every fraction a/b, there is an occupied seat. The hotel manager claims that there are simply not enough rooms in the hotel, and it is full besides. The visitor objects that infinity is infinity, so if they accommodated your party, then they must be able to do so for hers. So, we know how to make infinitely many rooms available, but what instructions will allow each fraction-numbered passenger to know what room to go to?

To start, let’s assume they’re positive fractions, a/b, with a,b>0. If we pick a numerator and go through all possible denominators, then we end up with infinitely many… but there are infinitely many numerators to pick from! Infinitely many infinities? Uh oh! We need to be a little more clever. If we restrict our attention to fractions with a+b=n for some n>0, then we only have finitely many. For example, if n=2, then we have just 1/1=1. If n=3, then we get 2/1=2 and 1/2. For n=4, there’s 1/3, 2/2=1, and 3/1=3. There’s just n-1 numbers to consider. Notice that some numbers repeat, like 1/1 and 2/2. To make really good instructions, you’d have to keep track of this if the seats are all in the form of reduced fractions. I’ll leave that as an exercise for you. Basically, for each n, we assign the n-1 passengers with a+b=n to the next available n-1 hotel rooms.


An almost identical system lets you deal with an infinite number of infinite busloads all at once! Check out the picture below from an old NYtimes column by Strogatz.


Now we reach a much deeper conundrum. Yes, it gets deeper than infinity infinities is still infinity. One dark and stormy night, a shuttle arrives where the seats are numbered by decimal numbers, a.k.a. real numbers, like \pi, \sqrt{2}, etc. What clever way can we provide these people with hospitality? There is no way! Contemplate this:


No matter how you assign the passengers (imagine the list above as being who goes to room 1,2,3,…), I can always find at least one that is left out despite your claim that you have them all. So… some infinities are bigger than others! Well, no problem. Send the bus down the road to Cantor’s Paradise Resort with rooms labeled by colors. Exercise: Why did that last sentence sort of make sense?


Can you find sets that are bigger than the real numbers? For those of you who’ve held on this long, here’s a little tidbit to knock you off the rails. Is there a set with more elements than 1,2,3,… but less than the decimals? Why or why not? It turns out that the answer to this question is fundamentally undecidable. Math doesn’t always have the answers!

By the way, this wondrous madness came from the mind of Georg Cantor:


If you like this infinity stuff, I highly recommend the graphic novel Logicomix: An Epic Search for Truth.

Speaking of logic, Patrick Weed gave you an entertaining introduction to symbolic logic. Doing serious math or programming without knowing symbolic logic is like deciding to be a writer without knowing basic grammar. No, most writers don’t get excited about grammatical details, but they sure do know them well enough to make jokes about those who don’t.


Here’s a copy of the handout that he provided. Patrick Weed’s Math Circle on Logic

Also, there was some talk of how to map a line onto a plane. By onto, I mean so that every point in the plane is hit by a point from the line. This seems impossible, but if you ponder this illustration of a Hilbert curve, then it will still seem impossible. But it works! :-p