How big is infinity? - Dennis Wildfogel
When I was in fourth grade,
my teacher said to us one day:
"There are as many even numbers
as there are numbers."
"Really?", I thought.
Well, yeah, there are
infinitely many of both,
so I suppose there are
the same number of them.
But even numbers are only part
of the whole numbers,
all the odd numbers are left over,
so there's got to be more whole numbers
than even numbers, right?
To see what my teacher was getting at,
let's first think about what it means
for two sets to be the same size.
What do I mean when I say
I have the same number of fingers
on my right hand as I do on left hand?
Of course, I have five fingers on each,
but it's actually simpler than that.
I don't have to count, I only need to see
that I can match them up, one to one.
In fact, we think that some ancient people
who spoke languages that didn't have words
for numbers greater than three
used this sort of magic.
For instance, if you let
your sheep out of a pen to graze,
you can keep track of how many went out
by setting aside a stone for each one,
and putting those stones back
one by one when the sheep return,
so you know if any are missing
without really counting.
As another example of matching being
more fundamental than counting,
if I'm speaking to a packed auditorium,
where every seat is taken
and no one is standing,
I know that there are the same number
of chairs as people in the audience,
even though I don't know
how many there are of either.
So, what we really mean when we say
that two sets are the same size
is that the elements in those sets
can be matched up one by one in some way.
My fourth grade teacher showed us
the whole numbers laid out in a row,
and below each we have its double.
As you can see, the bottom row
contains all the even numbers,
and we have a one-to-one match.
That is, there are as many
even numbers as there are numbers.
But what still bothers us is our distress
over the fact that even numbers
seem to be only part of the whole numbers.
But does this convince you
that I don't have
the same number of fingers
on my right hand as I do on my left?
Of course not.
It doesn't matter if you try to match
the elements in some way
and it doesn't work,
that doesn't convince us of anything.
If you can find one way
in which the elements
of two sets do match up,
then we say those two sets have
the same number of elements.
Can you make a list of all the fractions?
This might be hard,
there are a lot of fractions!
And it's not obvious what to put first,
or how to be sure
all of them are on the list.
Nevertheless, there is a very clever way
that we can make a list
of all the fractions.
This was first done by Georg Cantor,
in the late eighteen hundreds.
First, we put all
the fractions into a grid.
They're all there.
For instance, you can find, say, 117/243,
in the 117th row and 243rd column.
Now we make a list out of this
by starting at the upper left
and sweeping back and forth diagonally,
skipping over any fraction, like 2/2,
that represents the same number
as one the we've already picked.
We get a list of all the fractions,
which means we've created
a one-to-one match
between the whole numbers
and the fractions,
despite the fact that we thought
maybe there ought to be more fractions.
OK, here's where it gets
really interesting.
You may know that not all real numbers
-- that is, not all the numbers
on a number line -- are fractions.
The square root
of two and pi, for instance.
Any number like this is called irrational.
Not because it's crazy, or anything,
but because the fractions are
ratios of whole numbers,
and so are called rationals;
meaning the rest are
non-rational, that is, irrational.
Irrationals are represented
by infinite, non-repeating decimals.
So, can we make a one-to-one match
between the whole numbers
and the set of all the decimals,
both the rationals and the irrationals?
That is, can we make
a list of all the decimal numbers?
Cantor showed that you can't.
Not merely that we don't know how,
but that it can't be done.
Look, suppose you claim you have made
a list of all the decimals.
I'm going to show you
that you didn't succeed,
by producing a decimal
that is not on your list.
I'll construct my decimal
one place at a time.
For the first decimal place of my number,
I'll look at the first decimal place
of your first number.
If it's a one, I'll make mine a two;
otherwise I'll make mine a one.
For the second place of my number,
I'll look at the second place
of your second number.
Again, if yours is a one,
I'll make mine a two,
and otherwise I'll make mine a one.
See how this is going?
The decimal I've produced
can't be on your list.
Why? Could it be, say, your 143rd number?
No, because the 143rd place of my decimal
is different from the 143rd place
of your 143rd number.
I made it that way.
Your list is incomplete.
It doesn't contain my decimal number.
And, no matter what list you give me,
I can do the same thing,
and produce a decimal
that's not on that list.
So we're faced with this
astounding conclusion:
The decimal numbers
cannot be put on a list.
They represent a bigger infinity
that the infinity of whole numbers.
So, even though we're familiar
with only a few irrationals,
like square root of two and pi,
the infinity of irrationals
is actually greater
than the infinity of fractions.
Someone once said that the rationals
-- the fractions -- are
like the stars in the night sky.
The irrationals are like the blackness.
Cantor also showed that,
for any infinite set,
forming a new set made of
all the subsets of the original set
represents a bigger infinity
than that original set.
This means that,
once you have one infinity,
you can always make a bigger one
by making the set of all subsets
of that first set.
And then an even bigger one
by making the set
of all the subsets of that one.
And so on.
And so, there are an infinite number
of infinities of different sizes.
If these ideas make you
uncomfortable, you are not alone.
Some of the greatest
mathematicians of Cantor's day
were very upset with this stuff.
They tried to make these different
infinities irrelevant,
to make mathematics work
without them somehow.
Cantor was even vilified personally,
and it got so bad for him
that he suffered severe depression,
and spent the last half of his life
in and out of mental institutions.
But eventually, his ideas won out.
Today, they're considered
fundamental and magnificent.
All research mathematicians
accept these ideas,
every college math major learns them,
and I've explained them
to you in a few minutes.
Some day, perhaps,
they'll be common knowledge.
There's more.
We just pointed out
that the set of decimal numbers
-- that is, the real numbers --
is a bigger infinity
than the set of whole numbers.
Cantor wondered
whether there are infinities
of different sizes
between these two infinities.
He didn't believe there were,
but couldn't prove it.
Cantor's conjecture became known
as the continuum hypothesis.
In 1900, the great
mathematician David Hilbert
listed the continuum hypothesis
as the most important
unsolved problem in mathematics.
The 20th century saw
a resolution of this problem,
but in a completely unexpected,
paradigm-shattering way.
In the 1920s, Kurt Gödel showed
that you can never prove
that the continuum hypothesis is false.
Then, in the 1960s, Paul J. Cohen showed
that you can never prove
that the continuum hypothesis is true.
Taken together, these results mean
that there are unanswerable
questions in mathematics.
A very stunning conclusion.
Mathematics is rightly considered
the pinnacle of human reasoning,
but we now know that even mathematics
has its limitations.
Still, mathematics has some truly
amazing things for us to think about.
