Russell's paradox (also known as Russell's antinomy), discovered by Bertrand Russell in 1901, showed that some attempted formalizations of the naïve set theory created by Georg Cantor led to a contradiction.

Russell’s paradox

Bertrand Russell (1872-1970) was involved in an ambitious project to rewrite all the truths of mathematics in the language of sets. In fact, what he was trying to do was show that all of mathematics could be derived as the logical consequences of some basic principles using sets. At this time (around 1900), it was generally believed that any property of objects could define a set. For example, the property “x is a natural number between four and seven” defines the set {4, 5, 6, 7}. We could also write this set as {x| x is a natural number between 4 and 7}. What was believed was precisely that for any property “P” that you can think of, it made sense to talk about the set {x| x has property P}. Certainly, sets that consist of numbers make sense this way. But when you allow any objects in your sets, you can run into trouble.

Russell was the first one to notice this.

Russell’s insight was the following. First, it is possible for a set to be an element of itself. (Remember that elements are the objects which make up the set, e.g. the number 4 is an element of the set {4, 5, 6, 7}). An example of a set which is an element of itself is {x| x is a set and x has at least one element}.

This set contains itself, because it is a set with at least one element. Using this knowledge, Russell defined a special set, which we’ll call “R”. R is the set {x| x is a set and x is not an element of itself}.

Russell then asked: is R an element of the set R? Let’s think about this question.

If R is an element of R, that exactly means that it is an element of itself.

Which means that it can’t possibly be in R - by definition R is the collection of all sets which are not elements of themselves.

Since this option is impossible, we must agree that R is not an element of R.

But in that case, R is not an element of itself, so by definition it belongs to the collection of sets which are not elements of themselves. Uh-oh! [It is worth pausing a minute here and reassessing the situation on your own. Do you believe that R is an element of R or not? Neither? What’s the problem?]

Mathematicians and logicians thought for a while that the problem with the set R was going to undermine their whole project to do all mathematics in terms of set theory. Fortunately, they eventually came up with a technical solution that changes the way sets are constructed (slightly) and prevents R from being considered a set (whew!). This technical solution is why you sometimes see a set being described in the form {x ? X| x has property P}, where “X” is supposed to denote some other set, or “the universe” (whatever that means!) We won’t worry about that issue in our class, as most of our sets will be sets of numbers and these are always safe.

So did Russell succeed? Yes and no. The program to do all mathematics in terms of set theory was the birth of modern day logic, a rich and exciting area of mathematics. But ultimately, the logician Kurt G¨odel showed that the original goal of the project – to deduce all mathematics from some axioms (rules) concerning sets – was itself mathematically impossible!

For more details on this story, I recommend the excellent book Logicomix by Doxiades and Papadimitriou. You may be delighted to know that a) it’s a graphic novel and b) the Reg library has a copy.

Sun, Mar 28, 2021

In the foundations of mathematics, Russell's paradox (also known as Russell's antinomy), discovered by Bertrand Russell in 1901,[1][2] showed that some attempted formalizations of the naive set theory created by Georg Cantor led to a contradiction. The same paradox had been discovered in 1899 by Ernst Zermelo[3] but he did not publish the idea, which remained known only to David Hilbert, Edmund Husserl, and other members of the University of Göttingen. At the end of the 1890s Cantor himself had already realized that his definition would lead to a contradiction, which he told Hilbert and Richard Dedekind by letter.[4]

According to naive set theory, any definable collection is a set. Let R be the set of all sets that are not members of themselves. If R is not a member of itself, then its definition dictates that it must contain itself, and if it contains itself, then it contradicts its own definition as the set of all sets that are not members of themselves. This contradiction is Russell's paradox. Symbolically:

{\displaystyle {\text{Let }}R=\{x\mid x\not \in x\}{\text{, then }}R\in R\iff R\not \in R}{\text{Let }}R=\{x\mid x\not \in x\}{\text{, then }}R\in R\iff R\not \in R In 1908, two ways of avoiding the paradox were proposed: Russell's type theory and the Zermelo set theory. Zermelo's axioms went well beyond Gottlob Frege's axioms of extensionality and unlimited set abstraction; as the first constructed axiomatic set theory, it evolved into the now-standard Zermelo–Fraenkel set theory (ZFC). The essential difference between Russell's and Zermelo's solution to the paradox is that Zermelo altered the axioms of set theory while preserving the logical language in which they are expressed, while Russell altered the logical language itself. The language of ZFC, with the help of Thoralf Skolem, turned out to be first-order logic.[5]

https://en.wikipedia.org/wiki/Russell%27s_paradox