The barber shaves. Bertrand Russell's Paradox

The most famous of the paradoxes discovered already in our century is the antinomy discovered by B. Russell. The idea was in the air, and its publication produced the impression of an exploding bomb. This paradox caused in mathematics, according to D. Hilbert, "the effect of complete catastrophe." The simplest and most important logical methods, the most common and useful concepts, are under threat. It immediately became obvious that neither in logic nor in mathematics, in the entire long history of their existence, was anything decidedly worked out that could serve as a basis for eliminating the antinomy. Clearly a departure from habitual ways of thinking was necessary.

Russell's paradox in its original form is connected with the concept of a set, or a class. We can talk about sets of different objects, for example, about the set of all people or about the set of natural numbers. An element of the first set will be any individual person, an element of the second - every natural number. It is also possible to consider sets themselves as some objects and speak of sets of sets. One can even introduce such concepts as the set of all sets or the set of all concepts. With respect to any set arbitrarily taken, it seems reasonable to ask whether it is its own element or not. Sets that do not contain themselves as an element will be called ordinary. For example, the set of all people is not a person, just as the set of atoms is not an atom. Sets that are proper elements will be unusual. For example, a set that unites all sets is a set and therefore contains itself as an element. Obviously, every set is either ordinary or unusual.

Consider now the set of all ordinary sets. Since it is a set, one can also ask about it whether it is ordinary or unusual. The answer, however, is discouraging. If it is ordinary, then by definition it must contain itself as an element, since it contains all ordinary sets. But this means that it is an unusual set. The assumption that our set is an ordinary set thus leads to a contradiction. So it can't be normal. On the other hand, it cannot be unusual either: an unusual set contains itself as an element, and the elements of our set are only ordinary sets. As a result, we come to the conclusion that the set of all ordinary sets cannot be either ordinary or extraordinary.

Thus, the set of all sets that are not proper elements is a proper element if and only if it is not such an element. This is a clear contradiction.

The contradiction says that such a set simply does not exist. But why can't it exist? After all, it consists of objects that satisfy a well-defined condition, and the condition itself does not seem to be somehow exceptional or obscure. If a set so simply and clearly defined cannot exist, then what, in fact, is the difference between possible and impossible sets? The conclusion about the non-existence of the considered set sounds unexpected and inspires anxiety. It makes our general notion of a set amorphous and chaotic, and there is no guarantee that it cannot give rise to some new paradoxes.

Russell's paradox is remarkable for its extreme generality. For its construction, no complex technical concepts are needed, as in the case of some other paradoxes, the concepts of "set" and "element of the set" are sufficient. But this simplicity just speaks of its fundamental nature: it touches on the deepest foundations of our reasoning about sets, since it speaks not about some special cases, but about sets in general.

Russell's paradox is not specifically mathematical. It uses the concept of a set, but does not touch on any special properties associated specifically with mathematics. This becomes apparent when the paradox is reformulated in purely logical terms.

Of every property one can, in all probability, ask whether it is applicable to itself or not. The property of being hot, for example, does not apply to itself, since it is not itself hot; the property of being concrete also does not refer to itself, for it is an abstract property. But the property of being abstract, being abstract, is applicable to oneself. Let us call these properties inapplicable to themselves inapplicable. Does the property of being inapplicable to oneself apply? It turns out that an inapplicability is inapplicable only if it is not. This is, of course, paradoxical. The logical, property-related variety of Russell's antinomy is just as paradoxical as the mathematical, set-related variety.

B. Russell also proposed the following popular version of the paradox he discovered. “The barber shaves all those and only those residents of the city who do not shave themselves. Who shaves the barber?" The paradox of the barber lies in the fact that, allegedly, it is impossible to answer this question.

To understand the situation, we will divide the inhabitants of the city into three groups. This breakdown is shown in the left figure: those who shave themselves are on top; those who are shaved - from below; those who don't shave at all (monks, children, women...) are outside the ellipse.

Consider first the action of condition (1). Let the barber shave all those who do not shave themselves, that is, the entire lower half of the ellipse (hatching marks the barber's clients). But condition (1) allows him to shave and the one who shaves himself, that is, himself. Condition (1) allows him to position himself in the upper half of the ellipse, where the inhabitants themselves shave, and shave themselves there. This is shown in the middle picture.

If condition (2) applies, and the barber shaves only those who do not shave themselves, this means that he shaves part of the lower half of the ellipse and does not shave himself, that is, he is not in the upper half of the ellipse. But the inhabitants of the lower half may not be shaved by a barber, but by someone else. And a barber can be among these people (right figure). So the barber can shave his friend, and the barber will shave the shaded part of the lower half of the ellipse.

But if both conditions (1) and (2) apply, then the barber has no place in the ellipse. He doesn't shave at all. And there is no paradox here. He, therefore, is either a monk, or a robot, or a child, or a woman, or a non-resident of the city ... And if there is no one in the city except shaving men, and, therefore, the appearance of the ellipse is empty, then a barber that satisfies the conditions (1) and (2) simply does not exist. It is absurd to ask in this case who shaves him. Many such barbers are empty.

And here we will notice that the question asked, "Who shaves the barber?", was incorrect from the very beginning, just like the classic question: "Why do you beat your father?" Before asking who shaves the barber, one must obtain agreement that someone shaves him.

The argument about the hairdresser can be called a pseudo-paradox. In its course, it is strictly analogous to Russell's paradox, and this is what makes it interesting. But it is still not a true paradox.

Another example of the same pseudo-paradox is the well-known catalog argument.

A certain library decided to compile a bibliographic catalog that would include all those and only those bibliographic catalogs that do not contain references to themselves. Should such a directory include a link to itself? It is easy to show that the idea of creating such a catalog is not feasible; it simply cannot exist, because it must simultaneously include a reference to itself and not include. It is interesting to note that cataloging all directories that do not contain references to themselves can be thought of as an endless, never ending process.

Let's say that at some point a directory was compiled, say K1, that included all other directories that did not contain references to themselves. With the creation of K1, another directory appeared that does not contain a reference to itself. Since the goal is to make a complete catalog of all directories that do not mention themselves, it is obvious that K1 is not the solution. He doesn't mention one of those directories - himself. Including this mention of himself in K1, we get the K2 catalog. It mentions K1 but not K2 itself. Adding such a mention to K2, we get K3, which is again incomplete due to the fact that it does not mention itself. And so on without end.

abridged and amended chapter from the work
"Logical paradoxes. Solutions»

B. Russell's paradox "About the hairdresser (barber, barber)"

Shaved barber or again about the hairdresser

At the beginning of the 20th century, Bertrand Russell discovered a logical paradox. He reported about it in his letter to the famous mathematician, philosopher and logician Gottlob Frege - the founder of modern logical semantics - when he "in 1902 already submitted the second volume of the Fundamentals of Arithmetic for printing." The letter "reported a formal contradiction in Frege's proposed justification for arithmetic (Russell's paradox), which Frege tried in vain to resolve until the end of his life. However, it was Russell who brought Frege wide fame, because in Russell's presentation (special supplement to the Foundations of Mathematics, 1903) Frege's concept became accessible to a wide circle of readers. End of quote http://www.krugosvet.ru/articles/92/1009213/1009213a1.htm).
Not only Frege, but no one else for more than a hundred years to this day has not been able to solve this logical paradox. Nobody except me.

"Russell's paradox in its original form is associated with the concept of a set, or class" (Ivin A. A. The art of thinking correctly. - M .: Education. - 1998). In this form, the solution is in another article: Russell's paradox - the original version - about sets, But the whole world knows it in a different formulation. Russell “offered the following popular version of the paradox he discovered in mathematical set theory.
Let us imagine that the council of one village defined the duties of the barber of that village as follows: to shave all the men of the village who do not shave themselves, and only these men. Should he shave himself? (Ivin A. A. The art of thinking correctly. - M .: Education. - 1990, pp. 205 - 206, http://www.koob.ru/books/iskusstvo_pravilno_mislit.rar).

There were many distortions of the paradox, as well as attempts to resolve this contradiction, but basically all the solutions came down to the following.
“If yes (i.e. the barber must shave himself - my insert), then he will refer to those who shave themselves, and those who shave themselves, he should not shave. If not, then he will belong to those who do not shave themselves, and, therefore, he will have to shave himself. We thus come to the conclusion that this barber shaves himself if and only if he does not shave himself. Which, of course, is impossible.

The argument about the barber is based on the assumption that such a barber exists. The resulting contradiction means that this assumption is false and there is no such villager who would shave all those and only those of its inhabitants who do not shave themselves. The duties of a hairdresser do not seem contradictory at first glance, so the conclusion that there cannot be one sounds somewhat unexpected. However, this conclusion is not paradoxical. The condition that the village barber must satisfy is, in fact, self-contradictory and therefore impossible. There cannot be such a hairdresser in a village for the same reason that there is no person in it who would be older than himself or who would be born before his birth. The argument about the hairdresser can be called a pseudo-paradox." End of quote (ibid.).

DECISION

In 1992, on December 19, the TV game “What? Where? When?". With the score 2:6, as it often happens, a disputable, even conflict situation arose. And then Vladimir Yakovlevich Voroshilov asked a question that was supposed to bring victory or defeat to experts. It was the barber question, Russell's paradox. Of course, the experts lost, although they could have won. Because he asked a slightly distorted version of the question: “The question is: does the barber shave himself if the barber shaves everyone who does not shave himself?
The answer of experts: no, he does not shave. (Chronicle / "What? Where? When? Production Center IGRA-TV", http://chgk.tvigra.ru/letopis/?19921219#cur). They had to answer: “From the information that a barber shaves everyone who does not shave himself, it is impossible to conclude whether he shaves himself, whether someone else shaves him, or he does not shave at all. Because there are no sufficient grounds for such conclusions.
But this paradox haunted me. It seemed that the answer was spinning in my head, you just need to "grab it by the tail." And after a while I succeeded.

The decision, as is often the case, is simply insane. The whole discussion in detail and with consideration of distorted options takes up several pages. I will give only an abbreviated version of the argument.

The answer to the question of Russell's paradox is possible if we attribute the barber to any class of men: "they shave themselves" or "they do not shave themselves." But after a logical analysis of the possible grounds for referring to these classes of sets of men, the only conclusion follows is that this is impossible, because such a logically justified ground does not exist. Based on this conclusion, many, including A. A. Ivin, came to the conclusion that the paradox is unsolvable, calling it a pseudo-paradox. But then all other paradoxes should be “solved” in this way once and for all. After all, no one thinks that in reality there can be a situation of a conversation between a mother and a crocodile, a missionary and cannibals and others. Hence, the negation of the logical assumption is not a solution. And the solution is:

If it is impossible to attribute a hairdresser to any of the classes "shave themselves" and "do not shave themselves", then he must be included in the third class - "DO NOT SHAVE". And then the hairdresser does not violate any of the logical conditions, because they do not apply to this class of men.

All the men of the village

A. SHAVING 1 - themselves, 2- not themselves B. DO NOT SHAVING

And now the barber is destined to die bearded.

For a correct understanding of this task, it was only necessary to mentally rearrange the particle “not” before the verb “shave” to the place after it. And then the meaning of the paradoxical condition of the problem would appear, as on photographic paper during printing. After all, the phrase “do not shave themselves” immediately took the form of an absolutely simple, not confusing and understandable to anyone. Namely - “DO NOT shave themselves” means “DO NOT shave themselves”, that is, they still shave, although not with their own hands. And thus, an obvious and gross error in the logical reasoning of all those who tried to solve this paradox immediately appears. I called this type of error “false conclusion”, when an absolutely incorrect and even opposite conclusion is made from the logically necessary conclusion (“Logical paradoxes. Solutions”, chapter “Errors of reasoning - false conclusion”,). In this problem, the “false conclusion” is that the phrase in logical reasoning should not sound like: “if the barber should not shave himself, then he will refer to those who do not shave themselves”, which is incorrect, but in the form: "if a barber is not supposed to shave himself, then he will refer to those who do not shave themselves or DO NOT SHAVES."

After solving the “Russell paradox”, I also solved other well-known paradoxes by applying two general postulates to them: 1. when approaching the solution of any problem, a clear understanding of the problem itself in all details is necessary; 2. knowledge is a relative concept (“Logical paradoxes. Ways of solution”, chapter “On the principles of solving paradoxes”,

The most famous of the paradoxes discovered already in the last century is the antinomy discovered by Bertrand Russell and communicated by him in a letter to G. Ferge. Russell discovered his paradox related to the field of logic and mathematics in 1902. The same antinomy was discussed simultaneously in Göttingen by the German mathematicians Z. Zermelo (1871-1953) and D. Hilbert. The idea was in the air, and its publication gave the impression of an exploding bomb Miroshnichenko P.N. What destroyed Russell's paradox in Frege's system? // Modern logic: problems of theory, history and application in science. - SPb., 2000. - S. 512-514. . This paradox caused in mathematics, according to Hilbert, the effect of complete catastrophe. The simplest and most important logical methods, the most common and useful concepts, are under threat. It turned out that in Cantor's set theory, which was enthusiastically accepted by most mathematicians, there are strange contradictions that are impossible, or at least very difficult, to get rid of. Russell's paradox brought these contradictions to light with particular clarity. The most outstanding mathematicians of those years worked on its resolution, as well as on the resolution of other found paradoxes of Cantor's set theory. It immediately became obvious that neither in logic nor in mathematics, in the entire long history of their existence, was anything decidedly worked out that could serve as a basis for eliminating the antinomy. Clearly a departure from habitual ways of thinking was necessary. But from where and in what direction? Courant R., Robbins G. What is mathematics? - Ch. II, § 4.5.

How radical was the rejection of established ways of theorizing supposed to be? With further study of antinomy, the conviction in the need for a fundamentally new approach steadily grew. Half a century after its discovery, specialists in the foundations of logic and mathematics L. Frenkel and I. Bar-Hillel already stated without any reservations: , so far invariably failed, are obviously insufficient for this purpose. The modern American logician H. Curry wrote a little later about this paradox: “In terms of the logic known in the 19th century, the situation simply defied explanation, although, of course, in our educated age there may be people who see (or think they see ), what is the mistake” Miroshnichenko P.N. What destroyed Russell's paradox in Frege's system? // Modern logic: problems of theory, history and application in science. - SPb., 2000. - S. 512-514 ..

Since it is a set, one can also ask about it whether it is ordinary or unusual. The answer, however, is discouraging. If it is ordinary, then by definition it must contain itself as an element, since it contains all ordinary sets. But this means that it is an unusual set. The assumption that our set is an ordinary set thus leads to a contradiction. So it can't be normal. On the other hand, it cannot be unusual either: an unusual set contains itself as an element, and the elements of our set are only ordinary sets. As a result, we come to the conclusion that the set of all ordinary sets cannot be either ordinary or extraordinary.

Thus, the set of all sets that are not proper elements is a proper element if and only if it is not such an element. This is a clear contradiction. And it was obtained on the basis of the most plausible assumptions and with the help of seemingly indisputable steps. The contradiction says that such a set simply does not exist. But why can't it exist? After all, it consists of objects that satisfy a well-defined condition, and the condition itself does not seem to be somehow exceptional or obscure. If a set so simply and clearly defined cannot exist, then what, in fact, is the difference between possible and impossible sets? The conclusion that the set under consideration does not exist sounds unexpected and worrisome. It makes our general notion of a set amorphous and chaotic, and there is no guarantee that it cannot give rise to some new paradoxes.

Russell's paradox is remarkable for its extreme generality Courant R., Robbins G. What is mathematics? - Ch. II, § 4.5. . For its construction, no complex technical concepts are needed, as in the case of some other paradoxes, the concepts of "set" and "element of the set" are sufficient. But this simplicity just speaks of its fundamental nature: it touches on the deepest foundations of our reasoning about sets, since it speaks not about some special cases, but about sets in general.

Other variants of the paradox Russell's paradox is not specifically mathematical. It uses the concept of a set, but does not touch on any special properties associated specifically with mathematics.

This becomes apparent when the paradox is reformulated in purely logical terms. Of every property one can, in all probability, ask whether it is applicable to itself or not. The property of being hot, for example, does not apply to itself, since it is not itself hot; the property of being concrete also does not refer to itself, for it is an abstract property. But the property of being abstract, being abstract, is applicable to oneself.

Let us call these properties inapplicable to themselves inapplicable. Does the property of being inapplicable to oneself apply? It turns out that inapplicability is inapplicable only if it is not. This is, of course, paradoxical. The logical, property-related version of Russell's antinomy is just as paradoxical as the mathematical, set-related version.

Russell also proposed the following popular version of the paradox discovered by him Katrechko S.L. Russell's Barber's Paradox and Plato-Aristotle's Dialectic // Modern Logic: Problems of Theory, History and Application in Science. - SPb., 2002. - S. 239-242 .. Let's imagine that the council of one village defined the barber's duties in this way: to shave all the men of the village who do not shave themselves, and only these men. Should he shave himself? If so, it will refer to those who shave themselves, and those who shave themselves, he should not shave. If not, he will belong to those who do not shave themselves, and therefore he will have to shave himself. We thus come to the conclusion that this barber shaves himself if and only if he does not shave himself. This, of course, is impossible.

The argument about the barber is based on the assumption that such a barber exists. The resulting contradiction means that this assumption is false, and there is no such villager who would shave all those and only those villagers who do not shave themselves. The duties of a barber do not seem contradictory at first glance, so the conclusion that there cannot be one sounds somewhat unexpected. However, this conclusion is not paradoxical. The condition that the village barber must satisfy is, in fact, self-contradictory and therefore impossible. There cannot be such a hairdresser in the village for the same reason that there is no person in it who would be older than himself or who would be born before his birth Miroshnichenko P.N. What destroyed Russell's paradox in Frege's system? // Modern logic: problems of theory, history and application in science. - SPb., 2000. - S. 512-514 ..

The argument about the barber can be called a pseudo-paradox. In its course, it is strictly analogous to Russell's paradox, and this is what makes it interesting. But it is still not a true paradox.

Another example of the same pseudo-paradox is the well-known catalog argument. A certain library decided to compile a bibliographic catalog that would include all those and only those bibliographic catalogs that do not contain references to themselves. Should such a directory include a link to itself? It is easy to show that the idea of creating such a catalog is not feasible; it simply cannot exist, because it must simultaneously include a reference to itself and not include.

It is interesting to note that cataloging all directories that do not contain references to themselves can be thought of as an endless, never ending process. Let's say that at some point a directory, say K1, was compiled, including all other directories that do not contain references to themselves. With the creation of K1, another directory appeared that does not contain a link to itself. Since the goal is to make a complete catalog of all directories that do not mention themselves, it is obvious that K1 is not the solution. He doesn't mention one of those directories -- himself. Including this mention of himself in K1, we get the K2 catalog. It mentions K1, but not K2 itself. Adding such a mention to K2, we get KZ, which again is not complete due to the fact that it does not mention itself. And on without end.

One more logical paradox can be mentioned - the paradox of the Dutch mayors, similar to the paradox of the barber. Every municipality in Holland must have a mayor and two different municipalities cannot have the same mayor. Sometimes it turns out that the mayor does not live in his municipality. Let us suppose that a law is passed by which some territory S is allocated exclusively to such mayors who do not live in their municipalities, and directing all these mayors to settle in this territory. Suppose further that there are so many of these mayors that the territory S itself forms a separate municipality. Where should the mayor of this Special Municipality S reside? Simple reasoning shows that if the mayor of a Special Municipality lives in territory S, then he should not live there, and vice versa, if he does not live in the territory, then he must live in this territory. That this paradox is analogous to the barber's paradox is quite obvious.

Russell was one of the first to propose a solution to “his” paradox. The solution he proposed was called "type theory": a set (class) and its elements belong to different logical types, the type of a set is higher than the type of its elements, which eliminates Russell's paradox (type theory was also used by Russell to solve the famous "Liar" paradox) . Many mathematicians, however, did not accept Russell's solution, believing that it imposes too severe restrictions on the mathematical statements of Katrechko S.L. Russell's Barber's Paradox and Plato-Aristotle's Dialectic // Modern Logic: Problems of Theory, History and Application in Science. - St. Petersburg, 2002. - S. 239-242 ..

The situation is similar with other logical paradoxes. “The antinomies of logic,” writes von Wright, “have puzzled us since their discovery and will probably always puzzle us. We should, I think, regard them not so much as problems waiting to be solved, but as inexhaustible raw material for thought. They are important because thinking about them touches upon the most fundamental questions of all logic, and therefore all thinking” Wrigt G.Kh. background. Logic and philosophy in the XX century // Vopr. philosophy. 1992. No. 8..

Russell's paradox (Russell's antinomy, also Russell-Zermelo paradox) - a set-theoretic paradox (antinomy) discovered in 1901 by Bertrand Russell, demonstrating the inconsistency of Frege's logical system, which was an early attempt to formalize the naive set theory of Georg Cantor. Previously discovered but not published by Ernst Zermelo.

In informal language, the paradox can be described as follows. Let us agree to call a set "ordinary" if it is not its own element. For example, the set of all people is "ordinary", since the set itself is not a person. An example of an "unusual" set is the set of all sets, since it is itself a set, and therefore is itself a proper element.

One can consider a set consisting only of all "ordinary" sets, such a set is called Russell set . A paradox arises when trying to determine whether this set is "ordinary" or not, that is, whether it contains itself as an element. There are two possibilities.

On the one hand, if it is "ordinary", then it must include itself as an element, since by definition it consists of all "ordinary" sets. But then it cannot be "ordinary", since "ordinary" sets are those that do not include themselves.
It remains to be assumed that this set is "unusual". However, it cannot include itself as an element, since by definition it must only consist of "ordinary" sets. But if it does not include itself as an element, then it is an "ordinary" set.

In any case, a contradiction results.

Encyclopedic YouTube

1 / 5

✪ Lecture 1. Definition of a set. De Morgan's laws. Russell's paradox. Weierstrass theorem

✪ 3 Russell's Paradox

✪ Bertrand Russell Advice to future generations

✪ Lecture 21: Naive set theory and fuzzy logic

✪ Monty Hall Paradox - Numberphile

Subtitles

Formulation of the paradox

Russell's paradox can be formulated in naive set theory. Therefore, naive set theory is inconsistent. A contradictory fragment of naive set theory, which can be defined as a first-order theory with a binary membership relation ∈ (\displaystyle \in ) and selection scheme: for every logical formula with one free variable in naive set theory there is an axiom

∃ y ∀ x (x ∈ y ⟺ P (x)) (\displaystyle \exists y\forall x(x\in y\iff P(x))).

This axiom scheme says that for any condition P (x) (\displaystyle P(x)) there are many y , (\displaystyle y,) consisting of those x , (\displaystyle x,) which satisfy the condition P (x) (\displaystyle P(x)) .

This is enough to formulate Russell's paradox as follows. Let be P (x) (\displaystyle P(x)) there is a formula x ∉ x . (\displaystyle x\notin x.)(I.e P (x) (\displaystyle P(x)) means that many x (\displaystyle x) does not contain itself as an element, or, in our terminology, is an "ordinary" set.) Then, by the axiom of selection, there is a set y (\displaystyle y)(Russell set) such that

∀ x (x ∈ y ⟺ x ∉ x) (\displaystyle \forall x(x\in y\iff x\notin x)).

Since this is true for any x , (\displaystyle x,) that is also true for x = y. (\displaystyle x=y.) I.e

y ∈ y ⟺ y ∉ y . (\displaystyle y\in y\iff y\notin y.)

It follows from this that a contradiction is deduced in naive set theory.

The paradox would not arise if we assumed that the Russell set does not exist. However, this assumption itself is paradoxical: in Cantor's set theory, it is believed that any property determines the set of elements that satisfy this property. Since the property of a set to be "ordinary" seems well-defined, there must be a set of all "ordinary" sets. This theory is now called naive set theory .

Popular versions of the paradox

There are several versions of Russell's paradox. Unlike the paradox itself, they, as a rule, cannot be expressed in a formal language.

Liar paradox

Russell's paradox is related to the liar's paradox known since ancient times, which is the following question. Given a statement:

This statement is false.

Is this statement true or not? It is easy to show that this statement can neither be true nor false.

Russell wrote about this paradox:

Russell himself explained the liar paradox in this way. In order to say something about utterances, one must first define the very concept of "utterance", while not using concepts that have not yet been defined. Thus, statements of the first type can be defined which say nothing about statements. Then one can define statements of the second type that speak of statements of the first type, and so on. The statement "this statement is false" does not fall under any of these definitions, and thus does not make sense.

The Barber's Paradox

Russell mentions the following version of the paradox, formulated as a riddle that someone suggested to him.

Let a barber live in a certain village, who shaves all the inhabitants of the village who do not shave themselves, and only them. Does the barber shave himself?

Any answer leads to a contradiction. Russell notes that this paradox is not equivalent to his paradox and is easily solved. Indeed, just as Russell's paradox shows that there is no Russell set, the barber's paradox shows that no such barber exists. The difference is that there is nothing surprising in the non-existence of such a barber: not for any property there is a barber who shaves people with this property. However, the fact that there is no set of elements given by some well-defined property contradicts the naive idea of sets and requires explanation.

Option about directories

The closest wording to Russell's paradox is the following version of his presentation:

Bibliographic catalogs are books that describe other books. Some directories may describe other directories. Some directories can even describe themselves. Is it possible to catalog all catalogs that do not describe themselves?

A paradox arises when trying to decide whether this directory should describe itself. Despite the apparent closeness of the formulations (this is actually Russell's paradox, in which catalogs are used instead of sets), this paradox, like the barber's paradox, is resolved simply: such a catalog cannot be compiled.

Grelling-Nelson paradox

This paradox was formulated by German mathematicians Kurt Grelling and Leonard Nelson in 1908. It is in fact a translation of Russell's original version of the paradox, stated by him in terms of predicate logic (see letter to Frege), into non-mathematical language.

Let's call the adjective reflective if this adjective has the property defined by this adjective. For example, the adjectives "Russian", "polysyllabic" - have the properties that they define (the adjective "Russian" is Russian, and the adjective "polysyllabic" is polysyllabic), so they are reflexive, and the adjectives "German", "monosyllabic" - are non-reflexive. Will the adjective "non-reflexive" be reflexive or not?

Any answer leads to a contradiction. Unlike the barber's paradox, the solution to this paradox is not so simple. One cannot simply say that such an adjective ("non-reflexive") does not exist, since we have just defined it. The paradox arises from the fact that the definition of the term "non-reflexive" is incorrect in itself. The definition of this term depends on values the adjective to which it applies. And since the word "non-reflexive" is itself an adjective in the definition, a vicious circle ensues.

Story

Russell probably discovered his paradox in May or June 1901. According to Russell himself, he was trying to find an error in Cantor's proof of the paradoxical fact (known as Cantor's paradox) that there is no maximum cardinal number (or set of all sets). As a result, Russell got a simpler paradox. Russell communicated his paradox to other logicians, notably Whitehead and Peano. In his letter to Frege on June 16, 1902, he wrote that he had found a contradiction in " Concept Calculus” - a book by Frege, published in 1879. He laid out his paradox in terms of logic and then in terms of set theory, using Frege's definition of a function:

I experienced difficulties in only one place. You claim (p. 17) that a function can itself act as an unknown. I used to think so too. But now this view seems doubtful to me because of the following contradiction. Let be w predicate: "to be a predicate which cannot be applied to itself." Can w be applicable to itself? Any answer implies the opposite. Therefore, we must conclude that w is not a predicate. Similarly, there is no class (as a whole) of those classes which, taken as a whole, do not belong to themselves. From this I conclude that sometimes a certain set does not form a holistic formation.

Original text (German)
Nur in einem Punkte ist mir eine Schwierigkeit begegnet. Sie behaupten (S. 17) es könne auch die Funktion das unbestimmte Element bilden. Dies habe ich früher geglaubt, jedoch jetzt scheint mir diese Ansicht zweifelhaft, wegen des folgenden Widerspruchs: Sei w das Prädicat, ein Prädicat zu sein welches von sich selbst nicht prädicirt werden kann. Kann man w von sich selbst prädiciren? Aus jeder Antwort folgt das Gegentheil. Deshalb muss man schließen dass w kein Prädicat ist. Ebenso giebt es keine Klasse (als Ganzes) derjenigen Klassen die als Ganze sich selber nicht angehören. Daraus schliesse ich dass unter gewissen Umständen eine definierbare Menge kein Ganzes bildet .

Frege received the letter just at the time when he completed work on the second volume of The Fundamental Laws of Arithmetic (German: Grundgesetze der Arithmetik). Frege did not have time to correct his set theory. He only added an appendix to the second volume with an exposition and his analysis of the paradox, which began with the famous remark:

It is unlikely that anything worse can happen to a scientist than if the ground is pulled out from under his feet at the very moment when he completes his work. It was in this position that I found myself when I received a letter from Bertrand Russell, when my work was already completed.

Original text (German)
Einem wissenschaftlichen Schriftsteller kann kaum etwas Unerwünschteres begegnen, als daß ihm nach Vollendung einer Arbeit eine der Grundlagen seines Baues erschüttert wird. In diese Lage wurde ich durch einen Brief des Herrn Bertrand Russell versetzt, als der Druck dieses Bandes sich seinem Ende näherte .

z ∈ ( x: P (x) ) ⟺ P (z) (\displaystyle z\in \(x\colon P(x)\)\iff P(z)),

which said that it is possible to construct a set of elements that satisfy the property P (x) , (\displaystyle P(x),) he suggested using the following axiom:

z ∈ ( x: P (x) ) ⟺ P (z) & z ≠ ( x: P (x) ) (\displaystyle z\in \(x\colon P(x)\)\iff P(z)\ \&\ z\neq \(x\colon P(x)\)),

thus eliminating the possibility for a set to be a member of itself. However, a small [ which?] modification of Russell's paradox proves that this axiom also leads to a contradiction.

Russell published his paradox in his book " Principles of Mathematics" in 1903 .

Below are some of the possible approaches to constructing a system of axioms free from Russell's paradoxes.

Russell's type theory

Russell himself was the first to propose a theory free of Russell's paradox. He developed a theory of types, the first version of which appeared in Russell and Whitehead's book Principles of Mathematics" in 1903 . This theory is based on the following idea: simple objects in this theory have type 0, sets of simple objects have type 1, sets of sets of simple objects have type 2, and so on. Thus, no set can have itself as an element. Neither the set of all sets nor the Russell set can be defined in this theory. A similar hierarchy is introduced for statements and properties. Propositions about simple objects belong to type 1, propositions about the properties of propositions of type 1 belong to type 2, and so on. In general, a function, by definition, is of a higher type than the variables on which it depends. This approach allows you to get rid of not only the Russell paradox, but also many other paradoxes, including the liar paradox (), the Grelling-Nelson paradox, the Burali-Forti paradox. Russell and Whitehead showed how to reduce all mathematics to the axioms of type theory in their three-volume Principia Mathematica, published in 1910-1913.

However, this approach met with difficulties. In particular, problems arise in defining such concepts as the best upper bound for sets of real numbers. By definition, a least upper bound is the smallest of all upper bounds. Therefore, when determining the least upper bound, the set of real numbers is used. Hence, the least upper bound is an object of a higher type than the real numbers. This means that it is not itself a real number. To avoid this, it was necessary to introduce the so-called reducibility axiom. Because of its arbitrariness, many mathematicians refused to accept the reducibility axiom, and Russell himself called it a defect in his theory. In addition, the theory turned out to be very complex. As a result, it has not received wide application.

Zermelo-Fraenkel set theory

The best-known approach to the axiomatization of mathematics is the Zermelo-Fraenkel (ZF) set theory, which originated as an extension of Zermelo's theories(1908). Unlike Russell, Zermelo retained the logical principles and changed only the axioms of set theory. The idea of this approach is that it is allowed to use only sets built from already built sets using a certain set of axioms. For example, one of Zermelo's axioms says that it is possible to construct a set of all subsets of a given set (the Boolean axiom). Another axiom ( selection scheme) says that from each set it is possible to select a subset of elements that have a given property. This is the main difference between Zermelo set theory and naive set theory: in naive set theory, you can consider the set of all elements that have a given property, and in Zermelo set theory, you can only select a subset from an already constructed set. In Zermelo set theory, it is impossible to construct a set of all sets. Thus, the Russell set cannot be constructed there either.

Classes

Sometimes in mathematics it is useful to consider all sets as a whole, for example, to consider the totality of all groups. To do this, set theory can be extended by the notion of class , as, for example, in the Neumann- Bernays- Gödel (NBG) system. In this theory, the collection of all sets is class. However, this class is not a set and is not a member of any class, thus avoiding Russell's paradox.

A stronger system that allows one to take quantifiers over classes, and not just over sets, is, for example, Morse set theory - Kelly(MK) . In this theory, the main concept is the concept class, but not sets. Sets in this theory are considered to be such classes that are themselves elements of some classes. In this theory, the formula z ∈ ( x: P (x) ) (\displaystyle z\in \(x\colon P(x)\)) is considered equivalent to the formula

P (z) & ∃ y . z ∈ y (\displaystyle P(z)\ \&\ \exists y.z\in y).

As ∃ y . z ∈ y (\displaystyle \exists y.z\in y) in this theory means that the class z (\displaystyle z) is an many, this formula should be understood as ( x: P (x) ) (\displaystyle \(x\colon P(x)\)) is the class of all sets(not classes) z (\displaystyle z), such that P (z) (\displaystyle P(z)). Russell's paradox in this theory is resolved by the fact that not every class is a set.

One can go further and consider collections of classes - conglomerates, collections of conglomerates, and so on.

Impact on mathematics

Axiomatization of mathematics

Russell's paradox, along with other mathematical antinomies discovered at the beginning of the 20th century, stimulated a revision of the foundations of mathematics, which resulted in the construction of axiomatic theories to justify mathematics, some of which are mentioned above.

In all the new axiomatic theories constructed, the paradoxes known by the middle of the 20th century (including Russell's paradox) were eliminated. However, to prove that new similar paradoxes cannot be discovered in the future (this is the problem of the consistency of the constructed axiomatic theories), it turned out, in the modern understanding of this problem, is impossible (see Gödel's theorems on incompleteness).

intuitionism

In parallel, a new trend in mathematics arose, called intuitionism, the founder of which is L. E. Ya. Brouwer. Intuitionism arose independently of Russell's paradox and other antinomies. However, the discovery of antinomies in set theory increased intuitionists' distrust of logical principles and hastened the formation of intuitionism. The main thesis of intuitionism says that in order to prove the existence of some object, it is necessary to present a method for its construction. Intuitionists reject such abstract concepts as the set of all sets. Intuitionism denies the law of the excluded middle, however, it should be noted that the law of the excluded middle is not needed to derive a contradiction from Russell's antinomy or any other (in any antinomy it is proved that A (\displaystyle A) entails negation A (\displaystyle A) and denial A (\displaystyle A) entails A , (\displaystyle A,) however, from (A ⇒ ¬ A) & (¬ A ⇒ A) (\displaystyle (A\Rightarrow \neg A)\&(\neg A\Rightarrow A)) even in intuitionistic logic a contradiction follows). It is also worth noting that in later axiomatizations of intuitionistic mathematics, paradoxes similar to Russell's were found, such as, for example, Girard's paradox in the original wording Martin Loef.

Diagonal argument (self-applicability)

Despite the fact that Russell's reasoning leads to a paradox, the main idea of \u200b\u200bthis reasoning is often used in the proof of mathematical theorems. As mentioned above, Russell got his paradox by analyzing Cantor's proof of the non-existence of the largest cardinal number. This fact contradicts the existence of a set of all sets, since its cardinality must be maximum. However, according to the Cantor theorem, the set of all subsets of a given set has a greater cardinality than the set itself. The proof of this fact is based on the following diagonal argument?!:

Let there be a one-to-one correspondence , which to each element x (\displaystyle x) sets X (\displaystyle X) matches a subset s x (\displaystyle s_(x)) sets x. (\displaystyle X.) Let be d (\displaystyle d) will be a set of elements x (\displaystyle x) such that x ∈ s x (\displaystyle x\in s_(x)) (diagonal set). Then the complement of this set s = d ¯ (\displaystyle s=(\overline (d))) can't be one of s x . (\displaystyle s_(x).) Therefore, the correspondence was not one-to-one.

Cantor used the diagonal argument to prove the uncountability of real numbers in 1891. (This is not his first proof of the uncountability of real numbers, but the simplest).

Related paradoxes

Self-applicability is used in many paradoxes other than those discussed above:

The omnipotence paradox is a medieval question: "Can an almighty god create a stone that he himself cannot lift?"
The paradox Burali-Forti (1897) is an analogue of the paradox Cantor for ordinal numbers.
Mirimanov's paradox (1917) is a generalization of the Burali-Forti paradox for the class of all well-founded classes.
Richard's paradox (1905) is a semantic paradox showing the importance of separating the language of mathematics and metamathematics.
Berry's paradox (1906) is a simplified version of Richard's paradox published by Russell.
Kleene-Rosser paradox(1935) - formulation of Richard's paradox in terms of the λ-calculus.
Curry's (1941) paradox is a simplification of the Kleene-Rosser paradox.
Girard's paradox(1972) - formulation of the Burali-Forti paradox in terms of intuitionistic type theory .
is a semi-joking paradox reminiscent of Berry's paradox.

Notes

Godhard Link (2004) One hundred years of Russell's paradox, with. 350, ISBN 9783110174380 , .
Russell's antinomy // Dictionary of Logic. Ivin A. A., Nikiforov A. L.- M.: Tumanit, VLADOS, 1997. - 384 p. - ISBN 5-691-00099-3.
Andrew David Irvine, Harry Deutsch. Russell "s Paradox // The Stanford Encyclopedia of Philosophy / Edward N. Zalta. - 2014-01-01.
Antinomy- article from the Mathematical Encyclopedia. A. G. Dragalin
A. S. Gerasimov. Course mathematical logic and theory computability. - Third edition, revised and enlarged. - St. Petersburg: LEMA, 2011. - S. 124-126. - 284 p.

In the most general paradox form Bertrand Russell looks like that:

Let M be the set of all sets that do not contain themselves as their element. Question: Does M contain itself as an element?

If the answer is "yes", then, by the definition of M, it must not be an element of M, and we have a contradiction.

If the answer is "no" - then, by the definition of M, it must be an element of M - again a contradiction ...

“What is the essence of the contradiction? A class is sometimes and sometimes is not a member of itself. " Class teaspoons, for example, is not another teaspoon, but classes of things that are not teaspoons are some of the things that are not teaspoons."

Russell's paradox is related to the use of the notion of a class of all proper classes. "Own" is a class that does not contain itself as its member. "Improper" is a class that is supposed to contain itself as its member. It is assumed that this is the class of all classes. With regard to the class of all proper classes (the "Russell class"), the question is raised: what is it - proper or improper? If we assume that it is own, then it should be assigned to non-own classes, and vice versa.

In a semi-joking way, Russell presents this paradox through the so-called "Barber" paradox in An Introduction to the Philosophy of Mathematics (1919). The village barber must shave all those and only those inhabitants of his village who do not shave themselves. Should he shave himself? If he shaves himself, then he shaves himself and has no right to shave himself. But if he does not shave himself, he has the right to shave himself. In this way, one can also demonstrate the paradoxicality of "the set of all sets that are not proper elements." It should be noted that the “Barber” is not a “pure paradox”, because it only follows from it that such a hairdresser cannot exist at all, i.e. “in principle, no unambiguous and consistent definiteness can be found for this set containing elements defined only in terms of this totality, as well as elements that include or imply this totality. The paradox is eliminated by the conclusion that if some premises give rise to a contradiction, then they are wrong.

Russell's antinomy played an important role in the development of the foundations of mathematics. It undermined the foundations of set theory, the very new logic, became a real disaster and the collapse of the hopes of those who dealt with the problems of substantiating mathematics and logic at the turn of the 19th-20th centuries.

Russell in 1903 did not openly admit that he had discovered the solution to the paradox. In the "Preface" to "Principles of Mathematics", he noted that the only justification for publishing a work that had a number of unresolved questions was that this study made it possible to penetrate deeper into the nature of classes. Russell proposed a simple type theory as a possible solution in "Appendix B" to this paper. In the future, he comes to the conclusion that it is this theory, developed into a system, that makes it possible to eliminate the paradox.

Kolesnikov A.S., Philosophy of Bertrand Russell, L., Leningrad University Press, 1991, p. 84-85.

Portal for the student. Self-training