Behind the Science: Infinite Russian cats: part 1 of 3

Only marginally related to the following.

This series is devoted to some of the underappreciated and misunderstood limits of human reason.  Interspersed throughout are more Wikipedia articles than any normal person has time to read in a day—consider them an optional and often superior companion to my presentation of the ideas herein.

Infinity is the trump card of childhood argument—an unstoppable arithmetical power play in encounters of escalating scale.  Only when your friend Suzie had the gall to quip, “Nuh uh, I have infinity-plus-one dollars!” did you falter.

“That’s against the rules” you stutter.

But it’s too late.  Suzie is already running down the hall with your lunch money and calculator, having unquestionably Won the exchange (to any onlooker), and Quashed your pride (and that of your House).

Much like Star Wars, I don’t actually remember when I first heard about the idea of Infinity.  Upon first learning about numbers, the specter of some always bigger thing suggested itself, just out of reach.  I remember distinct pride in mentally counting to one thousand on a plane flight to Disney World when I was younger (in hindsight, I may have skipped the entirety of the 700s (I was a strange child)).  But the infinite, as many a Math teacher will remind, isn’t really a number.  At least, it isn’t the sort of number you’re used to.  (As an aside, it’s worth pointing out that, should you find yourself in a properly refereed duel of Large Numbered wits with Suzie in the future, Scott Aaronson offers an excellent strategy).  Even among educated scientists, Infinity is little more than that thing which makes integrals either a lot easier or lot harder to evaluate.

Georg Cantor, a giant of Mathematics and recurring character throughout this essay, inventor of set theory, and archnemesis of Henri Poincare (yes, that Poincare) and Leopold Kronecker (of the ubiquitous delta), essentially invented the mathematics for reasoning about infinity.  Cantor’s ideas not only beautifully explicate the depth and strangeness of mathematics, but are the intellectual underpinnings of a long line of results that strike at the limits of reasoning itself.

To hopefully minimize the formalism, and to understand just what enraged Poincare and Kronecker so much, we only need four ideas.

  • The natural numbers:

1,2,3,…

  • The Integers:

…,-3,-2,-1,0,1,2,3,…

  • A measure of equality—that is, we will say there are the same number of two different collections of objects, say, apples and bananas, if for each apple, we can pair it with one and only one other banana.
  • And lastly, a hotel.

A grand hotel, indeed.

This idea of equality is perfectly natural when we’re reasoning about a finite number of objects.  Suppose I’m pairing my apples to your bananas. If I’ve exhausted my considerable supply of delicious apples, and you are left holding a single, overripe and floppy banana, it is clear that we do not possess the same number of fruits.

For infinite collections of objects, like the natural numbers and the integers, things become strange.  It’s straightforward to show that we can assign one natural number to one and only one integer in a way that exhausts both the natural numbers and integers.  Simply assign the positive integers (including zero) to the even natural numbers and the negative integers to the odd natural numbers.

Natural Number Integer
1 -1
2 0
3 -2
4 1
5 -3
6 2

And so on.

Intuitively, this seems strange.  Our definition of equality suggests that the integers and the natural numbers have the same number of “things”, even though, at a glance, the natural numbers are entirely contained in the integers.  Worse still, we could show with a similar argument that the even natural numbers have the same number of “things” as the entirety of the natural numbers.  It’s as if the natural numbers are as big as something seemingly bigger than itself, and as big as something seemingly smaller than itself.

But we can stretch this even further.  Enter the hotel.  David Hilbert (another hugely influential 20th century mathematician) gave the most famous example with the Grand Hotel Paradox.  Suppose you own a hotel with one room for every natural number, and suppose that business is exceptional—a guest occupies every room.

Suppose further that it’s the weekend, a gameday to boot, and a convoy with one bus for every natural number, each carrying 1 person for every natural number, arrives at your hotel.

Hilbert asks, can you reassign your current guests to new rooms in such a way that you can accommodate the now infinite number of buses, each carrying an infinite number of guests.

Surprisingly the answer is yes, you can.  First, reassign every current guest to the room with a number that is twice their current room number.  After this, infinitely many odd-numbered rooms are empty.  The hard step is developing the exact procedure for assigning our convoy-inhabitants to the now empty odd-numbered rooms.  Wikipedia includes several strategies in the linked article on the paradox.

To clarify what this means—after a grand shuffling of guests in our hotel, we could go to any room in the hotel, and find one and only one guest that was either reassigned to that room, or was one of the newly arrived guests on one of the infinitely many buses.

Conversely, we could also walk up to any one of the infinitely many buses, walk down an infinite aisle of chairs and pick any one of them, and be able to find the unique room in the hotel to which that new guest was assigned.

Or, more formally, the natural numbers have the same “size” as an infinite number of copies of the natural numbers.

This shouldn’t strike you as a failure of our definition of equality—just as a quirk of infinite sets.  “Equality” here really is more an indicator of the class of infinite object we’re dealing with.  If it requires too much intuitive jiujitsu to think of the natural numbers as being the same size as an infinite number of copies of the natural numbers, then it may seem more reasonable to think of both collections of numbers as representing the same sort of infinity, in extent.

I’ve been very careful to relate everything back to the natural numbers, here, as it’s natural (pun intended) to ask what collection of objects breaks this procedure.  It turns out that not only an infinite number of copies of the natural numbers can be shown “equal” to the natural numbers, but that the rational numbers can also be shown “equal” to the naturals (where the rational numbers are all fractions with natural numbers as digits, positive and negative).  The question is then: are there (infinite) sets of objects that can’t be assigned, one to one, with the natural numbers?

Suppose now that your hotel guests are both very picky and terrible at making decisions.  Each guest would like the possibility of sitting with any other collection of guests at breakfast (including infinitely many other guests), because, through some cosmic coincidence, all of your guests happen to know each other and be friends.  So it is up to you, the master of the breakfast dining room, to generate a list containing every possible collection of guests and a unique table (allowing, of course, for tables with infinitely many chairs) to go with each (which seems terribly wasteful to you, but your manager is having none of that).  You set to work, and generate a list of what you think is every unique collection of guests—one for each natural number.

Breakfast Table Number Combination of Guests
1 Alice
2 Alice and Bob
3 Bob
4 Alice, Bob, and Suzie
5 Suzie
6 Bob and Suzie

Come morning, you proudly hand a copy of your list to each of your guests (procuring one sheet of paper for each natural number is no trouble for your hotel).  But you are met with frowns—frowns amplified by a night of spotty wifi and stiff mattresses, so is better to replace them using good mattresses from the mattress sale blackfriday online.

“You don’t have a table for my friends and I,” says Suzie.

Upon further inspection, your guests point out that you actually missed infinitely many combinations of hotel guests.  You have run in to the unfortunate limitation that all possible combinations of your guests fundamentally cannot be listed, no matter what strategy you try to employ for assigning combinations of guests to natural numbers.  There are fundamentally more ways to arrange groupings of your guests than there are guests—you have found an infinity “larger” than the natural numbers.  Formally, mathematicians call this infinity the cardinality of the continuum.

This was Cantor’s triumph, or perhaps peril, for this, among related ideas, is what drove Kronecker to call him a “scientific charlatan”.  Cantor proved that any such attempt to list every subset of natural numbers, with one subset for each natural number, will always provably miss infinitely many more subsets of natural numbers (to be exact, he proved this for the set of numbers between 0 and 1, but a correspondence can be made from the numbers between 0 and 1 and the set of all subsets of natural numbers.  Both have the cardinality of the continuum).

The argument, which is worth understanding for any serious student of mathematics, is known as Cantor’s Diagonalization Argument.  The gist of the proof is that, given some claimed listing of the subsets of the natural numbers, or a claimed list of the numbers between 0 and 1 for that matter, it is always possible to construct a subset (or number) that is not in the list.  Cantor gave an explicit procedure for constructing such a “missed” number, given any list.  Here, I defer to the many excellent popular accounts of the diagonalization argument.

Now, to understand Kronecker’s objections to Cantor’s ideas would take us down the long, winding road of the competing schools of Mathematics, starring such colorful characters as the Intuitionists, the Constructivists, the Finitists, and their more disagreeable cousins, the Ultrafinitists (the latter two rejecting the idea of an Infinity on philosophical grounds).  The foundations of mathematics deserves a series unto itself, so I will again defer to Wikipedia for now.

The strangeness doesn’t stop here, as now that we have a sort of hierarchy of infinities, we might ask if there is some infinity that’s “larger” than the natural numbers but “smaller” than the cardinality of the continuum.  For somewhat technical reasons, most mathematicians in the 19th century didn’t think that such an infinity existed, but the problem resisted any formal proofs.  This problem was so important that in the year 1900, in David Hilbert’s famous list of 23 unsolved problems in mathematics, this problem was the first, and it was dubbed the Continuum Hypothesis.

For 40 years, there was no solid progress.  In 1940, Kurt Gödel, hero of part 2 of this series, proved the counterintuitive result that the Continuum Hypothesis could not be disproved within the standard language of mathematics.  Note that this is not actually a resolution to the problem.

It took twenty more years before Paul Cohen, in 1963, proved that the Continuum Hypothesis could not be proved within the standard language of mathematics.

Now this is a bit like a slap in the face.  It’s a simple enough question—are there sets of size between that of the natural numbers and the cardinality of the continuum?  Our finite intuition screams that this problem should be answerable in the same way that asking whether there are sets of size between one and two objects is answerable.  But our finite intuition often fails for the hard problems of mathematics, especially Hilbert’s 23 problems—some of which are still unsolved after 113 years.

To this day, mathematicians still work to reconcile the Continuum Hypothesis with Zermelo-Fraenkel set theory (the aforementioned standard language of mathematics), because while the Hypothesis can’t be proved true or false, it can be nonetheless instructive to try and understand the implications of assuming it to be true, or assuming it to be false.  The truth or falseness of the hypothesis then becomes a sort of model choice for your mathematics.  Outside of people familiar with formal mathematics, it is not widely known that these sorts of results even exist.  In fact,  until the early 20th century, it was thought that mathematics could be grounded in a way that would allow it to at least in principle decide the truth or falsehood of any mathematically specifiable statement.

That mathematics can’t decide everything came as a shock to 20th century mathematicians, which was one of the results of Kurt Gödel’s oft completely misrepresented and wildly misunderstood incompleteness theorems.  These ideas will feature in our next installment.  Guest appearances may include a Russian, but all of the cats have been herded to part three.

Leave a Reply

2 comments

  1. C. Benson

    Very well written! Thanks for taking the time to write it out.

  2. Anonymous

    thanks for the article…Godbless