Cantor's Seductive Sets

This article has absolutely nothing to do with travelling, it's something I wrote for a competition for a math article (actually for a "maths" article, as it was a British contest). The results have just been out, and no, I haven't won it. I actually didn't stand a chance, because there was a word limit, and I accidentally sent them the version with a couple hundred extra words. Arghhhh...

PS Sorry 'bout the varying sizes of the pictures; I still haven't quite got the hang of inserting pictures here.

A Beautiful Concept: Cantor’s Seductive Sets

“There are just as many even numbers as there are natural ones.”

“What…? But how…?” you might be thinking…

See for yourself: let’s pair ’em up:

Generally, every number n in the set of natural numbers is paired with 2n in the set of even numbers, and so in the land of numbers there are no bachelors. As this land can be quite conservative, bigamy isn’t allowed, and so there must indeed be as many even numbers as natural ones.

But how can a set have as many elements as a subset that isn’t that set? There can’t be as many women as people if there exists at least one man…

Welcome to the world of infinity, where these strange things do indeed happen! Your passport is an open mind, and the most important law goes like this:

If and only if there exists a one-to-one correspondence between two sets, both sets have the same number of elements (so-called cardinality).

Working under this law, we soon discover that there are just as many rational numbers (fractions), as integers (natural plus negative numbers), as natural numbers, as even numbers. This infinity, the infinity of the natural numbers, is called ‘countable infinity’. Is it the only one?

Nope. In fact, there are more points on any line segment, no matter how small, than there are fractions in the vast expanse of Numberland.

And, as if this weren’t enough, there’s an infinite (at least countably infinite, that is) number of infinities – every set of subsets of a set has more elements (a larger cardinality) than that given set. I’ll try to outline the proof for your benefit and amusement.

Imagine you are in a room with infinitely many children. Perhaps uncountably many yelling, screaming brats... You give each kid a piece of paper (so much for saving trees...) and ask them to make a list of all their friends present in the room. Could it happen that each possible list of children was written down by one of the kids?

Given the sheet of paper, each child is faced with a problem. Is he his own friend? Consider all the kids with a low self-esteem, who decided they don’t like themselves. Make a list of them. Could this list have been written by any of the children? Suppose a child had indeed made this list. Is this child, then, her own friend? If she is, she should be on her list – but her list names only the children who aren’t their own friends. Suppose then that she’s not her own friend. Then we should include her on the list of kids that aren’t their own friends – but that’s the list of her friends, and she isn’t her own friend!

Clearly, the list of children that aren’t their own friends can’t be matched up with any child, so not every possible list can be written down by some child.

The conclusion? The set of all subsets of a given set always has a larger cardinality than the set itself. (Don’t quite see it? Disregarding all children’s rights, throw the yelling and screaming brats, the whole infinity of them, into a nearby dump, replace them with elements of any set, and look at what’s left of our story.) The second conclusion? Low self esteem doesn’t pay off...

***

“Do any of you love set theory?” asked my maths teacher once upon a calculus lesson. Undaunted by the jeering silence that followed, he continued. “Because, you know, you’re at the age in which young people are often under the negative influence of that theory.”

Setting aside my teacher’s charming cluelessness about the level of teenagers’ vulnerability to beautiful mathematical concepts, what could he have meant by that foreboding “negative influence”?

At the time Georg Cantor (though I owe the topic of this article to him, I still haven’t introduced him, so... everyone, meet Cantor, the brilliant 19^th century German mathematician, father to all the different infinities!) created set theory, it was truly revolutionary. Up till then, the only acceptable type of infinity was a potential one – numbers could be as large as one wanted, but they never actually reached infinity. Cantor changed all this – he wrote about infinity as if it was as much of an existent being as any of our little number friends.

But how can infinity exist? When we talk about 0’s and 25’s, we can pretend that we are just talking about abstract properties of ‘the real world’. But when we start talking about the infinity of real numbers, where in the universe can we find anything that even resembles it? This is one of the reasons many of Cantor’s contemporaries rejected his theory. Another objection they had was Cantor’s use of the so-called reductio ad absurdum proof. This is the sort of proof the ‘brat story’ is – we assumed that the children could have made all these lists, and then showed that this assumption leads to a contradiction, so its negation must be true.

Kurt Gödel, a brilliant 20^th century logician, once proved that God exists. His proof was strictly logical, starting with a carefully blended mixture of axioms, and ending in the elegant filet mignon of the conclusion; the same type of proof used in mathematics. Our belief in points, numbers and infinity is no more or less justified than that in God. Mathematics proves that certain numbers and points exist – but what that existence means no one has much of an idea. At best, mathematics seems to be an impossibly nerdy religion.

Cantor’s set theory, even when clad in the unladylike rags of infinitely many brats, is too elegant to be thrown into the dump. Perhaps my maths teacher knew more about young men’s nature than he let on... After all, it’s not all that difficult to capture a young man’s heart, and set theory is the perfect seductress. She might not be true, but she sure is beautiful.