What do you mean when you use the word “infinity”? I am going to show you, using a few facts about functions and sets that you should have learned during your K-12 education, that there are two infinite sets that are not the same size. In fact, we'll do better than that: we'll show that there are an infinite number of infinite sets, no two of which are the same size!

First, though, we have to agree on what we mean when we say that
two sets are __the same size__. For finite sets, that is easy:
just count the number of elements in the two sets and compare the
numbers. Either they are the same, or they are not. But if we are
comparing sets, some of which may be finite and some of which may be
infinite, we need a different approach.

The standard mathematical solution to this problem is to pair up
elements of the two sets to be compared. Let us say we have two
sets named *S* and *T*. If each element of *S*
is paired with exactly one element of *T*, and every element
of *T* can be found in one of these pairings, then we say
that the two sets are *cardinally equal*: they have the same
size.

Here's a little terminology you may recall from K-12 mathematics.
A function from *S* to *T* that maps every element of
*S* to a unique element of *T* is called a
*1-to-1* or *injective* function. A function from
*S* to *T* where every element of *T* is the
result of applying the function to some element of *S* is
called an *onto* or *surjective* function. A function
that does both is called *1-to-1 and onto*, or
*bijective*. In short, two sets *S* and *T*
are the same size if there exists some bijective function from
*S* to *T*. (Why not from *T* to *S*,
you may ask? Every bijective function has an inverse function, that
does the pairing in the opposite way. So it doesn't matter. If you
find a bijective function going one way, you automatically have a
bijective function going the other way, too.)

Many of the infinite sets you can think of off the top of your head
are the same size. Here is an example: let *S* be the set of
integers \(\left\{ ..., -2, -1, 0, 1, 2, ... \right\}\), and let
*T* be the set of natural numbers
\(\left\{1, 2, 3, ... \right\}\). Even though it looks like
*S* is “bigger”, because it is infinite in both
directions, these two sets are actually the same size. To prove
that, I have to give you a way of pairing up elements from the two
sets so that nothing is left out. Here is one way to do that:

Element of T |
Element of S |
---|---|

0 | 0 |

1 | 1 |

2 | -1 |

3 | 2 |

4 | -2 |

5 | 3 |

… | … |

See how that works? We are “zigzagging” back and forth
to cover all of the elements of *S*. We can even write this
as a function from *T* to *S*:

or we can write it as a function from *S* to *T*:

The functions *f* and *g* are both bijective, and are
inverses of each other. That means that, for any integer *i*,
\(f(g(i)) = i\), and for any natural number *n*,
\(g(f(n)) = n\). Try a few numbers to convince yourself that is
true.

Do you recall the notion of a power set? Given a set *S*,
the power set *P(S)* is the set of all subsets of *S*.
So, for example, if \(S = \left\{0, 1, 2\right\}\), then:

It is called the power set because, for finite sets, the size of
the power set is 2 to the power of the size of the original set. In
our example above, the set *S* has 3 elements, and
*P(S)* has 2^{3} = 8 elements.

Does the power set of an infinite set have the same size as the
original set? Let's suppose that that is the case. Let's pick some
arbitrary infinite set and call it *A* to distinguish it from
all of our example sets above. If *A* and *P(A)* are
the same size, then there is some bijective function *h* from
*A* to *P(A)*. Since everything is paired up, I can
pick any element of *P(A)* (i.e., any subset of *A*),
and there is some element of *A* paired with it.

Consider the set of all elements *a* of *A* such that
*a* is not an element of *h(a)*. That is, we're
making the set *N* (for “not in its paired
element”) like this:

*N* may be the empty set. *N* may be equal to
*A*. It may be somewhere in between. In any case,
*N* is a subset of *A*, and therefore it is an element
of *P(A)*. This means that for some element *b* of
*A*, \(h(b) = N\).

Is *b* in *N*? We said that *N* is the set of
all elements that are *not* in their pairs, so no: *b*
cannot be in *N*. But then *b* is not in the element
it is paired with, which is the definition of *N*, so
*b* __must__ be in *N*. But wait, …

We have found a contradiction: *b* must be in *N* and
*b* must not be in *N*, simultaneously. We therefore
conclude that *b* does not, in fact, exist. Since *b*
does not exist, *nothing is paired with N*, so *h* is
*not* a bijection, which means that *A* and
*P(A)* are *not* the same size. Notice that we never
assumed that *A* is finite. This proof works for both finite
and infinite sets. So now we can pick two infinite sets that are
not the same size:

*I*= the set of integers*P(I)*= the power set of the set of integers

But why stop there? We can keep going for as long as we like:

*P(P(I))*= the power set of the power set of the set of integers*P(P(P(I)))*= the power set of the power set of the power set of the set of integers- …

There you go: an infinite number of infinite sets, no two of which are the same size. Each one is “bigger” than the one before it in the list (although we didn't prove this). You may now leave the classroom to go boggle for awhile.