122
$\begingroup$

Though I've understood the logic behind's Russell's paradox for long enough, I have to admit I've never really understood why mathematicians and mathematical historians thought it so important. Most of them mark its formulation as an epochal moment in mathematics, it seems to me. To my uneducated self, Russell's paradox seems almost like a trick question, like a child asking what the largest organism on Earth is, and getting back an answer talking about a giant fungus.

"Well, OK..."

The set of all sets admits all sorts of unmathematical objects right? Chickens, spoons, 2 $\times$ 4s, what have you...I can't imagine a situation where a mathematician solving a concrete problem would invoke a set like that. The typical sets one sees in everyday mathematics are pretty well defined and limited in scope: $\mathbb{Z}$, $\mathbb{R}$, $\mathbb{C}$, $\mathbb{R}^n, \mathbb{Q}_p$, subsets of those things. They are all built off each other in a nice way.

But clearly important people think the result significant. It prompted Gottlob Frege, a smart and accomplished man, who Wikipedia tells me extended the study of logic in non-trivial ways, to say that the "foundations of [his] edifice were shaken." So I suppose Russell's paradox is "deep" somehow? Is there a practical example in mathematics that showcases this, where one might be led horribly astray if one doesn't place certain restrictions on sets, in say, dealing with PDEs, elliptic curves, functional equations? Why isn't Russell's paradox just a "gotcha"?

  • 0
    I'm not sure if this has been mentioned, but there is also the fact that in classical logic -- the logic that most mathematicians use, knowingly or not -- we have the principle of explosion: from a contradiction, we can deduce anything. So if we admit the Russell set and Russell's paradox, how do we know that any theorems we've proven aren't just $r \in r \land r \notin r \vdash P$ in disguise.2016-09-12

16 Answers 16

98

Russell's paradox means that you can't just take some formula and talk about all the sets which satisfy the formula.

This is a big deal. It means that some collections cannot be sets, which in the universe of set theory means these collections are not elements of the universe.

Russell's paradox is a form of diagonalization. Namely, we create some diagonal function in order to show some property. The most well-known proofs to feature diagonalization are the fact that the universe of Set Theory is not a set (Cantor's paradox), and Cantor's theorem about the cardinality of the power set.

The point, eventually, is that some collections are not sets. This is a big deal when your universe is made out of sets, but I think that one really has to study some set theory in order to truly understand why this is a problem.

  • 3
    About the well-known proofs by diagonalization, the halting problem is also a very important one.2014-01-28
88

My dad likes to tell of a quotation he once read in a book on philosophy of mathematics. He does not remember which book it was, and I have never tried to track it down; this is really hearsay to the fourth degree, so it may not even be true. But I think it is pretty apt. The quote describes a castle on a cliff where, after each a storm finally dies down, the spiders come out andrun around frantically rebuilding their spiderwebs, afraid that if they don't get them up quickly enough the castle will fall down.

The interesting thing about the quote was that it was attributed to a book on the logical foundations of mathematics.

First, note that you are looking at the problem from a perspective of someone who "grew up" with sets that were, in some way, carefully "built off each other in a nice way." This was not always the case. Mathematicians were not always very careful with their foundations: and when they started working with infinite sets/collections, they were not being particularly careful. Dedekind does not start from the Axiom of Infinity to construct the naturals and eventually get to the reals; and moreover, when he gives his construction it is precisely to try to answer the question of just what is a real number!

In some ways, Russell's paradox was a storm that sent the spiders running around to reconstruct the spiderwebs. Mathematicians hadn't been working with infinite collections/sets for very long, at least not as "completed infinities". The work of Dedekind on the reals, and even on algebraic number theory with the definitions of ideals and modules, was not without its critics.

Some mathematicians had become interested in the issues of foundations; one such mathematician was Hilbert, both through his work on the Dirichlet Principle (justifying the work of Riemann), and his work on Geometry (with the problems that had become so glaring in the "unspoken assumptions" of Euclid). Hilbert was such a towering figure at the time that his interest was itself interesting, of course, but there weren't that many mathematicians working on the foundations of mathematics.

I would think like Sebastian, that most "working mathematicians" didn't worry too much about Russell's paradox; much like they didn't worry too much about the fact that Calculus was not, originally, on solid logical foundation. Mathematics clearly worked, and the occasional antinomy or paradox was likely not a matter of interest or concern.

On the other hand, the 19th century had highlighted a lot of issues with mathematics. During this century all sorts of tacit assumptions that mathematicians had been making had been exploded. Turns out, functions can be very discontinuous, not just at a few isolated points; they can be continuous but not differentiable everywhere; you can have a curve that fills up a square; the Dirichlet Principle need not hold; there are geometries where there are no parallels, and geometries where there are an infinite number of parallels to a given line and through a point outside of it; etc. While it was clear that mathematics worked, there was a general "feeling" that it would be a good idea to clear up these issues.

So some people began to study foundations specifically, and try to build a solid foundation (perhaps like Weierstrass had given a solid foundation to calculus). Frege was one such.

And to people who were very interested in logic and foundations, like Frege, Russell's paradox it was a big deal because it pinpointed that one particular tool that was very widely used led to serious problems. This tool was unrestricted comprehension: any "collection" you can name was an object that could be manipulated and played with.

You might say, "well, but Russell's paradox arises in a very artificial context, it would never show up with a "real" mathematical collection." But then, one might say that functions that are continuous everywhere and nowhere differentiable are "very artificial, and would never show up in a 'real' mathematical problem". True: but it means that certain results that had been taken for granted no longer can be taken for granted, and need to be restricted, checked, or justified anew, if you want to claim that the argument is valid.

In context, Russell's paradox showed an entirely new thing: there can be collections that are not sets, that are not objects that can be dealt with mathematically. This is a very big deal if you don't even have that concept to begin with! Think about finding out that a "function" doesn't have to be "essentially continuous" and can be an utter mess: an entirely new concept or idea; and entirely new possibility that has to be taken into account when thinking about functions. So with Russell's, an entirely new idea that needs to be taken into account when thinking about collections and sets. All the work that had been done before which tacitly assumed that just because you could name a collection it was an object that could be mathematically manipulated was now, in some sense, "up in the air" (as much as those castle walls are "up in the air" until the spiders rebuild their webs, perhaps, or perhaps more so).

If nothing else, Russell's paradox creates an entirely new category of things that did not exist before: not-sets. Now you think, "oh, piffle; I could have told them that", but that's because you grew up in a mathematical world where the notion that there are such things as "not-sets" is taken for granted. At the time, it was the exact opposite that was taken for granted, and Russell's paradox essentially tells everyone that something they all thought was true just isn't true. Today we are so used to idea that it seems like an observation that is not worth that much, but that's because we grew up in a world that already knew it.

I would say that Russell's paradox was a big deal and wasn't a big deal. It was a big deal for anyone who was concerned with foundations, because it said "you need to go further back: you need to figure out what is and what is not a collection you can work with." It undermined all of Frege's attempt at setting up a foundation for mathematics (which is why Frege found it so important: he certainly had invested a lot of himself into efforts that were not only cast into doubt, but were essentially demolished before they got off the ground). It was such a big deal that it completely infuses our worldview today, when we simply take for granted that some things are not sets.

On the other hand, it did not have a major impact on things like calculus of variations, differential equations, etc., because those fields do not really rely very heavily on their foundations, but only on the properties of the objects they are working with; just like most people don't care about the Kuratowski definition of an ordered pair; it's kind of nice to know it's there, but most will treat the ordered pair as a black box. I would expect most of them to think "Oh, okay; get back to me when you sort that out." Perhaps like the servants living on the castle not worrying too much about whether the spiders are done building their webs or not. Also, much like the way that after Weierstrass introduced the notion of $\epsilon$-$\delta$ definitions and limits into calculus, and then re-established what everyone was using anyway when they were using calculus, it had little impact in terms of applications of calculus.

That rambles a bit, perhaps. And I'm not a very learned student of history, so my impressions may be off anyway.

  • 1
    Morris Kline also uses the spider metaphor in _Mathematics: The Loss of Certainty_2012-03-07
36

The difficulty can be hard to see from a modern point of view, where set theory books have been written in a way that avoids the problem. So imagine that you had never learned any set theory, but you are familiar with the English word "set". You probably think, as mathematicians did at the time, that any well-defined collection of objects forms a set, and any set is a particular well-defined collection of objects. This seems like a perfectly reasonable idea, but Russell's paradox shows that it's actually inconsistent. Moreover, the "set" that we now associate with Russell's paradox -- the set of all sets that don't contain themselves -- seems like a perfectly well-defined set. After all, each particular set is either a member of itself or not, so the ones that are not seem to be a well-defined collection. This casts doubt on the English language term "set", which in turn seems to cast doubt on all mathematics done in English. That was why the paradox was so revolutionary -- because things people had been routinely using turned out to be inconsistent, and it seemed possible that more paradoxes might be found that would cast doubt on other mathematical objects.

The solution that mathematicians eventually adopted was to drop the normal English meaning of set ("any well-defined collection of things") and replace it with a different concept, the "iterative" concept of sets. But it took some time for that solution to even be proposed, much less accepted. Even now, a key argument that the new conception is consistent is that nobody has managed to find an inconsistency. If that seems less than completely certain, that's because it is.

Several other paradoxes were discovered around the same time. One of the more interesting ones in my opinion, which was discovered somewhat later, is "Curry's paradox". It consists of this sentence: "If this sentence is true then 0=1". If you use the normal natural-language proof technique for proving an if/then statement, you can actually prove that sentence is true (it's not hard - try it). But if that sentence is true, then 0=1 - and you can prove that too, in the normal mathematical way. The fact that the normal techniques we use in everyday mathematics can prove 0=1 is certainly paradoxical, since each of those techniques seems fine on its own. Like Russell's paradox, Curry's paradox both casts doubt on our informal natural-language mathematics, and shows that certain formal theories that we might wish were consistent are actually inconsistent.

  • 5
    Curry's paradox is a modern version of Epicurius' Liar's Paradox,which centers around the natural-language sentence:"I am Lying." If the sentence is true,then it's false and converse. The entire discipline of metamathematics has developed largely to tackle problems like this and although a lot of "real" mathematicians consider such problems mere dinner theater and nothing that effects mathematics in "the real world",I would seriously take issue with that if they are simultaneously accepting logic and set theory-at least implicitly-as their foundations.2011-08-20
10

The significance of Russel's paradox is not just philosophical. Russel's paradox implies a contradiction in the presence of the unbounded axiom of comprehension:

$\exists s. \forall e. e\in s \leftrightarrow \phi$

where $\phi$ is the logical formula typically containing $e$. This axiom “creates” the set $s$ of all elements $e$ satisfying $\phi$. In other words, it turns properties into sets.

Let $r$ be the set of elements $e$ satisfying $e\notin e$. Then $r$ satisfies: $\forall e. e\in r \leftrightarrow e\notin e$. Instantiate $e$ to $r$: $r\in r \leftrightarrow r\notin r$. $p:=r\in r$ for clarity. Use $(p\leftrightarrow (\neg p))\rightarrow \bot$ valid in intuitionistic propositional logic. We've got a contradiction.

If you suspect there is a gap in my proof, I formalized it in Coq, but the accompanying text is mostly in Russian. To prove a contradiction, I need building blocks, which I introduced via “Variable” — the universe “all_sets”, the relation “in_set”, and our honey “comprehension”.

P.S. Contradictions in pure Coq are not found. ;)

  • 1
    So with unbounded comprehension you can infer '0=1' or 'False'?2011-03-06
7

Partially quoting Terence Tao, "One problem with this axiom ('Universal specification' or 'axiom of comprehension') is that it creates sets which are far too 'large' - for instance one can talk of a set of all objects (a so called universal set). Since sets are themselves objects, this means sets are allowed to contain themselves, which is somewhat silly state of affairs.One way to informally resolve it to think of objects as being arranged in hierarchy. .... " -- Analysis1, 2nd ed., Hindustan Book Agency, pp47

7

Much of what you say makes sense philosophically, and there are also ways to make it precise mathematically: For example, one result in reverse mathematics is that mathematicians often need even less complex sets than they use.

But I think you are actually asking several different questions.

Why did mathematicians take Russell's paradox seriously?

Did they? Those that were dealing with foundations certainly did, but I'd be surprised if that claim was true for the average mathematician.

The set of all sets admits all sorts of unmathematical objects right?

Well, that depends on how you define "set." In naive set theory, the idea that a set can contain any given object is a common point of view; I think it appeals to some pre-existing linguistic intuition about the word "set." But as you say:

I can't imagine a situation where a mathematician solving a concrete problem would invoke a set like that.

This is correct for a lot of mathematics, but there also are a lot of areas where you can easily get into trouble. Cardinal and ordinal numbers are the first examples, historically speaking (BTW, the Burali-Forti paradox apparantly predates Russell's paradox). Category theory is a more complicated case. One isn't necessarily tempted to invoke a "set of all sets," but similar things which are just as problematic (and arguably related).

But clearly important people think the result significant. It prompted Gottlob Frege, a smart and accomplished man, who Wikipedia tells me extended the study of logic in non-trivial ways, to say that the "foundations of [his] edifice were shaken."

I think you are generalizing too much from this sentence. Russell first stated his paradox explicitly about Frege's system. This is because Frege was basically the first person who tried to reduce all of mathematics to a single formal system. And then it turned out that his system, which took years to work out, could in fact prove every statement and was thus useless, technically speaking. It's not hard to imagine he was a bit disappointed.

Is there a practical example in mathematics that showcases this, where one might be led horribly astray if one doesn't place certain restrictions on sets, in say, dealing with PDEs, elliptic curves, functional equations?

I would answer "no" because whenever set-theoretic difficulties come up, the problematic sets turn out to be "tricky" in exactly the way you describe. However, being "tricky" is not a particularly solid criterion, and one that different people might have different opinions about. So when in doubt, mathematicians prefer to delegate such questions to a specific formal system, usually ZFC. That is, the criterion that is actually used nowadays is: "Can this set be constructed in ZFC?" If it can't, that doesn't necessarily mean that a contraction can arise from talking about it; this is where things become more interesting.

  • 1
    I'm not enough of a historian to know with certainty what the norm was. Certainly other prominent mathematicians in the early 20th century were interested in foundations. Later the Bourbaki were also mathematicians formemost. Category theory and topos theory were founded by mathematicians. So I think mathematicians "of stature" are just as likely to be interested in foundations, but I can't say whether they are *more* likely. In the early 20th century it was still possible to know the majority of math, and foundations were more accessible than today, when they almost require specialization.2011-03-03
6

Set theory's success was so great in the late nineteenth century that there were high hopes of making it a foundation for philosophy, let alone mathematics.

In particular, Frege had a simple ontology that solved several foundational problems in philosophy. For instance, "what is the number three?" To Frege, it was none other than the set of all triples. "What is the color blue?" It is the set of blue things, etc. In this way there is no need to create an ontological distinction between a property ("concept" if I understand the classical terminology correctly, which I may not) and its extension (the set of all things with that property) because there is a one to one correspondence between concepts and extensions.

This may seem pedantic, but it's a tremendously useful philosophical axe. Try to sit down and give a coherent definition of the difference between a "property" and a "thing" and what it means for a thing to have the property. It's not so simple. So 19th century set theory provided an answer to some ancient questions.

Unfortunately, the answer is wrong. The concept "S is a set and S does not contain itself" has no extension. This was Russell's original formulation of the paradox, I believe, and is why Frege was so upset by it.

  • 1
    Very nice answer giving the philosophical context, thanks!2015-10-04
4

Maybe this answer is just stating the obvious. If so I apologize in advance.

Often when one proves things in mathematics, one uses a proof by contradiction. This means that we assume the opposite of what we want to prove, make some deductions, and eventually deduce something absurd like $0=1$ or "$x\in X$ and $x \notin X$." The falsehood of this last statement then implies the truth of the original statement that we wanted to prove.

But you see now how this kind of logic breaks down if there is an inconsistency embedded in our everyday mathematics? Using proof by contradiction you could then "prove" any statement at all in the following way: "Assume by way of contradiction that A has a non-real eigenvalue. Let S be the set of all sets which do not contain themselves. [...] As this is a contradiction, A has only real eigenvalues." Even if it was in this case obvious that the contradiction had nothing to do with A and everything to do with the tacked-on Russell's paradox, this might not be obvious in a more complicated situation.

  • 0
    a highly satisfactory theory; and (iii) there is no obvious need for any additional theory of 'naive sets' ." It should be noted that he proves the consistency of the naive theory of properties by weakening e$x$cluded middle (he resolves the semantic paradoxes $b$y weakening excluded middle as well).2014-02-01
4

I think the key point in Russell's paradox is the self-reference. It was important as well in subsequent developments like Gödel's incompleteness theorems.

The possibility of self-reference is what in a way opens up a theory. Something that makes it richer. But also something that from an axiomatic point of view allows for the possibility of paradoxes.

Douglas Hofstadter has written a load of popular books on the subject.

4

Because it represented a contradiction in the current formulation of math. In math a contradiction will propagate and invalidate everything, you can use it to prove and disprove any statement. This paradox could not be solved by math, it required a reformulation of math.

  • 1
    @Mitch: There is a contradiction in the system, see my answer.2011-03-06
3

It's not too hard to show that given a logical contradiction, you can prove anything. Russell's paradox showed that a certain set of axioms were inconsistent. If followed then that these axioms could be used to prove any statement. The simplicity of Russell's paradox made it clear which axiom was problematic, and it's was removed from further treatments of the subject, and we hope that what remains is consistent.

The point is, if you have an inconsistent axiomatic system, then you can't really trust anything that you derive from it, because, well, everything is derivable. Take any mathematical fact that you think is important, $2\times 2=4$, $\{1, \dots, n\} \subseteq \{1, \dots, n+1\}$, etc. and you can prove the negation using the axioms that lead to Russell's paradox.

So it didn't really matter what Russell's paradox was per se (well, it did in the sense that it showed which axiom was problematic), so much as the fact that there was a paradox at all.

Also, keep in mind that this all happened before Gödel's incompleteness theorems. At the time, it was still believed by many mathematicians that it would be possible to, given any mathematical statement, algorithmically compute whether it was true or not under the accepted set of axioms. The fact that there was a hole in the currently accepted set of axioms was therefore a big deal.

2

I cannot say it for russels paradox itself, but for computer science analogons. There are Questions, which can fundamentally not be answered. Not because of too few knowledge or power, but because of logical "reason". With Undecidability, this seems to be "obvious" today. But: Back then, the mathematicans thought, they just has to provide the right set, that they could solve every problem in the world. That there would be no theoretically unsolvable problems.

This is a so huge fact, that it takes some time, to really acknowledge it without any trivialization..

2

Instead of giving you an answer that expresses an opinion or a particular point of view (regardless of how widespread or not that point of view might be), I would like to give you a list of source material that might be helpful to you.

First, in order to understand why the mathematical and logical communities take Russell's paradox seriously, I would urge you read the SEP (Stanford Encyclopedia of Philosophy) article "Frege's Theorem and Foundations for Arithmetic" sections 1 and 2 (you can find SEP articles on the Web). Reading these sections will help you understand Frege's "Basic Law V" from which all the trouble sprang. After digesting these sections, I would urge you to read the rest of the article in order to appreciate the significance of Frege's work on the foundations of arithmetic irrespective of the problems with Basic Law V.

Second, find a copy of Jean van Heijenoort's book "From Frege to Godel: A Source Book in Mathematical Logic, 1879 to 1931". In it you will find (in translation) Russell's letter to Frege announcing his discovery of the paradox and Frege's reply to Russell. Pay particular attention to his (Russell's) conclusion that "under certain circumstances a definable collection [Menge] does not form a totality." This ties in to the notion of proper class as well as (to the discerning reader) the possibility of 'roads not taken'.

Third, I would urge you to read the following paper by Thoralf Skolem, "Investigations on a Comprehension Axiom without Negation in the Defining Propositional Functions". In this paper, Skolem proves the existence of "domains" (i.e. models) such that the axiom of comprehension was satisfied for elementary propositional functions $\phi$, that is $\phi$ being built from atomic propositions u$\in$v by use of conjunction and disjunction, provided only conjunction, disjunction, and u$\in$v are allowed in $\phi$. He also shows that for these models the axiom of extensionality also holds. This shows that there are consistent fragments of naive set theory, in answer to your second question.

Finally, I urge you to look up and read any and all articles by the following Authors: Olivier Esser, Ross Brady, Thierry Libert, Roland Hinnion, and Zach Weber, among others. These researchers are doing interesting work in naive set theory.

I hope you find this helpful. Happy reading.

0

Mathematics must ultimately be based on a limited collection of rules and axioms of logic and set theory. If you don't stray too far, you can probably get away with ignoring most if not all the finer points.

The domain of discourse for most mathematicians is just a few well-defined sets of numbers or points in space, and sets constructed from them. When most mathematicians make generalizations, it is not usually about every object in the universe, but only about things like numbers or points. This greatly simplifies matters to the point that weird situations like Russell's Paradox never actually comes up in practice. For example, there is nothing paradoxical about a set $r$ such that $\forall x\in N:[x\in r \iff x\notin x].$ You just have $r\notin N$ and that's the end of it! Likewise, if you define $r$ as a subset of $N$ such that $\forall x:[x\in r \iff x\in N \land x\notin x].$ Then you get $r\notin N$ and $r\notin r.$

The above mentioned rules and axioms, however, have to cover every eventuality. If you are going to be making generalizations about every object in the universe -- somebody has to! -- you have to guard against beasties in the set-theoretic wilderness like Russell's Paradox.

Some form of restricted comprehension axiom prevents the construction of the so-called Russell Set. If you are always working with some underlying set(s), comprehension is automatically restricted. Problems of comprehension can only occur when you define those underlying sets. If they are consistently defined (a big IF), you can pretty much ignore any concerns about comprehension after that.

0

While Russell's paradox may seem like a small technicality, it disproves one of the very foundations of mathematics, so it has some drastic implications.

For example: Using Curry's paradox, a variant of Russell's paradox, you can prove that $0 = 1$.

Discovering that not every definable collection is a set was like discovering that $π$ is not actually a number, and that while you can treat it like a number for the purposes of multiplying and dividing, $\sqrt[x]{π}$ is actually undefined, so every mathematical proof that uses $\sqrt[x]{π}$ could potentially be wrong, and would have to be reconsidered.

  • 0
    No, not in $\sf ZFC$. But there is other set theories outside of $\sf ZFC$.2015-04-20
-5

Fortunately, set theory isn't that important to modern math. But category theory is, and an analogue of Russell's paradox stops you from constructing what would otherwise be one of the most obvious things to construct, the category of categories.

In practice, I've seen a bunch of expositions that go "Let $\mathbf{Cat}$ be the category of all (small) categories..." with a bit of a wink and a nudge to get you on the right track. So I don't think this is a terribly important issue -- but it does give a natural place for a working mathematician to get accidentally involved in set theory.

By Russell's paradox proper, there's also no set of groups, rings, topological spaces, and so on, but this can be remedied by introducing proper classes, and as far as I can tell, you'd never want to topologize the class of topological spaces or something like that.

Edit: I realized your question was more historical. Russell came at a time of tremendous vagueness in math, and his work was largely an effort to eliminate such vagueness. It was surprising that such a project could possibly have nontrivial results. Frege, specifically, had been working on a massive treatise on logic that was totally destroyed by Russell's paradox, because it relied so heavily on sets whose elements could come from anywhere. If you're interested, Logicomix is a really good graphic novel about Russell's life and work -- addressed to non-mathematicians, but a good read and helps motivate issues like these.

  • 4
    -1: I like set theory.2014-01-31