Given a town in which a barber shaves everyone and only those who don't shave themselves, does he shave himself?
Introduction
What's the paradox here? Well, the barber shaves all of those and only those who do not shave themselves.
If he were to shave himself, then that would be a contradiction as the rule explicitly states he only shaves those who do not shave themselves. If he were not to shave himself, then he again is breaking the rule as he there is one person, namely the barber, who doesn't shave himself that is not shaved by the barber. A contradiction!
But, the purpose of this page is not to talk about barbers, but mathematics. So what is the mathematics behind this? It turns out that this scenario is simply an applied version of Russel's Paradox. Russel's paradox is perhaps one of the most intriguing and influential paradoxes formulated in humanity's history. Russel's paradox was an attempt by the British logician, philosopher, and mathematician Bertrand Russel to show the inconsistencies of naive set theory, or the early framework of set theory set in motion by Georg Cantor and Gottlob Frege.
Cantor was the figurehead of the new move in mathematics to provide a foundational theory. Before Cantor and Frege, much of mathematics was disconnected. Analysis was very different from topology, which was very different from number theory. There was no common framework that fully united these branches of mathematics. Naive set theory was one such attempt, and although it satisfactorily laid the foundation of much mathematics, it did not hold up to mathematical scrutiny.
What is Russel's Paradox?
In naive set theory, Cantor advocated the concept that any definable collection of elements is a set. For the sake of simplicity, these elements will be numbers, but they can be anything we desire them to be. Set theory is a very abstract theory and can be applied to all sorts of scenarios (as you may suppose, the concept of a collection of elements is just about universal).
Russel didn't like this free-roaming, informal framework. As a logician, he wasn't a fan of defining whole foundations of fields in informal language, which is what naive set theory set out to do. Even though these early theories sufficed for everyday use of set theory in mathematical circles, they were considered too fragile by Russel. Therefore, Russel attempted to find a definable collection of elements that cannot exist as a set. He came up with the following:
Let R be the set of all sets that are not members of themselves. If R is not a member of itself, then by definition it must contain itself. If it does contain itself, then it contradicts its definition as only including sets that are members of themselves. Contradiction spotted again! Symbolically, this can be represented as
Let R = {x | x ∉ x}, then R ∈ R ⟺ R ∉ R
As you can see, the nature of this paradox is very similar to that of the Barber paradox. Russel's paradox is simply the abstract, original statement that motivated the Barber paradox as an applied analogue. Why do we care? From the principle of explosion in logic, any proposition, no matter how outlandish, could be proved from such contradictions. The presence of contradictions like these is a calamity for mathematics as it can topple the entire framework of mathematics, meddling with the ideals of mathematical truth and falsity.
A Little Background
Let's talk about the millennia of intellectual advances that led to Russel's paradox. There's a lot of talk about foundational theories, so let's begin with proto-attempts at such theories. We are especially looking for the question: "What is mathematics?" We begin our story with Plato, a huge figure of philosophy and a prominent mathematics aficionado. Plato described mathematics as some sort of mental reality, in which numbers existed not in the world but in some alternate reality of concepts ("the world of forms"). Aristotle, his most famous student, disagreed. Aristotle thought that numbers themselves were not objects but in fact properties of objects. So if I have five pencils in front of me, the pencils and the number of five weren't two separate objects, but five is a property of the number of pencils on my table.
Fast forward 2000 years to Immanuel Kant, yet another huge mathematics aficionado. Kant disagreed with Plato's notion that mathematics is objective truth independent of human experience, and thought that to come up with any mathematics one would need intuition. Sure, mathematics described the world, but we also were the ones creating math from our experience.
Then comes Frege, arguably the hero behind this whole story. Frege was a quiet logician with quite fundamental and revolutionary ideas. He disagreed with Aristotle's view of numbers as merely properties of objects, for if they were, then only one number would belong to any arbitrary object uninfluenced by subjective opinion. For example, take a deck of cards. Is one the number corresponding to the one deck of cards, or is 52 the number corresponding to the 52 cards in that deck?
Frege's Theory
To Frege, the aforementioned argument dismantled Aristotle's view. He also disagreed with Kant's intuition theory of mathematics, stating that arithmetic can be known from logic alone. With these prominent disagreements, he sought a new way of conceptualizing number and mathematics, based on logic. This initiated a whole movement in mathematics named logicism. Frege began by asking:
What is number? Define it without using any sort of circular definition (i.e. including the word number, quantity, etc)
Frege defined numbers using concepts and extensions. A concept is any idea you can think of, and an extension would be the set of all things belonging to the concept. A concept might be books, and the extension is the set of all books. Numbers are then extensions of concepts, with each concept assigned a sort of "extension number." For example, all things made of three objects would have extension number three. Similar on the surface to previous mathematical philosophy, but yet very different.
Frege took it as an axiom that each concept had a corresponding extension (even if it was empty, i.e. a square circle is a concept with an extension that is the empty set). This would become the general comprehension principle, which states that the number of concepts is identical to that of extensions. This sounds pretty reasonable, right? Not so quick.
The Tragic Story of a Genius
Just as Frege published his work, Russel sent a letter to him stating that even though he agrees with him on quite a lot, he has just one difficulty: that which will later become his famous paradox.
Frege crumbled after this. His whole life's work seems to be futile now. He was so crushed he had a mental breakdown which took him to the hospital. However, Frege later took this incredibly well. He hurried to make an appendix noting of Russel's note, describing it as well as the fact that its implications are not quite clear as of the moment. Eventually, Frege would have to give up many of his ideas on the foundations of mathematics. In writing about Frege's handling of the paradox, Russel wrote:
As I think about acts of integrity and grace, I realise that there is nothing in my knowledge to compare with Frege's dedication to truth. His entire life's work was on the verge of completion, much of his work had been ignored to the benefit of men infinitely less capable, his second volume was about to be published, and upon finding that his fundamental assumption was in error, he responded with intellectual pleasure clearly submerging any feelings of personal disappointment. It was almost superhuman and a telling indication of that of which men are capable if their dedication is to creative work and knowledge instead of cruder efforts to dominate and be known.
Resolution
About seven years later, two ways of avoiding the paradox were proposed: Russell's type theory and the Zermelo set theory. While Russel advocated for an alteration of the logical language and framework itself, Zeremelo simply went beyond Frege's flexible axioms. Zermelo would form the first axiomatic set theory, which is a set theory based in formal logic. Zeremelo set theory evolved into the canonical Zermelo-Fraenkel set theory (ZFC) which forms the basis of mathematics today. In a happy ending, a lot of Frege's original ideas are incorporated into ZFC, so his research was not fruitless at all.
But the story is not over. ZFC is not free from criticism, and some newer theories are proving to be more lucrative candidates for a "foundation of mathematics" clay by day. One such theory is category theory, which abstractly represents mathematical concepts through "categories." Another is hornotopy type theory, which revives Russel's work on type theories albeit in a different form.
0 Comments