Let's ease into this by starting with a simple question: how can you show that

you have the same number of fingers as toes? Most people

would say, "ten fingers, ten toes, done." That's fine, but it brings in

an unnecessary concept; the actual *counting* of fingers and toes.

I only asked why the two sets had the same size, not to

actually count them. How else can one answer the question? By making

a one-to-one correspondence between the toes and fingers,

that is, pair up each finger with exactly one toe.

This connection shows that the two sets have the same size without counting.

By the way, since most people cannot touch their toes, please

do not try this unsupervised.

Although this pairing process seems strange, you're actually

already familiar with it, especially when the two sets are large:

whether you're counting left shoes and right shoes, nuts and bolts,

front and rear bike tires, or brides and grooms at a mass wedding,

the numbers always match up because these objects come in pairs.

So how do we compare the size of infinite sets?

If there is a one-to-one matching between two infinite sets,

we think of them as the same size. Mathematicians use the word

"cardinality" to describe how big a set is, but we'll just use

the word "size".

For example, the set of positive integers has the same size

as the set of all non-zero integers. How is this possible since the

first set fits into the second? After you've matched the positive

integers together, don't all the leftovers suggest that the

second set has a larger size? In fact, the second set seems to be

twice as large as the first set since each positive integer has a

corresponding negative integer. But the two sets actually have the

same size. We see this by arranging the elements in the second

set differently. Although the order of the numbers seems strange,

you can see that every non-zero integer will eventually appear,

and so there is a correspondence between the two sets.

A more devious example involves rational numbers, fractions which are

the ratio of two integers. The claim is that the rational numbers

also have the same size as the positive integers. Again, how can this be?

Even between zero and one there are infinitely many rational

numbers, so how can these two sets have the same cardinality?

Place rationals on a grid where the numerator is the same on each row

and the denominator is the same on each column. Now start at 1/1 and follow

the path, touching each positive rational number.

The first few rationals we hit are 1, 2, 1/2, 1/3, 3, 4, 3/2, and 2/3.

Note that some of the numbers have been crossed out. For example,

2/4 and 3/6 will be skipped over. That's OK because these numbers can

both be written in lowest form as 1/2. We want to pass through each fraction

exactly once so we eliminate these copies. The positive rationals

can thus be listed, so they have the same cardinality as the integers.

These ideas about the size of infinite sets were developed by

the German mathematician Georg Cantor. Everyone was surprised

by his ideas, including Cantor himself. When he realized that the set of points in

a square has the same size as the set of points on a line, his reaction

was “I see it, but I don’t believe it!”

While these ideas are considered mainstream by

today's mathematicians, they illicited different responses

from Cantor's contemporaries. Poincare considered his work a "grave disease" and Kronecker asserted

that Cantor was a "scientific charlatan", a "renegade",

and a "corrupter of youth". On the other hand,

David Hilbert strongly defended Cantor's ideas, declaring that

"No one shall expel us from the Paradise which Cantor has created."

These strong opinions seem more justified with the following

provocative question: Are there infinite sets which are NOT countable?

Such a set would be so big that we couldn't list the elements like we did

with the rational numbers. This would imply that there is more than one

kind of infinity.

To answer this question, let's talk about subsets. How many

subsets does the set S={a,b,c} have? Denoted by P(S), we call this the

power set of the original set S and we can easily list its elements.

To generate the subsets, it's simply a matter of noting that

each element is either in a subset or not, making 2^3 or 8

possibilities. We can do the same for other sets and note that

if there are n distinct objects in a set S, its power set P(S) has size 2^n.

Clearly the size of the power set is larger than the original set.

How does this relate to infinite sets? Cantor showed that

for ANY set S --- infinite or not --- the power set P(S) always

has a larger size than the original set S. This means that the power set of the positive

integers is uncountable, or loosely speaking, its size is a larger

infinity.

If that doesn't shock you, let's see a truly mind blowing idea,

but please don't watch this with small children present.

Let S1 represent the positive integers and S2 its power

set. Now let S3 be the power set of S2, an even larger infinity,

then let S4 be the power set of S3, a larger infinity still.

Of course we can keep taking power sets and thus produce a larger infinity

each time. This all implies a really bizarre fact:

there are infinitely many different kinds of infinity.

There's a lot more one can say about different infinities, but since

we have only a *finite* amount of time, let's stop here.