Okay, I admit it – my previous blog post was published on April 1. The foundations of mathematics are not really under attack, not now. But they were once!
Here’s a famous puzzle: imagine a village barber, who cuts the hair of everyone who doesn’t cut their own hair. Sounds simple enough, but who cuts the barber’s hair?
In the late 19th century, one of the founders of modern logic, Friedrich Frege, was writing down a complete logical foundation for the whole of mathematics. Bertrand Russell read Frege’s work in 1901, and realised it gave rise to a puzzle like that of the village barber. He wrote to Frege and pointed out there must be a “set of all sets that don’t contain themselves.”
Why was this a problem? Well, let’s think about the barber. He’ll cut John’s hair, because John doesn’t cut his own. Eric cuts his own hair, so the barber doesn’t. So, does the barber cut his own hair?
- If he does, then he cuts his own hair. That means he doesn’t.
- If he doesn’t, then he doesn’t cut his own hair, so he does.
Either way, there’s a contradiction. The only way to escape the village barber paradox is to reject the description of the puzzle – clearly the information given about whocuts whose hair was wrong.
In Frege’s system, the “set of all sets that don’t contain themselves” must exist. Does it contain itself?
- If it doesn’t contain itself, then it does, because it contains all such sets.
- If it does contain itself, then it doesn’t, because it only contains sets that don’t contain themselves.
There’s no way to resolve this paradox except to reject Frege’s system. As it stood, it gave rise to contradictions. Some of the axioms must be wrong.
Frege’s system was quickly replaced – many mathematicians invented new axiomatic systems, trying to avoid Russell’s Paradox. The system that was eventually adopted as the mainstream was a set of axioms about sets by Zermelo and Fraenkel.
As far as we know (and there’s no way to prove this for sure) Zermelo-Fraenkel set theory avoids paradoxes like Bertrand Russell’s. However, it turns out to have gaps.
Here’s one:
A couple of weeks ago, we talked about infinite numbers. Now there are different sizes of infinite numbers. For example, there are strictly more real numbers than whole numbers, meaning no matter how you try to line up the real numbers in a list, there’ll always be some numbers you miss.
In Zermelo and Fraenkel’s foundation of mathematics, it’s impossible to know if there is an infinite number strictly bigger than the whole numbers, and strictly smaller than the real numbers.
So, infinite numbers are super-weird. Adding them? Easy. Multiplying them? Also super easy. Figuring out the next bigger infinite number? Sorry, that’s impossible.
So, yes, when Frege’s system was proved to have a contradiction, it really was replaced by something even stranger.