A Brief Proof of
Cantor's Theorem

Explained in (Sort of) Everyday Language

Big George and His Theorem

When halftime rolls around, it's time to relax. So as the entertainment comes on screen, everyone will sit back, stretch, and wonder if there is a simple proof for Cantor's Theorem.

The proof, as all know, was first published in 1891 by Georg Cantor (pronounced GAY-org, but he's George to his English speaking friends).

And if you look up the theorem in a popular informational reference, you read the proof runs something like:

Suppose there is a surjective function, f: N → P(N), then from a set B = { n ∈ N ∣ n ∉ f(n) } there exists g ∈ N where f(g) = G and therefore g ∈ G if and only if g ∉ G which means f is not surjective, but because there is an injective function where n maps to {n}, the cardinality of P(N) must be strictly larger than the cardinality of N.

Halftime

Although this proof make perfect sense to George's colleagues, it may be a bit terse for the average sports fan. So a little exposition is clearly warranted.

First of all, what the heck is Cantor's Theorem? We've always wanted to know that.

No doubt you have, as Captain Mephisto said to Sydney Brand. It's very simple really.

Cantor's Theorem states that the number of subsets is always larger than the size of the set itself.

Captain Mephisto
We understand.

Some people scratch their heads at such a statement since it seems the proof is - as Thomas Jefferson might have said - self-evident. After all, if you take some sets and write out their subsets, you get:

Set		Total Subsets
{1}		{}, {1}
{1, 2}		{}, {1}, {2}, {1, 2}
{2, 4, 6}		{}, {2}, {4}, {6}, {2,4}, {2,6}, {4, 6}, {2, 4, 6 }

... where among the subsets is the empty set {} - often represented as ∅ - and the set itself.

In fact, it can be proven rigorously - a proof we will eschew - that if a set has n elements, then the number of subsets is 2ⁿ.

Or put in more rigorous terms, if a set S has a size - or as mathematicians say, a cardinality - of n:

CARD[S] = n

... then the set of all its subsets - called the power set, P(S) - has a cardinality of 2ⁿ.

CARD[P(S)] =2ⁿ

Which is easy to see:

Set S		Power Set, P(S)
{2, 4, 6}		{{}, {2}, {4}, {6}, {2,4}, {2,6}, {4, 6}, {2, 4, 6 }}
CARD[S] = 3		CARD[P(S)] = 23 = 8

Although this may seem to solve the matter, alas, it doesn't. The (omitted) proof is only valid for finite sets. But it has been known since Galileo's time that properties of finite sets are not necessarily the same as for an infinite set. So proving something for a finite set can't be considered a proof for infinite sets.

That's were George's proof comes in. It applies to infinite sets as well.

More exactly George's Theorem states:

Given the set of counting numbers, N, then the cardinality of its power set, P(N), is greater than the cardinality of N.

In other words, there are more subsets of a set than the elements of the set - even if the set is infinite.

But how can a set have more elements than an infinite set? Is't possible?¹

George Steps In

The usual proof of Cantor's Theorem and as given below is what's called an indirect proof or a proof by contradiction. A proof by contradiction is where you first assume the opposite of what you want to prove. Then starting with that assumption you use arithmetic until you arrive at a statement that's impossible - ergo, you find a contradiction. And if you find a contradiction, the logicians tell us, your assumption was wrong. Therefore what you wanted to prove in the first place is in fact correct.

Got that?

Now to determine if two infinite sets are the same size, you obviously can't count the elements. Instead you need to establish that there is a one-to-one correspondence between the sets. For instance, we know the set of even numbers and odd numbers are the same size - that is, they have the same cardinality - since they can be paired up:

So in our proof by contradiction we start by assuming we CAN pair each counting number, n, with a unique subset of the counting numbers. We'll designate the subsets as S_n's.

For instance, in the pairing you might get something like:

What we have defined here are indexed subsets, S_n of the counting numbers. The index, n, is simply the counting number associated with the particular subset.

Now here George pointed out that some of the subsets contain their index.

Such subsets where n ∈ S_n and the corresponding index n are called inclusive. That is, inclusive subsets are defined as:

All S_n where n ∈ S_n

Inclusive Subsets

But there are also subsets that do NOT contain their index:

Such a subset and its index are called exclusive subsets and exclusive indexes.

All S_n where n ∉ S_n

Exclusive Subsets

The proof now focuses on the exclusive subsets.

"No culture can live if it attempts to be exclusive." - Mahatma Gandhi (Attr.)

Mahtama

At this point we look again at the exclusive subsets.

Now take the index of all these exclusive subsets and put them into a set. We call this set G.

G = {2, 4, ..., n ∉ S_n, ... }

So in general G is defined as:

G = {n ∈ N: n ∉ S_n }

... which is read in fairly plain English as:

G is the set of all counting numbers, n, such that n is not an element of it's indexed subset

... or in plainer English:

G is the set of the indexes of all exclusive subsets.

Here's the kicker. Notice that G is itself a subset of the counting numbers. So if the counting numbers ARE in a one-to-one correspondence with EVERY subset, then G must be one of the subsets in the list.

Now if G IS in the list of subsets it must have an index - a corresponding counting number. We'll call its index g.

In other words g is the index of the set G:

NOW we need to find a contradiction.

"Contradiction is not a sign of falsity, nor the lack of contradiction a sign of truth." - Blaise Pascal

At this point its a good idea to recap what we've done.

Remember in an indirect proof, we assume the OPPOSITE of what we want to prove. Since we want to prove that all counting numbers CANNOT be put into a one-to-one correspondence with all its possible subsets we have assumed you CAN.

The next step will then be to determine if our assumption leads to an impossible conclusion. If so then the assumption was wrong and what we wanted to prove originally is correct. Remember this is what you do in an indirect proof or proof by contradiction.

Our assumption led us to recognizing that the indexed subsets are two types, inclusive or exclusive subsets depending on whether the index is or isn't a member of the set.

We then defined the subset G as the subset of all exclusive indexes. But since we assumed every possible subset was in our original list, G must be one of the original subsets. If so then it must have an index which is a counting number we call g.

The nice thing about an indirect proof is ANY contradiction will do. The contradiction doesn't have to be related to what we want to prove at all.

For instance if you assumed that there was no counting number greater than 3 that can be expressed as the sum of two primes and from this assumption you were able to deduce that George Washington was the King of France, you would have proven Goldbach's Conjecture.

So what we do is take our set G and its index, g and ask:

Is the set G inclusive or exclusive?

Here we begin to reason.

"Reason is the slow and torturous method by which those who do not know the truth discover it." - Blaise Pascal.

Remember that G is defined as the subset of the indexes that are NOT contained in their corresponding subsets. So we MIGHT expect g is not in G.

g ∉ G

But hold on! If g is NOT an element of G, then g is an index that is NOT in its corresponding subset.

But every index not in its subset is an element of G!

So we MUST conclude that g is an element of G!

g ∈ G

Note, though, we arrived at this conclusion - that g ∈ G - by assuming that g ∉ G!

That means we can write:

If g ∉ G then g ∈ G.

In other words, if G is exclusive then G must be inclusive!

Well, OK. So G must be inclusive.

But wait a minute! If G is inclusive then it contains its own index, g. That is g is an element in G.

g ∈ G

But by definition, all numbers in G are NOT in their corresponding subset!

So g cannot be in G!

g ∉ G

So this last bit of reasoning has led us to conclude:

If g ∈ G then g ∉ G

So now we've proven that if G is inclusive, then G is exclusive!

So putting it all together we have shown:

IF G IS EXCLUSIVE THEN G IS INCLUSIVE
and
IF G IS INCLUSIVE THEN G IS EXCLUSIVE!

... which is written mathematically as:

If g ∉ G then g ∈ G
and
If g ∈ G then g ∉ G

Which formal logic says is the same as saying:

g ∉ G IF And Only IF g ∈ G

So we conclude that g is an element of G and it is not an element of G!

Since no number can be in a set and not be in the same set, we now have a contradiction.

Mr. Cantor, What Does It All Mean?

Admittedly you may ask what the hey does a contradiction about a rather contrived property of sets - exclusive and inclusive - have to do with the number of subsets of counting numbers?

Well, remember we are doing an indirect proof or proof by contradiction. We assume the opposite of what we want to prove and arrive at a contradiction. If we do that then we have proven what we wanted to prove.

And remember, any contradiction will do. And our assumption was that the counting numbers can be put into a one-to-one correspondence with ALL of its subsets. And we found a contradiction.

So by finding a contradiction, we proved the assumption was FALSE. So we know that every subset of the counting numbers CANNOT be paired with every counting number. Therefore the number of counting numbers is not the same as the number of all subsets of the counting numbers.

"Thus mathematics may be defined as the subject in which we never know what we are talking about, nor whether what we are saying is true." - Bertrand Russell.

Now to many the reasoning seems awfully convoluted and leaves some people thinking mathematicians are trying to pull a fast one. But actually you don't need to have a lot of "If-it-is-it-isn't-and-if-it-isn't-it-is" type of BROUHAHAH.

In fact you can skirt around the indirect reasoning. Just start from the beginning and look if G can be any of the sets.

To this end we go back to our examples:

And G is:

G = {2, 4, ..., n ∉ Sn, ... }

OK. Can G be S₁?

Well, no. It can't. That's because in our example 1∈S₁ but 1∉G. So G and S₁ differ by at least one element. So they can't be the same.

Well, what about G being S₂? Well, no. G can't be S₂, either. That's because in our example 2∉S₂ but 2∈G. Again they don't have the same elements.

S₃? Nope, G isn't S₃. 3∈S₃ but 3∉G.

S₄? Nope. 4∉S₄ but 4∈G.

S₄? Nope. 5∈S₅ but 3∉G.

If we summarize what we've found we see:

So at least in our example G cannot be any of the indexed subsets S_n.

In fact these examples here can be easily generalized to any indexed subset of the counting numbersx. With a bit of reflection we realize:

1. If n is an index of an inclusive subset then it is an element of its subset S_n.

2. But an index of an inclusive subset CANNOT be an element of G whose elements are only indexes of exclusive subsets.
3. Therefore every inclusive subset differs from G by at least one element.
4. Therefore G cannot be any inclusive subset.

Then with further reasoning:

1. If n is an index of an exclusive subset, it cannot be an element of its subset S_n.
2. But since G is the set of all exclusive indexes, then n will be an element of G.
3. Therefore G will differ from any exclusive S_n by at least one element.
4. Therefore G cannot be any exclusive subset.

And in conclusion:²

Or in simple mathematical jargon, for any counting number, n, and any unique subset, S_n, paired with n:

So all you really need to do is look at the original list and realize a set created from the exclusive indexes cannot be in the list. You don't need to first make an explicit assumption that G is in the list and has its own index g.

"Don't, for heaven's sake, be afraid of talking nonsense! But you must pay attention to your nonsense." - Ludwig Wittgenstein,

Ludwig Wittgenstein
Unsinn or not Unsinn?

Now at this point it might be tempting to say that since every subset is inclusive or exclusive, what we really did is prove that G simply cannot exist. Or as Ludwig Wittgenstein might say, asking if G is one of the indexed sets is an unsinn or nonsense question. So you haven't really proven there is another set of counting numbers on in the list.

But actually the question is NOT UNSINN at all.

Instead what we found was that if a group of unique subsets of the counting numbers are paired with the counting numbers, then all can be listed as inclusive or exclusive. But then we showed there is a new subset, G, can be CREATED that CANNOT be one of those indexed sets.

But yet³ no matter how G was created it IS a bonafide subset of the counting numbers.

Therefore our correct conclusion is:

If you assume you can pair every counting number with a unique subset of the counting numbers, there is at least one subset not in the list.

And after long last we know:

The cardinality (size) of the set of counting numbers, N, is not the same as the cardinality of its power set, P(N).

Bigger and Better

OK. The two sets aren't the same size. But is the power set of counting numbers larger or smaller than the set of counting numbers?

It would seem that it must be larger. After all, we paired each number with a unique subset and we could create a new subset not in the list. So there must be more subsets than counting numbers.

Well, that's not quite what we proved. Strictly speaking all we proved was the counting numbers and their power sets are not the same size. That's because the pairing the numbers with a unique subset was nevertheless an assumption.

So to prove there are more subsets than counting numbers, we first must UNAMBIGUOUSLY CONSTRUCT a one-to-one correspondence of the numbers to a WELL DEFINED group of unique subsets.

Fortunately that's simple enough. Just match each counting number, 1, 2, 3, ..., n, ... with the subsets {1}, {2}, {3}, ..., {n}, ...

So this proves that the power set of the natural numbers, P(N), must be at least as large the set of counting numbers, N.

But we have ALSO just proven that the two sets are NOT the same size.

So if the number of subsets is not the same size as the counting numbers AND the number of subsets is at least as large as the counting numbers, then the only conclusion is that:

THERE MUST BE MORE SUBSETS OF COUNTING NUMBERS THAN COUNTING NUMBERS!

Slipping It In

At some point the clever reader will think, "Wait! So what if I create a set that isn't in the original list? I'll just bump the other sets up one number and put the new set at the beginning. Then every set will be paired with a counting number after all!"

For instance, we'll just take our original set:

And stick G

G = {2, 4, ..., }

at the beginning:

But since none of the subsets in the original list were the same, and G was different from any of them, this new list again is pairing each counting number with a unique subset.

Note we don't need the old list to define the new S₁. Remember the old G was defined as:

G = {n ∈ N:  n ∉ S_n }

So the new S₁ is now:

S₁ = Old G = {n - 1 ∈ N: n - 1 ∉ S_n>1 }

OK. Now we have ALL subsets of the counting numbers paired with a counting number.

Right?

Weeeehhhhhheeeeeelllll, that doesn't quite work.

Note that when you slip the new set into the list, the index of the new S₁ is now 1. And it can now be designated as exclusive or inclusive based on whether 1 is an element of the new S₁ (the old G).

And as before we can now we simply create a New G from a new set of indexes from exclusive sets. In our example S₁ is exclusive and so the New G is:

New G = {1, 3, 4, 6, ...}

And using the same reasoning as before it can be shown that the New G - whether inclusive or exclusive - is NOT one of the new indexed subsets - an exercise that will be left for the reader.

It is tempting to say, well, we'll just slip this New G in as yet another S₁. No matter how many New G's we create we can always put it in the list. No matter how many new subsets we make, we can always pair them with a counting number!

So it seems George's Theorem is an unsolvable chicken-and-the-egg type problem. And you will find much discussion on this topic and there are many who argue that George is wrong.

But (another big "but") ...

To prove that you can put all counting numbers into a one-to-one correspondence with all possible subsets, you would have to show that after creating the indexed subsets as we did above, it is impossible to create a new one.

But George's Theorem shows that can always create a new one. So the inescapable conclusion is George is right.

When ∞ > ∞

1. There are at least as many subsets of counting numbers as counting numbers.
2. The number of subsets of counting numbers is not the same as the counting numbers.

So that means:

3. There are more subsets of counting numbers than counting numbers.

But naturally we have the question, just how many more subsets are there than the numbers? After all, the counting numbers are infinite. How can something be bigger than infinity?

Now here's where George came up with something really new. George decided the only way to resolve the dilemma that one infinite set is larger than another infinite set is that

THERE IS MORE THAN ONE TYPE OF INFINITY!

George's reasoning was really smart. Instead of calling the cardinality of the natural numbers just the old fashioned infinity, ∞, George referred to it as ℵ₀, or Aleph-Null.

CARD[ N ] = ℵ₀

But remember that George also showed that the cardinality of the power set of N, CARD[ P(N) ], is greater than the cardinality of N. Therefore:

CARD[ P(N) ] > ℵ₀

So how do we calculate CARD[ P(N) ]?

Remember that the cardinality of any finite set, S, with n elements is:

CARD[ P(S) ] = 2ⁿ

But if n is infinite, you take the limit of 2ⁿ as n goes to infinity.

Now in the old days B. G. (Before George), you'd just write the formula using the old infinity sign:

... and the mathematicians would have said this equation simply "blows up". That is, the limit is simply infinity and that's that.

But using George's idea of infinity things are more exact. Since n is a counting number, as n approaches infinity it must be the infinity of the counting numbers. And that infinity is ℵ₀.

And so we get the formula.

And this new limit, George, concluded, was the cardinality of the power set of N. But because George proved that the cardinality of P(N) can't be ℵ₀ and must be larger, he called the new infinity ℵ₁ or Aleph-One.

So the two infinities are related by the equation:

ℵ₁ = 2^ℵ₀

George then went even further. The infinities of ℵ₀ and ℵ₁ are just the beginning of a new type of number, the transfinite numbers. And each transfinite number - designated by ℵ_i - are related by the equation:

ℵ_{(n + 1)} = 2^ℵ_n.

Cantor's Theorem was a big plus for George. Nearly twenty years earlier he used a similar approach to prove the number of real numbers was greater than the counting numbers. But now he reasoned that as ℵ₀ was the infinity of counting numbers, then ℵ₁ must be the infinity of the real numbers as well.

Here, though, George got stuck. He thought - but never proved - that there were no infinities between ℵ₀ and ℵ₁. This is the famous Continuum Hypothesis. However, in 1940 Kurt Gödel and Paul Cohen in 1963 showed that if George wasn't right, but then he wasn't all that wrong either.

Kurt and Paul
George wasn't all that wrong.

Making it Direct

Despite all the explanations offered, as shown above Cantor's Theorem still requires the hypothesis that you can pair every counting number with a unique subset. So the proof can still be considered indirect.

And there are a group of curmudgeonly mathematicians - called constructivists - that object to such roundabout proofs. In fact, they don't accept indirect proofs or proof by contradiction at all. Proofs, they say, must start with axioms or previously proven theorems and by clearcut direct reasoning lead to the proper conclusion.

We have to admit that constructivists are in the minority. Most mathematicians not only accept indirect proofs but they like indirect proofs. They point out that if you go to a mathematics journal most of the proofs are in fact indirect. And there's just a lot of things you can't prove unless it's with an indirect proof.

But in the spirit of harmony and solidarity we will find there are ways to cut back the number of hypotheses even more to avoid the rather convoluted "if-it-is-it-isn't-and-if-it-isn't-it-is" reasoning. And only simple middle school math is needed.

So how to proceed?

At this point the intuitionists will say, pshaw! It's easy to create unique indexed subsets paired with the counting numbers and then create on that isn't in the list. For instance, let's define the sets:

So you get:

Clearly all of these sets are unique and are in a 1:1 correspondence with ALL counting numbers. Half are inclusive and half exclusive.

Creating G from exclusive subsets is simply the even numbers:

G = {2, 4, 6, ..., 2n, ... }

However, this doesn't quite work. For instance, if we slip this in as Subset #2, S₂ instead of S₁, you get:

Hm. All the sets are inclusive. So with no exclusive subsets, there can be no new G. So using this method of making the one-to-one correspondence, we reach quickly a dead end and can't create a new subset.

Now such an example does not disprove George's Theorem. It just shows that there are some one-to-one pairings of sets with counting numbers do not have an inexhaustible supply of new sets waiting in the wings.

There is, though, a procedure that might work. That is we can make a constructive one-to-one correspondence where there's always a new subset waiting off stage.

What we need is to construct a distinct series of indexed subsets of the counting numbers some of which guaranteed to be inclusive and the others to be exclusive. Also creating the new set must be able to be added anywhere to the list but not preventing a new subset from being created.

To this end, we begin by indexing the entire set of counting numbers and put them in Row #1.

Then we place a series of RANDOMLY SELECTED 0's and 1's under each number. So you might get something like:

Then where there's a 0 we delete the counting number. If there's a 1, we leave it. This creates the subset S₁.

... which in ordinary set notation is:

S₁ = { 1, 2, 5, 10, 12, 15, ... , n, ... }

Next repeat the process for a new set.

And so our second subset is:

S₂ = { 1, 6, 9, 12, 13, 14, ... , n, ... }

Note that in our examples, S₁ is inclusive. That is the index is 1 and 1∈A₁. But S₂ is exclusive since the set index is 2 and 2 ∉ A₂.

This procedure - generating an infinite series of random 0's and 1's and deleting the counting number where there's 0's - certainly is an effective method for creating a pairing of the counting numbers with a subset of the counting numbers.

But ....

Can any of the subsets created in this way be the same? Remember we need unique subsets to pair with the counting numbers.

Fortunately a little middle school math will prove - directly of course - that all sets created in this manner MUST be different.

Look at it this way. Generating the subsets is by first creating a random series of 0's and 1's for each elements of the subset. Wherever there's a 1 the counting number will be selected to be in the subset. Where there's a zero it will be deleted. So the only way for two sets to be the same is if the 0's and 1's for the subsets are identical.

Simple calculations tell us that the probability, P, that two randomly generated series of 1's (or 0's) of finite length i will be the same is (¹/₂)ⁱ.

 P = (1/2)i

For instance if the length of two random strings of 0's and 1's are 10, then the probability that two sequences will be the same is:

 P = (1/2)10 = (1/210) = (1/1024)
     = 0.000977

If the length is 50, then the probability the sequences are the same is:

 P = (1/2)50 = (1/250) = (1/1125899906842620)
     = 0.000000000000000888178419700125

OK. But what if the length is infinite? Well, that's easy. You just take the limit of the probability as i goes to infinity.

P =

lim

i → ∞

(¹/₂)ⁱ

Which everyone knows is:

P =

lim

i → ∞

(¹/₂)ⁱ = 0

So as long as we are creating infinite sets of the counting numbers by randomly selecting counting numbers, the probability that any two sets will be the same is ZERO!

This means that each subset can be paired UNIQUELY with a counting number.

But since we are also dealing not just with infinite sets where we randomly delete counting numbers there are an infinite number of such sets. So exactly half of the sets will be inclusive and the other half will be exclusive. Then the proof can proceed as before.

Note that this unique pairing of counting numbers with unique subsets does not require any assumptions. None of the "assume there is a pairing" stuff. The sets have been created by a clear-cut constructive method.

The curmudgeons may argue this isn't really an effective method, since it involves random selection of an infinite set of numbers. So the sets cannot be expressed as a real formula.

Well, if it's not direct, it's direct enough. Besides being infinite can actually be quite economical as the following story shows.

 An infinite number of mathematicians walk into a bar. The first orders a beer. The second orders half a beer. The third orders a quarter of a beer. Each of the mathematicians order half of what the previous one did.
 The bartender asked, "Why are you ordering drinks like that?
 The first mathematician replied, "Two's our limit."

References and Further Reading

"Set Theory", Daniel Cunningham, Internet Encyclopedia of Philosophy.

"Recent Work on the Principles of Mathematics," Bertrand Russell, The International Monthly, July, 1901.

Return to Department of Education

Return to CooperToons Home Page