Bertrand Russell's paradox. solving problems of logical paradoxes. Bearded barber - solution to B. Russell's paradox The barber shaved everyone who did not shave himself

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 (the Zermelo-Fraenkel theory ZF, the Neumann-Bernays-Gödel theory NBG, etc.), but 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?

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 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. AT this book the dramatic history of mathematical logic, connected with the concept of the "universe of reasoning" - the subject area in logic, is considered. The conflict of views between two...

The barber shaves those and only those who do not shave themselves,
Will the barber shave himself?

Answer: The barber will perform the act of shaving until
until he realizes what he is doing. for example
cut at least one hair. Those. something happened
the result, evaluating which, the barber will be able to make
logical deduction whether he shaves or not. After which he
stop shaving the flag and when it reaches it
the fact that in this moment he doesn't shave, he repeats
their actions. as a result, the shaving speed will be
depend on the speed with which the barber himself
works as an analytical system. And in the end, the decision
the paradox will be in time, i.e. shave not shave
shaved not shaved, etc. i.e. cycle, but
our-generator.

So the Barber will shave as a result?

Depends on the truth criterion for the term shave (in
task, it is not specified, as a result of which the task is not
set correctly).

so I took the liberty of installing it, so that the task
had a decision and introduce the definition of "shaves"
the fact of shaving is the cutting of one hair at a time
time t1-t2.

copy-pasted from another forum:

"Let's put all the dots on Yo!"
Well, the fact of the truth of shaving is certainly cool! And who is actually going to install it?

The barber himself, of course!
After all, he determines for himself whether he fulfills the condition of the task at a given time or not.
If he is not shaving at the moment, then he can calmly start shaving. At this moment, he is not a barber for himself.
The condition does not say that it is forbidden to start shaving or to be shaved.
He must not have the fact that he himself is aware of the process of shaving, otherwise he will violate the condition.
Those. if he cannot realize it, then he does NOT violate the condition of the problem!
And in his frame of reference, according to the law of the excluded middle, this cannot happen.

Because he simply does not have time to realize the action of cutting the hair at the time t1-t2.

It turns out that the action happened, and the barber is not to blame. Yes, he is aware that he has completed the act of shaving, but at the moment when he had not yet performed it, he had every right to begin the shaving procedure according to the condition! He was not a barber in his ISO. And when he shaved off, his conscience is clear again, because he does not shave himself again. And the very fact of the action of shaving in his ISO is not defined at all.
From the point of view of any villager, the barber also did not violate the conditions, because everything that he did in such a short time interval is not determined from their ISO, and even more so. They both see only the result: he was not shaved, and now he is shaved.

If we take a “fast barber” who is able to determine the fact of his shaving at the moment of cutting off half of the hair, then he will simply stop so as not to violate the condition, and immediately continue shaving, since he will again cease to be a barber.

In any case, the barber will be shaved and the realization that he did violate the condition will not come to him, despite the fact.

It doesn’t occur to you that the body moves in a straight line and uniformly accelerated in a vacuum for a reason after the fact? You take it for granted, don't you? oops! The body has moved, energy has not been spent, but who moved it? Who spent the energy?
Likewise, the barber will be confronted with a fact. Oops! Pabrilsi! How did it happen? This is, of course, if his memory has been knocked out and he does not remember what he did a moment ago.

And in the case of Newton's 1st law, you just don't do it, that's all.

And only due to the fact that the barber remembers what he did a moment ago, and also that he was not shaved, he can make a deductive ASSUMPTION that he shaved himself and that he violated the condition.
The fact of shaving could not be established, but it definitely was.
We apply the law of logic of inversion of causality:
a deductive conclusion turns into an inductive one in the case of proof that there cannot be another deductive conclusion, but there cannot be, there was no one nearby, therefore the barber himself shaved, and not a miracle shaved him, and the fact of violation has already been established inductively.
(I’ll ask you to feel this moment, because I showed you here how the law of inversion of causality works for the concept of induction and deduction, where else can I show)

But this again does not violate the conditions of the problem, since the problem does not say anything about whether the barber should suffer from this after the fact. There was a question to shave or not to shave.

Even if the barber concludes that he violates the condition after the fact of shaving one hair, and that trying to shave again will lead him to the next violation of the condition of the problem, this again does not change anything, since the problem was not instructed to take into account negative feedbacks in time, i.e. by default, we neglect them by convention.

"Observer? This is another ISO."

After all, the task is set for the barber, and not for some kind of outside observer, who can measure the procedure for shaving one hair by quantizing this action in even more detail than the barber into components in another ISO (slow motion), realize the process of shaving off half of the hair and say that the barber violates the condition. Well, yes, from his position, the barber will break it, but this does not contradict the condition of the problem.

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 section 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 role of connectives in composing complex sentences of the simple ones, the following grammatical means play:

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 “diving deep into the structure of the formula”, we single out the subformulas all greater 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, it is possible to 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 idempotence(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.

Not her inconsistency.

Russell's antinomy is formulated as follows:

Let K is the set of all sets that do not contain themselves as their element. Does it contain K itself as an element? If yes, then by definition K, it must not be an element K- a contradiction. If not, then by definition K, it must be an element K- again a contradiction.

The contradiction in Russell's antinomy arises from the use of the 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 antinomy. 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 U of all sets exists. Then, according to the selection axiom, there must also exist a set K, 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 K leads to Russell's antinomy. Therefore, in view of the consistency of the theory , the statement about the existence of a set U is not deducible in this theory, which was 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 (the Zermelo-Fraenkel theory ZF, the Neumann-Bernays-Gödel theory NBG, etc.), however, for none of these theories, so far no proof of inconsistency. 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.

They mistakenly believe that this paradox demonstrates the inconsistency of G. Cantor's set theory. To refute these views, N. Vavilov cites the following paradox - the "Piglet Paradox":

Let n is an integer that is both greater than and less than zero. Then n is positive if and only if it is negative.

It is obvious that only the non-existence of the number assumed by us follows from it n, and not the inconsistency of number theory in general - the same method is used in proofs by contradiction.

The structure of this paradox is identical to the structure of Russell's paradox, which allows us to draw conclusions only about the inconsistency of the concept of "set of all sets", but not the theory of sets as a whole.

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:

Literature

R. Courant, G. Robbins. 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. pp.512-514.
Katrechko S.L. Russell's paradox of the barber and Plato-Aristotle's dialectics //Modern logic: problems of theory, history and application in science. SPb., 2002. pp.239-242.

Notes

Wikimedia Foundation. 2010 .

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

Russell's paradox, discovered in 1901 by Bertrand Russell and later independently rediscovered by E. Zermelo, is a theoretical set paradox that demonstrates the inconsistency of Frege's logical system, which was an early attempt at formalization ... ... Wikipedia

Mathematics is usually defined by listing the names of some of its traditional branches. First of all, this is arithmetic, which deals with the study of numbers, the relationships between them and the rules for working with numbers. The facts of arithmetic admit various ... ... Collier Encyclopedia

Ouroboros "The serpent that devours itself." Self-reference (self-reference) is a phenomenon that occurs in systems of propositions in those cases when a certain concept refers to itself. In other words, if any ... Wikipedia

- ... Wikipedia

A service list of articles created to coordinate work on the development of the topic. This warning is not installed on informational articles, lists and glossaries ... Wikipedia

The barber, having received the order, was at first delighted, because many soldiers knew how to shave themselves, shaved those who did not know how to shave themselves, and then sat on a stump and thought: what should he do with himself? After all, if he shaves himself, he will violate the order of the commander not to shave those who shave themselves. The barber had already decided that he would not shave himself. But then the thought dawned on him that if he doesn’t shave himself, it will turn out that he doesn’t shave himself, and by order of the commander he must still shave himself ...

What happened to him, history is silent.

And what about set theory? And here's what: the commander tried to determine the set of people whom the barber needs to shave, in this way:

those and only those who do not shave themselves.

It would seem that an ordinary set is described in several Russian words, why is it worse, for example, sets

all the students in the school?

But with this set, a problem immediately arises: it is not clear whether barbers belong to this set.

Here is another version of this paradox.

Let's call the adjective of the Russian language reflective if it has a property that defines. For example, the adjective "Russian" is reflexive, and the adjective "English" is non-reflexive, the adjective "three-syllable" is reflexive (this word consists of three syllables), and the adjective "four-syllable" is non-reflexive (consists of five syllables). It seems that nothing prevents us from defining the set

all reflexive adjectives.

But let's consider the adjective "non-reflexive". Is it reflective or not?

It can be stated that the adjective "non-reflexive" is neither reflexive nor non-reflexive. But how then to be with such a spell:

Is either the assertion true or the negation true?

(This incantation is called the law of the excluded middle, and the method of contradiction is based on it, in fact.)

Finally, the third version of the paradox. Consider the set

Sets such that

We include in the set only those sets that belong to themselves. There are sets that contain other sets. For example, let

a set contains numbers, and a set has two elements: a set and a number. Returning to the boxes, it can be said like this: some boxes can be put in other boxes. (It turns out that each such sequence of nested boxes always has a finite number of elements - there are deep reasons for this.)

The considered set is a kind of "barber". If we assume that , we immediately conclude that . If we assume that - we get that .

Faced with these paradoxes, set theorists realized that you can not specify sets with arbitrary phrases. After that, they began to deal with paradoxes in two ways.

The first way is the way of Cantor, who came up with the "naive set theory", in which all actions and operations leading to paradoxes are prohibited. The idea is this: it is allowed to work with sets that "occur in nature", it is also allowed to work with sets that are obtained from them by reasonable set-theoretic operations. Let, for example,

Many school students
= set of continuous functions

(these sets "are found in nature"), from them you can get union, intersection. One can even multiply set by set: by definition

A set of pairs in which the first element is from the first set and the second is from the second. In our case, this is a set of pairs in which the first element is a student of the school, and the second is some kind of continuous function.

Another way is axiomatic. This way of overcoming paradoxes was developed by Zermelo and Frenkel (Zermelo–Frenkel axiom system), Gödel and Bernays (Godel–Bernays axiom system). According to this theory, a set is something that satisfies axioms such as the following.

Axiom records are duplicated in the "language of quantifiers". Here are the meanings of the quantifiers used:
- for anyone ;
- exists ;
- there is only one ;
- is a set;
- the set of those and only those that satisfy the condition ;
- logical "or";
- logical "and".

1. Axiom of volume. A set is defined by its elements: sets consisting of the same elements are equal.

2. Unification Axiom. The union of all elements of a set is a set.

3. Axiom of selection. For every set and every condition there is a set

A subset of elements of the set that satisfy the condition .

In other words, we cannot take the set of all flying crocodiles from all over the world or the set of those sets that do not contain themselves, but we can, taking a certain set, select a "piece" in it - a set of its elements that satisfy some condition.

4. Axiom of degree. The set of all subsets of a given set is a set.

5. Substitution axiom. Let be a set and let be an arbitrary formula. Then if for each there exists and is unique such that is true, then there is a set of all for which there exists such that is true.

6. Funding axiom. There is no infinite sequence of nested sets: each chain of sets

7. Axiom of infinity. There are infinite sets, i.e. such sets that are equivalent in size to .

8. Axiom of choice. Another very complex, but also very obvious axiom - about it later.

For more on the axiomatics of set theory, see the book.