The barber shaves. Bertrand Russell's Paradox

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 ..

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.

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 related specifically to 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 refer 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..

All sets that do not contain themselves as their element. Does it contain itself as an element? If so, then, by definition, it shouldn't be an element - a contradiction. If not - then, by definition, it must be an element - again a contradiction.

The contradiction in Russell's paradox arises from the use in reasoning of the internally contradictory concept sets of all sets and ideas about the possibility of unlimited application of the laws of classical logic when working with sets. Several ways have been proposed to overcome this paradox. The most famous is the presentation of a consistent formalization for set theory, in relation to which all “really necessary” (in a sense) ways of operating with sets would be acceptable. Within the framework of such a formalization, the statement about the existence sets of all sets would be irreducible.

Indeed, suppose that the set of all sets exists. Then, according to the selection axiom, there must also exist a set whose elements are those and only those sets that do not contain themselves as an element. However, the assumption of the existence of a set leads to Russell's paradox. Therefore, in view of the consistency of the theory , the statement about the existence of a set is not derivable in this theory, which was required to be proved.

In the course of the implementation of the described program of "saving" the theory of sets, several possible axiomatizations of it were proposed (Zermelo-Fraenkel theory ZF, Neumann-Bernays-Gödel NBG theory, etc.), however, no proof has been found for any of these theories so far consistency. Moreover, as Gödel showed by developing a number of incompleteness theorems, such a proof cannot exist (in a sense).

Another reaction to the discovery Russell's paradox the intuitionism of L. E. Ya. Brouwer appeared.

Wording options

There are many popular formulations of this paradox. One of them is traditionally called the barber's paradox and goes like this:

One village barber was ordered "shave anyone who does not shave himself, and do not shave anyone who shaves himself". How should he deal with himself?

Another option:

One country issued a decree: "The mayors of all cities should not live in their own city, but in a special city of mayors". Where should the Mayor of the City of Mayors live?

And one more:

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?

see also

Literature

• Courant R, Robbins G. What is mathematics? - Ch. II, § 4.5
• 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.
• Katrechko S. L. Russell's paradox of the barber and the dialectic of Plato - Aristotle // Modern logic: problems of theory, history and applications in science. - St. Petersburg, 2002. - S. 239-242.
• Martin Gardner Well guess what! = Ah! gotcha. Paradoxes to puzzle and delight. - M .: Mir, 1984. - S. 22-23. - 213 p.

Notes

Wikimedia Foundation. 2010 .

See what the "Russell Paradox" is in other dictionaries:

- (Greek paradoxos unexpected, strange) in a broad sense: a statement that is sharply at odds with the generally accepted, established opinion, the denial of what seems to be “undoubtedly correct”; in a narrower sense, two opposite statements, for ... ... Philosophical Encyclopedia

Russell's paradox, a set-theoretic antinomy discovered in 1903 by Bertrand Russell and later independently rediscovered by E. Zermelo, demonstrating the imperfection of the language of G. Cantor's naive set theory, and not its inconsistency. Antinomy ... ... Wikipedia

paradox- PARADOX (from Greek para outside and doxa opinion). 1) In a broad (non-logical) sense, everything that in one way or another conflicts (diverges) from the generally accepted opinion, confirmed by tradition, law, rule, norm or common sense. ... ... Encyclopedia of Epistemology and Philosophy of Science

The position, which at first is not yet obvious, however, contrary to expectations, expresses the truth. In ancient logic, a paradox was a statement whose ambiguity refers primarily to its correctness or incorrectness. AT… … Philosophical Encyclopedia

- (the paradox of the class of all well-founded classes) a paradox in set theory, which is a generalization of the paradox of Burali Forti. Named after the Russian mathematician D. Mirimanov. Contents 1 Wording ... Wikipedia

Demonstrates that the assumption of the existence of a set of all ordinal numbers leads to contradictions and, therefore, the theory of sets, in which the construction of such a set is possible, is contradictory. Contents 1 Wording 2 History ... Wikipedia

- (from the Greek paradoxes unexpected, strange) unexpected, unusual (at least in form) judgment (statement, sentence), sharply at odds with the generally accepted, traditional opinion on this issue. In this sense, the epithet "paradoxical" ... Great Soviet Encyclopedia

Cantor's paradox is a paradox of set theory, which demonstrates that the assumption of the existence of a set of all sets leads to contradictions and, therefore, a theory is inconsistent in which the construction of such a set ... ... Wikipedia

This term has other meanings, see Paradox (meanings). Robert Boyle. Scheme of proof that a perpetual motion machine does not exist Paradox ... Wikipedia

Books

• The collapse of the metaphysical concept of the universality of the subject area in logic. Frege-Schroeder controversy, B. V. Biryukov. This book discusses the dramatic history of mathematical logic associated with the concept of "reasoning universe" - the subject area in logic. The conflict of views between two...

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 uncountability 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

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

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 related specifically to 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, 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 notice that the question asked, "Who shaves the barber?", was incorrect from the very beginning, just like the classic question: "Why do you hit 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 refer 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, including all other directories that do 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.

The owner of a barbershop in one village posted the following notice: "I shave those and only those residents of the village who do not shave themselves." The question is, who shaves the barber?

Development mathematical logic especially intensified in the 20th century in connection with the development of computer technology and programming.

Ø Definition Mathematical logic is a modern form of logic that relies entirely on formal mathematical methods. It studies only inferences with strictly defined objects and judgments for which it is possible to decide unambiguously whether they are true or false.

The basic (undefined) concept of mathematical logic is the concept of " simple statement". A statement, which is a single statement, is usually called simple or elementary.

Ø Definition Statement is a declarative sentence that can be said to be true or false.

Statements can be true I or false L.

Example: Planet Earth solar system. (True); Every parallelogram is a square (False)

There are statements about which it is impossible to say with certainty whether they are true or false. "Today the weather is good" (anyone like it)

Example statement "It's raining"- simple, and true or false depends on what the weather is now outside the window. If it really is raining, then the statement is true, and if it is sunny and it is useless to wait for rain, then the statement is "It's raining" will be false.

Example“ ” is not a statement (it is not known what values ​​it takes).

“Sophomore student” is not a saying

Ø DefinitionElementary utterances cannot be expressed in terms of other utterances.

Ø DefinitionComposite propositions are propositions that can be expressed using elementary propositions.

Example“The number 22 is even” is an elementary statement.

There are two main approaches to establishing the truth of statements: empirical (experimental) and logical.

At empirical approach the truth of the statement is established with the help of observations, measurements, experiments.

logical approach lies in the fact that the truth of a statement is established on the basis of the truth of other statements, that is, without referring to the facts, to their content, that is, formally. This approach is based on the identification and use of logical connections between the statements included in the argument.

2.2 Propositional logic

First of all, you need to define the concepts, because the same section is often called differently: mathematical logic, propositional (sentence) logic, symbolic logic, two-valued logic, propositional logic, Boolean algebra ...

Ø Definitionpropositional logic- a branch of logic in which the question of the truth or falsity of statements is considered and decided on the basis of studying the method of constructing statements from e elementary(further not decomposed and not analyzed) statements with the help of logical operations of conjunction ("and"), disjunction ("or"), negation ("not"), implication ("if...then..."), etc. .

Ø Definition Propositional Calculus is an axiomatic logical system, the interpretation of which is the algebra of propositions.

Of greatest interest is the construction of a formal system, which, among all possible statements, distinguishes those that are logical laws (correctly constructed reasoning, logical conclusions, tautologies, generally valid statements).

Formal theories, not using natural (colloquial) language, need their own formal language in which the expressions encountered in it are written.

Ø Definition The formal system that generates statements that are tautologies and only them is called propositional calculus(IV).

The formal IoT system is defined by:

What symbols are best used to denote logical connectives?

Let us dwell on the following notations: negation, conjunction, disjunction, implication, and equivalence. Usually, the logical values ​​of the results of applying connectives are written in the form of tables (the so-called truth tables).

2.3 Logical connectives............................................................... ...

In natural language, the following grammatical means play the role of connectives in compiling complex sentences from simple ones:

unions "and", "or", "not";

the words "if ..., then", "either ... or",

“if and only if”, etc.

In propositional logic, the logical connectives used to compose complex propositions must be defined precisely.

Let us consider logical connectives (operations) on statements, in which the truth values ​​of compound statements are determined only by the truth values ​​of the constituent statements, and not by their meaning.

There are five widely used logical connectives.

negation (represented by a sign),

conjunction (sign),

disjunction (sign v),

implication (sign)

equivalence (sign).

Ø DefinitionNegation statements P is a statement that is true if and only if the statement P is false.

Ø DefinitionConjunction two propositions P and Q - a proposition that is true if and only if both propositions are true.

Ø DefinitionDisjunction two propositions P and Q - a proposition that is false if and only if both propositions are false.

Ø Definitionimplication two statements P and Q - a statement that is false if and only if P is true and Q is false. The statement P is called parcel implications, and the statement Q - conclusion implications.

Ø DefinitionEquivalence two propositions P and Q - a proposition that is true if and only if the truth values ​​of P and Q are the same.

The use of the words "if ..." "then ..." in the algebra of logic differs from their use in everyday speech, where, as a rule, we believe that if the statement X is false, then the statement "If X, then at' doesn't make sense at all. In addition, constructing a sentence of the form "if X, then at» in everyday speech, we always mean that the sentence at stems from the proposal X. The use of the words "if, then" in mathematical logic does not require this, since the meaning of propositions is not considered in it.

2.4Logical operations

The basis of digital technology are three logical operations that underlie all computer outputs. These are three logical operations: AND, OR, NOT, which are called “three pillars of machine logic”.

Logical connectives or logical operations known from the course of discrete mathematics can be applied to statements. This results in formulas. Formulas become propositions by substituting all the meanings of the letters.

Truth tables of basic logical operations.

Several variables linked together by logical operations are called a logical function.

The description of any calculus includes a description of the symbols of this calculus (alphabet), formulas, which are the final configurations of symbols, and the definition of derivable formulas.

2.5 Propositional calculus alphabet

The utterance calculus alphabet consists of symbols of three categories:

The first of them is the sign of disjunction or logical addition, the second is the sign of conjunction or logical multiplication, the third is the sign of implication or logical consequence, and the fourth is the sign of negation.

The propositional calculus has no other symbols.

2.6 Formulas. Tautology

Propositional calculus formulas are sequences of symbols from the propositional calculus alphabet.

Capital letters of the Latin alphabet are used to designate formulas. These letters are not calculus symbols. They are only symbols of formulas.

Ø Definition Formula– well-formed compound statement:

1) Every letter is formula.

2) If , are formulas, then , , , , are also formulas.

Obviously, the words are not formulas: ) (the third of these words does not contain a closed bracket, and the fourth does not contain brackets).

Note that the concept of logical connectives is not concretized here. Usually, some simplifications are introduced into the formulas. For example, brackets are omitted in the notation of formulas according to the same rules as in propositional algebra.

Ø Definition. The formula is called tautology, if it takes only true values ​​for any values ​​of letters.

Ø Definition A formula that is false for any value of the letters is called contradiction

Ø Definition The formula is called doable, if on some set of distribution of truth values ​​of variables it takes the value AND.

Ø Definition The formula is called rebuttable, if for some distribution of the truth values ​​of the variables it takes the value L.

Example are formulas according to clause 2 of the definition.

For the same reason, the words will be formulas:

Simultaneously with the concept of a formula, the concept subformulas or part of a formula.

1. subformula the elementary formula is itself.

2. If the formula has the form , then its subformulas are: itself, formula A and all subformulas of formula A.

3. If the formula has the form (A * B) (hereinafter, under the symbol * we will understand any of the three symbols), then its sub-formulas are: itself, formulas A and B and all sub-formulas of formulas A and B.

Example For formula its subformulas will be:

- subformula of zero depth,

Subformulas of the first depth,

Subformulas of the second depth,

Subformulas of the third depth,

Subformula of the fourth depth.

Thus, as we “dive deep into the structure of the formula”, we single out subformulas of increasing depth

From the course of discrete mathematics, the main logical equivalences (equivalences) are known, which are examples of tautologies. All logical laws must be tautologies.

Sometimes laws are called withdrawal rules, which determine the correct conclusion from the premises.

2.7Laws of propositional logic

The algebra of logic has commutative and associative laws with respect to the operations of conjunction and disjunction and a distributive law of conjunction with respect to disjunction, the same laws take place in the algebra of numbers.

Therefore, over the formulas of the algebra of logic, you can perform the same transformations that are carried out in the algebra of numbers (opening brackets, bracketing, bracketing the common factor).

Consider the basic laws of propositional logic.

1. Commutativity:

, .

2. Associativity:

3. Distributivity:

4. Idempotency: , .

5. Law of double negation: .

6. The law of the exclusion of the third:.

7. Law of contradiction: .

8. Laws of de Morgan:

9. Laws of idempotency(properties of operations with logical constants)

There are no exponents and coefficients in the algebra of logic. The conjunction of identical "factors" is equivalent to one of them

Here , and are any letters.

Examples. tautology formula.