Tag Archives: set theory

## The fault in “The Fault in Our Stars” (Cantor’s diagonalization argument)

8 Jul

I love The Fault in Our Stars- I’ve read the John Green book three times and my husband and I have discussed at length how much we like it.  We just watched the movie last weekend and thoroughly enjoyed it (not as much as the book, but it’s a tough act to follow).

There’s just one little thing wrong in it-a bit of math!  Both my officemate and my fairy blogmother have posted on social media about a flaw in something that Hazel says, so I thought I’d take a post to explain both a) why Hazel is wrong and b) how the argument that she refers to works.  For the record, I believe that c) it’s fine for teenagers in books to not fully understand these sorts of mathematical arguments, and it’s unclear whether John Green believes that the infinity between [0,1] is the same “size” as the infinity between [0,2] or not.  This is true and is what we will show, but Hazel says (beautifully) in the book:

There are infinite numbers between 0 and 1. There’s .1 and .12 and .112 and an infinite collection of others. Of course, there is a bigger infinite set of numbers between 0 and 2, or between 0 and a million. Some infinities are bigger than other infinities… I cannot tell you how grateful I am for our little infinity. You gave me forever within the numbered days, and I’m grateful.

Makes me tear up a little every time.  And not because the math is wrong, but because the writing is so pretty.  But the math is, in fact, wrong.  All those infinite sets are the same size.  But she is right that some infinities are bigger than others.

Speaking of math, I’ll do just a little bit more reminiscing before we dive in.  During my sophomore year of college, I took Set Theory with the other two math and philosophy majors (some of my now-best friends) and we saw this argument for the first time.  Blew.  My.  Mind.  This is also one of my two cocktail party math tricks (I’ve already written about my other one).  I’m not that fun at cocktail parties.

So.  Let’s talk about sizes, shall we?

Let’s first talk about finite counting.  How do I know that I have three potatoes?  I look at the potatoes and I assign a number to each one.

These potatoes are hiding their sadness- not enough eyes compared to their peers.

Another way to say this is that I have written a bijection between my set of potatoes and the set {1,2,3}.  That is, a function from one set to the other so that each item in set A gets assigned to exactly one item in set B (1), and so that each item in set B has someone assigned to her (2).  Property 1 makes a function injective, and property 2 makes a function surjective.  If your function is both injective and surjective, we say that it’s bijective.  One way to imagine a function is lining up all the items of your sets next to each other, and drawing a back-and-forth arrow between the items of the set.

These po’ taters… these smiles are hiding so much pain

And we can do this for any finite set.

Click photo for credit. I see a bijection to the set {1,…,14}, so there are 14 bunnies.

So far so good, this is just normal counting.  But what about counting to infinity?  Is there more than one kind of infinity?  (Spoiler alert: yes).  How could we know?

To deal with infinity, we extend how we count from finite sets.  We say that two sets are the same size if there exists a bijection between them.  For instance, the set of bunnies and the set of potatoes are not the same size, because there is no bijection between them.  I can see that by trying to make a bijection between A={1,2,3} and B={1,2,3,4,5,6,…14}.  No matter how I assign a number to 1, 2, and 3, there are still 11 numbers in set B that aren’t assigned a number in set A.  So I can’t have a surjection, therefore I can’t have a bijection, therefore A and B are different sizes, ergo the size of the bunny set is not the same size as the potato set.

Technical aside: if there is a bijection between sets A and B, and another one between sets B and C, you can put them together and get a bijection between sets A and C.  This jives with our intuition that if A and B are the same size, and B and C are the same size, then so are A and C.  “Being the same size” is an example of an equivalence class, a math term that we may use in the future (but not right now, so no formal definition just yet).

Here’s a first example of playing with infinity.  I claim that the set of natural numbers {1,2,3…} is the same size as the set of even natural numbers {2,4,6…}.  Proof by (completely unnecessary) picture

Eye just like putting eyes on things

This is our first idea of infinity.  In fact, we use this infinity so much that we have a word for when a set is the same size as the natural numbers: we say that set is countable.  Here’s the next question to ask: are all infinite sets countable?  Is there an infinite set which isn’t countable?  Or as Hazel puts it, are there some infinities that are bigger than others?

Here’s where Georg Cantor’s ingenious argument (from the 1870s) comes in.  Let’s try to see if the numbers between 0 and 1 are countable.  We’ll do so the same way we tried to see if there were the same number of bunnies and potatoes: start building a bijection, and come up with a contradiction.

Fact: every number between 0 and 1 can be written uniquely as an infinite decimal expansion.   By infinite, here, we mean countable.  Examples: 1/100=0.010000000…. 1/3= 0.33333333….. 1/11=0.09090909090….

So let’s start building our bijection by putting the natural numbers on the left, and infinite decimal expansions on the right.  I started with these examples here:

Assume I have finished building my bijection and have a list of all the natural numbers on the left, and the numbers between 0 and 1 on the right.  We’re going to build a number between 0 and 1 that doesn’t show up on this list.  This proves that our assignment function isn’t surjective, and therefore isn’t a bijection.  And our argument will hold for any way that you try to build a bijection, and so it’ll show that there are in fact no bijections between the two sets.

How do I build the number?  Let’s look at the first coordinate in its decimal expansion.  I look at the first number in my list, 0.01000000, and look at its first coordinate: it’s a “0”.  So we’ll assign any digit besides 0 to the first coordinate in our special number.  Let’s say it’s 1.  So far, my number is 0.1_________.

Now let’s look at the second coordinate.  I look at the second number on my list, 0.3333333333, and its second coordinate: it’s a “3”.  So let’s make our second coordinate a 4.  Now my number is 0.14______.

Third: I get 0.141________________

I keep going.  To make my ith coordinate, I look at the ith number in my list, and the ith coordinate of that number.  Then I pick any digit which is not that one, and assign it to my ith coordinate.

Now let’s say we’ve finished building our special number coordinate by coordinate.  Is it somewhere in our list?

Think about it for a second…

….

Answer: no!  If our special number were on our list, it’d have to be assigned to some natural number n.  But by the very way we built our special number, its nth coordinate is not the same as the nth coordinate of the number assigned to n.  So it can’t be on the list.  So our special number, which by construction lies between 0 and 1, is not in the image of our function.  So our function isn’t a surjection, and hence it isn’t a bijection.

This means that we do have more than one infinity: the infinity in [0,1] is not the same size as the infinity in {1,2,3….}.  Some infinities are bigger than others.  (we finished goal b)

But some aren’t. (goal a).  In particular, the bijection we did earlier between the sets {1,2,3…} and {2,4,6…} works to show that the infinity between 0 and 1 is the same size as the infinity between 0 and 2.  That is, $x \mapsto 2x$ is both injective and surjective.  Also, $x\mapsto 1000000x$ is also a bijection, so the infinity in [0,1] is the same size as the infinity in [0,1000000].  Sorry Hazel, you’re wrong in your example (but the idea is correct!).

I hope you’re enjoying a little bit of infinity in your day!  (Actually, a lot of infinity.  Or at least, uncountably much.)