Is math logical or why are axiomatic theories paradoxical?

Today we will talk about the basics. Theoretical foundations set the limits of the possible and show ways to achieve goals, and therefore the depth of understanding in such matters will never be superfluous.

We will not be able to illuminate all the basics, so for the time being we will direct our enlightenment beam on entertaining tasks called paradoxes. As the topic is covered, we gradually dive into the depths of the approach called logic, and then pay attention to the connection between logic and mathematics, after which our readers can easily understand not only the reasons for the utility of logic in the derivation of axiomatic theories, but why do we need axiomatic theories, as well as understand how not to approach the construction of consistent theories.

Let's start with a list of interesting tasks. These puzzles are called paradoxes, because no matter how we answer the question posed in the problem, the author of the paradox will always easily prove that we are wrong. That is, in other words - the tasks do not imply the existence of a solution, but rather in an interesting way show the non-triviality of logical reasoning.

The paradox of the barber

')
In a certain village, a certain barber declared that he shaves everyone in his village who does not shave himself. The question is - who shaves the barber?

If you answered that the barber shaves the barber himself, then the paradox supporters will quickly explain to you that the barber shaves those who do not shave themselves, which means he cannot shave himself, otherwise he would shave himself and thus shave one who shaves himself.

If you answered that the barber is shaved by someone else, then the supporters of the paradoxes will remind the task conditions again - they indicate that if a person does not shave himself, then he is obliged to shave exactly the barber, because he said that he shaves everyone who does not shave myself. So if someone else shaves him, then he does not shave himself and by the condition of being shaved by a barber.

While you shouldn’t dive deep into the logical contradictions of this task, it only introduces you to the world of paradoxes and several more controversial tasks will follow. Although if you have found an unexpected solution - do not rush, then you will see how the supporters of paradoxes will bypass any unexpected solutions.

Paradoxes of sets

Similarly, the paradox of the barber more than a hundred years ago, a paradox was discovered that seriously affected the foundations of mathematics, and so seriously that this period was called the crisis of the foundations of mathematics. True, there is no need to worry much about mathematics, because this crisis was not the first, and it had little effect on the substantive sections of mathematics. But nevertheless, the crisis clearly showed the weakness of our knowledge in that area, which has always been considered strict and almost comprehensive.

First we show the basis of one of the paradoxes in a simplified example. We represent the set (or a list, array) of all positive integers, and then we represent the number corresponding to the number of numbers in our set. Submitted? If so, what will happen to the set after adding to it a number equal to the number of its elements with the added unit? If all the elements are already there, remember that they can be sorted in ascending order and then it will become obvious that the largest element is equal to the number of elements in our set. But if we add one to the number, then we get an element that is not in the set, so it’s impossible to submit such a list, because every time a question about a new element will emerge. But on the other hand, we can formulate the phrase “the set of all positive integers”. So what can we really and what can not?

While you are thinking about the answer to the previous question, we will ask you the next one. And if we imagine the set of all sets, yes such that no set would include itself as an element? Is it possible? For example, the set of numbers {1, 2, 3} does not include itself as an element. So maybe all the other sets can also be presented?

If you say that this is possible, then the supporters of paradoxes will ask the question - does the presented set include itself?

If you say “yes”, then the supporters of paradoxes will answer that, according to the condition of the problem, the set should not include such sets that include themselves, but since you said “yes”, then you included the presented set by itself and thus prohibited its inclusion, because it became a set that includes itself, which contradicts the condition of the problem.

If you say "no", then the supporters of paradoxes will say that according to the conditions of the problem the set presented must include all the sets that do not include themselves, and therefore the set itself (which is not in itself) must also be in our set.

Just as you may now, the mathematicians of the whole world were slightly hurt by the apparent lack of common sense in the proposed paradox. After all, not only did common sense run away somewhere, but shortly before that, mathematicians managed to suggest using set theory (and we are just talking about its representative — the set of all sets that do not include themselves) to build all of mathematics on its basis. As a result, there was a crisis - the basis of mathematics, as it turned out, is not common sense. How do you like this math? Winnie the Pooh was well put on this topic - it is good, but for some reason it is lame (s).

But that is not all. Further, for completeness, we present a couple of paradoxes of a slightly different plan.

The paradox of self-applicability

There are words that can be applied to these words. For example - the word “trilogy” consists of three syllables and its meaning also tells us about three syllables, therefore such a word can be called self-applicable. Similarly, the word “Russian” is written in Russian and expresses the meaning of belonging to Russian, that is, again self-applicable. But the word "lilac" is usually written in a completely non-lilac color and does not grow on lilacs, which means it is not self-applicable. But there is another word (and we just saw it) "non-self-applicable." Does this word apply to itself?

If the struggle with common sense inside you has successfully ended and you said that the word is self-applicable, then the supporters of the paradoxes will say - how can it be self-applicable, if it says “non-self-applicable”?

If you say that the word is not self-applicable, the supporters of paradoxes will answer that the meaning of the word coincides with the definition you gave him (non-self-applicable), which means you yourself also showed a way of self-applicability, and then you are again wrong!

But the joy of supporters of paradoxes will be incomplete, if we do not show another problem.

The paradox of false saying

The problem is very simple - you must answer “yes” or “no” to the question whether the following statement is false - “this statement is false”.

If you answer "no", then the supporters of the paradoxes will say that what is written in the statement is false, which means you are saying something wrong.

If you answer “yes”, then the supporters of paradoxes will say that once you say that the statement is false (by answering “yes”), and the statement itself says that it is false, then where is the lie? So you answered wrong again! Further, the supporters of the paradoxes rejoice again.

Little demystification

We will not be disheartened by watching the fun in the camp of the supporters of paradoxes, but we will try to uncover the evil that, so to speak, strongly powdered our brains in all these paradoxes. Why, we - a bunch of mathematicians are still not sure about the consistency of the foundations of their science!

First, about the barber. Let's take a closer look at the composition of the paradox participants. We'll notice a couple of entities, this is the barber and some “all” that the barber shaves. We will also see a certain attitude that the barber enters into with those whom he shaves. Let's call this relationship simply “shave.” In the language of mathematics, we could write - x shaves y, that is, a certain X is in a relationship with a certain player, and the ratio is called shaves. Further, in the paradox, we see an algorithm for selecting the “all” essence. The essence of the algorithm is a check for the condition “do not shave itself”. We also see the obligation of the barber to shave all who enter into the mentioned essence “all”.

Now, having written down the “given” part for our task, we move on to the “solution” part.

Suppose that a certain commission selects people from the village, and everyone who answers “I don’t shave myself” is included in the set of the problem statement (the set “all”). After the completion of the work of the commission, we have a group of persons whom our barber must be properly processed. Then you can easily imagine that at the time of the survey the barber said that he shaves himself, and therefore he was not included in the group of people to be treated. As a result, we get a completely blissful picture - all those who do not shave themselves will be shaved calmly by our barber. And will not they be? At least, we will not see any obstacles on the part of common sense, and therefore we will easily present all shaved faces that are suitable for the condition and a very contented barber. But supporters of paradoxes in such a situation will be out of work, for a paradox, it turns out, is not at all!

But in fact, there is a paradox. It’s not for nothing that the mathematicians of the whole world are preoccupied with crisis!

To identify the cause of the paradox, it is necessary to include it in the equation of its supporters. They will say that the barber claimed that he shaves those who do not shave themselves, and therefore he has no right to shave himself, because then he will shave those who shave themselves and thus violate the condition of the problem. Then, in terms of logic, we can say that the statement “the barber shaves the barber” is false under the terms of the problem. But as a result, the barber must be included in the set of individuals who are subject to barber shaving. And the barber should shave them all, because otherwise supporters of paradoxes will immediately appear and remind us of the conditions of the problem.

For greater clarity, we reduce the description of the situation. We denote the barber by the letter B, the ratio “shave” should remain unchanged, it is already short. Many "all" can also not be reduced. Then in a brief record we get:

1) False (B shave B) means B belongs to "everything"
2) X shaves B and X = B

Such a record means that (the first line) from the fact that the barber does not shave the barber, the barber belongs to the “all” set. The second line tells us that a certain X should shave the barber, and this X should be the barber himself.

Now we will perform the minimal transformations with the second line - we will replace X in it with B, because by condition they are equal, and also we denote the truth of the resulting statement. We get:

true (B shaves B)

But from line (1) we have:

falsely (B shaves B)

And these two conditions (at the request of supporters of paradoxes) must be fulfilled simultaneously.

So what is evil here? As we saw, before the intervention of the paradox supporters, peace and order reigned in the village, all the officials were shaved and the barber was pleased. But after the intervention of the supporters of paradoxes, we received the demand at the same time of the truth and falsity of the assertion that the barber shaves the barber. To put it another way, we received conflicting demands. And of course, if the requirement is inconsistent, then it is impossible to solve the problem with such requirements. No matter how we wriggle out, no matter how we invent new and new ways of avoiding the paradox, for example, stating that the barber does not shave at all and wears a beard, or that the barber is a woman and does not need to shave, but supporters of paradoxes will consistently object - No, then everything should be exactly as we said. But as a result of the subordination of the severity of the statements of supporters of paradoxes, we get an insoluble task.

After pointing to the inconsistency of conditions, we can try to identify a number of factors that led to a situation where, in fact, stupid requirements (and how else to call the requirement to shave and not to shave at the same time?) Were taken very seriously by very many people.

First, it is worth pointing out the implicitness of conflicting requirements. A similar task, but with an obvious contradiction in the conditions, would be immediately rejected and no one would know any paradoxes, but it was the hidden nature of the contradictory nature of the restrictions that led to numerous attempts to solve the hopeless task. For example, the task of finding a number that is simultaneously greater than zero and less than zero would hardly have led to the emergence of the concept of paradox, because in such a task, the contradictory meaning of the requirements is obvious to everyone. But in the task about the barber, the non-obviousness of the inconsistency of the restrictions pulled significant consequences. Therefore, in any paradox, one should first look for implicit contradictions in the restrictions imposed on the solution of the problem.

Secondly, in addition to non-obviousness, there are actually contradictory limitations in such tasks (which are not visible at first glance). It is worth emphasizing here - it is the restrictions on the decision, and not something else. That is, the subject area to which the task belongs is somehow contradictory, and not the language in which the task is stated, but the contradictions are laid outside these concepts and precisely in the form of restrictions on a possible solution. Therefore, you should always carefully study the limitations on the solution, trying to identify possible contradictions in them.

Third, conflicting tasks necessarily include a reality-distorting formalism. The strict adherence to only the voiced conditions, precluding the finding of solutions outside the controversial area, is an obvious sign that should be carefully looked for in other tasks that at first glance do not look paradoxical.

As for the rest, in the task about the barber we see the peculiarities peculiar to it, which may not be repeated in other paradoxes. But nevertheless, it will be useful to indicate them.

First, the task of the barber is characterized by a peremptory demand “to shave all”, while not allowing any exceptions to the rule “who does not shave himself”. If the task did not impose such a strict restriction on “shaving all”, then the barber could be easily excluded from the list dangerous for the task. If the task did not limit only those who do not shave themselves, then the barber would only have frightened us instead of creating a crisis in the foundations of mathematics. Therefore, in other tasks, where a strict requirement is placed from the category of “all such and only such elements”, it is worthwhile to pay attention to the search for internal contradictions in such a formulation.

Secondly, the barber in the task is a special entity, different from all the others by its participation in shaving everyone who is supposed to shave. Without the barber, the entity system would have collapsed and would not constitute a single and meaningful task. But in spite of such a special status in the system of entities and restrictions, the supporters of paradoxes insist on a single attitude to all participants in the process, regardless of the additional restrictions that are imposed on the barber. But it is the special status of the barber that led to the emergence of a contradiction in the requirements, because besides the “like all” attitude, which requires the barber to be shaved, the barber is also not required to shave himself, and other barbers are excluded in the problem statement. Therefore, in other tasks it is necessary to identify the system-forming function of the elements, and if it exists, carefully check the correlation of the requirements “to all” and the requirements for this element. Otherwise, it is easy to get another contradiction in the requirements.

Problems in the remaining paradoxes

For now we will miss the paradox of sets, since we will need it later in connection with the problems of set theory.

Now let's see where the evil lies in the paradox of self-applicability. Along with the previously mentioned feature in the form of an implicit contradiction in the conditions here, we can also add freedom of interpretation of the meaning of self-applicability. That is, the meaning of the relationship of self-applicability can be interpreted quite widely, and therefore a contradiction can easily slip into these wide gaps. Therefore, in this case it would not be superfluous severity of definitions. But it is also impossible to overestimate the severity to the absolute, otherwise, as we saw in the example of the barber, the contradictions will result from the very severity.

Just as in the parade of the barber, in the paradox of self-applicability we have a special element of the system, distinguished from the others by the fact that when considering it the algorithm of the system works is changed. For all other words, it is enough for us to understand how the domain of definition of the meaning of a word relates to the word itself (that is, to calculate the number of syllables or pay attention to the language in which the word is written), but for the word “non-self-applicable” we have a not quite obvious definition, possibly coinciding with the system itself, in which the assessment of self-applicability is made. That is, for the word “non-self-applicable” the task itself explains to us some possible sense of applicability, but this explanation is implicit and weak.

Then you can find out the specific restrictions that contradict each other precisely for the word “non-self-applicable”. Obviously, after receiving any answer to the question of self-applicability, the paradox supporters simply launch an answer evaluation algorithm that compares the answer with the meaning of the word “non-self-applicable” and gives a negation both in the case of self-applicability and in the case of non-self-applicability. The algorithm consists in indicating the meaning of a word in response to a decision on self-applicability, and in indicating a coincidence of meanings in the case of a response on non-self-applicability. Moreover, if for other words it was possible to obtain an unambiguous algorithm, for example, counting the number of syllables, then for the word “not self-applicable” the algorithm for identifying self-applicability is completely unclear. And in the task it is required not only to give an answer about the applicability, but also to find implicitly an algorithm of self-applicability, only after the application of which a distinct answer is possible. What is the self-applicability algorithm for the word "non-self-applicable"?

If we accept that such an algorithm does not exist in nature, then it becomes immediately obvious that such a word is not self-applicable, but then at least one new algorithm will be required, convincing supporters of paradoxes of the need to ignore the similarity of the answer “non-self-applicable” with the meaning of the word “non-self-applicable”. And when creating such a new algorithm, we are already stepping on the fragile ground of the fight against implicitly given meanings, which the proponents of paradoxes will undoubtedly interpret exclusively in their favor. That is, you will need to create an algorithm that strictly proves something in the presence of completely lax rules, which are interpreted very arbitrarily. At the very least, this is a very difficult task, which ensures the viability of the paradox - just no one wants to kill time and nerves to achieve something that is quite possibly unattainable.

If we accept that the algorithm of self-applicability exists, then again we will encounter the rigid position of supporters of paradoxes, who demand to accept their refutation in the form of an indication of the contradiction of the meaning of the word “not self-applicable” by the presence of the algorithm of its self-applicability. And again we will get into conditions when it will be necessary to strictly prove something, and the answer of the supporters of paradoxes will still be based on very loose rules.

In general, for the case of self-applicability, we have a successful correspondence of the word “non-self-applicable” to both positive and negative answers, allowing supporters of paradoxes in both cases to deny the argument of solving the problem. That is, in the hands of the paradox supporters there is a simple algorithm that provides the answer “wrong” in all possible cases. An alternative for trying to solve a problem is to find an algorithm that can bypass the obstacles placed by supporters of the paradoxes. Since the search for such an algorithm seems, at least, difficult, the paradox supporters have a very serious advantage over all those who are trying to solve such a problem.

For greater clarity, we can give an example of a similar problem, but with an obvious big difference in the complexity of the position of the critic and the position of the decider. The question is - is there life near the star at the opposite end of the universe? Obviously, the strict evidence in this case is somewhat difficult, while the position of the critic only implies the simplest doubts in response to any decision. When issuing a decision in the form of “life is”, the critic will say “prove it!”, Which is obviously not easy. When issuing a decision in the form of "no life", the critic will declare "what if there is?".

A very similar situation holds for the paradox of a false statement. Here the direct meaning of the phrase is opposed to any answer. But in one case it is indicated that there is a mismatch of meanings, which is taken as proof of the fallacy of the decision, and in another case it is indicated that the meanings coincide, which again is taken as proof of the fallacy of the decision. That is, as in the self-applicability paradox, a successful phrase was chosen that allows us to construct a simple algorithm for denying any of the two possible answers. At the same time, the algorithm for proving the correctness of the decision again looks incomparably complex compared to the lack of complexity on the side of supporters of paradoxes.

You can minimize the previous paradox by asking the question - is the lie true? For such a statement, there are still no problems on the part of the supporters of paradoxes, and it is still unclear how to argue a vague understanding of the essentially meaningless phrase. The senselessness does not give the possibility to object to the supporters of paradoxes with reason, but they themselves are completely satisfied with this senselessness, because they interpret it formally as some kind of task conditions that are not obliged to have any meaning at all. But just such an approach, detached from reality, as we see, easily leads to contradictions such as a negative answer in any case. And the implicitness of contradictions allows supporters of paradoxes to insist on their own. If we can prove that there are no more and less zero numbers at the same time, then in cases with well-composed phrases that have no meaning, the evidence of inconsistency is nontrivial (because if there is no sense, what to prove?), And therefore in such cases it is difficult to identify contradictions in restrictions on the decision, which in turn leads to the presence of soil for the germination of the next paradoxes. That is why it is worth emphasizing once again the possibility of leaving formal reasoning in the direction of meaningless, and therefore fraught with paradoxes, which again can shake including such rigorous sciences as mathematics.

Problems of set theory

What are the paradoxes dangerous for mathematics? Very simply - if a certain formal theory allows one to derive contradictory results, then this means that such a theory allows one to derive absolutely everything. In other words - such a theory will give us the opportunity to derive any nonsense. Therefore, it is necessary to carefully monitor the absence of contradictions in the theories used. But how to avoid contradictions in theories?

At first there was the so-called naive set theory. In this theory, arguments about sets were made out in the form of sentences in natural language (originally in German), but as we have seen a little higher, reasoning in natural language is sometimes taken in a contradictory direction, and sometimes simply in a meaningless one. But the non-obviousness of such a turn makes it difficult even for very advanced minds to consider danger in time. Therefore, Georg Cantor, the creator of set theory, missed a number of similar moments when the requirements of his theory suggested to him a seemingly simple but not fully thought out way to satisfy them. So the very possibility of presenting anything allows us to imagine an infinite number of numbers, but as we saw a little higher, paradoxes can follow such a presentation.Another need - in the construction of sets by mathematical means - also led to an analogue of the paradox of sets, but already written in mathematical terms.

— , , ? , , ( ) « » , - . , , . , , , . .

Cantor (the creator of the theory of sets) could not overcome this barrier, but since then the topic of its substantiation was very relevant in mathematics, Kantor's theory came in the way for such a role, and therefore they tried to develop it, but a little differently.

Mathematicians saw the cause of the paradoxes in an insufficiently strict definition of the theory, which allowed some liberties, which, as we have seen, can lead to the complete meaninglessness of some definitions. But since rigor alone is not enough to eliminate the paradoxes (that is why a much more extensive list of signs of potential problems is given above) mathematicians soon found a paradox even in a rigorous statement of the theory.

For the formation of sets, mathematicians suggested using a set of functions that return true if an element belongs to a set and false if the element does not belong to a set. That is, a mathematical filter was created that worked very simply - all the elements that went through it were included in the new set. Thus, it was possible to construct any sets in a strict mathematical way. The idea itself is very simple and, of course, quite workable, just as an infinite number of filters work in a technique and, especially (in its pure form, very close to set theory), in information technology. But its strict implementation was not so simple.

The following formula was proposed for filtering:

$$

Here are the icons $$ and $$designate "there is such" and "for all", which in combination with the name of the variable ( x or y ) gives a restriction on the formula following the sign. In ordinary language, this means that there is a y for which the formula is true, in which for any x is a true formula that is separated by brackets. In brackets we see the icon$$, denoting that x belongs to the set y , and then an equivalence sign, which declares that x belongs to the set y equivalent to the execution of the logical function P (x) (it is called the propositional function or predicate). In general, the formula in parentheses states that if the element x passed filtering in the function P (x) , then it belongs to the set y , and vice versa - the elements belonging to y satisfy P (x) . The whole formula is read like this - there is a set y , for which for any x the restriction is satisfied that ifx is filtered by the function P (x) , then it belongs to the set y .

Now let's pay attention to the difference between the initial idea of ​​filtering and its design in the form of a formula. In the formula, though the arbitrariness that is present in the informally defined filter is limited, the same mistake was made that led to the parade of barber.

In the formula, all elements of x are treated equally. But in the above paradoxes, we have seen that such an interpretation of one size fits all causes paradoxes. As a result, a counter-example was quickly found showing the inconsistency of such a formula. Since in the formula there are no restrictions on the values ​​of x, then nothing prevents us from substituting y for it , and instead of filtering function to substitute$$ . Here is a sign $$denotes a logical negation. Then after all the replacements we get:

$$

That is, the denial of ownership was equivalent to belonging. True, in strict form it is necessary to derive two such formulas so that one would be the negation of the other, but we will leave this exercise to mathematicians, because for us the meaning is clear and true. Here we see that the interpretation of all elements of x as obeying the general requirements has led to a contradiction when substituting the system-forming element y for x , which has already been shown for other paradoxes.

As a result, mathematicians had to be corrected. But they corrected the situation as follows (sign$$ means logical AND):

$$

That is, in the preceding formula is added set and which further limits permissible for inclusion in the elements. The idea was correct - if we take for the new set only those elements that are included in the set of admissible parameters P (x) , then we get the opportunity to exclude falling into the set of system-forming element y . But did the result eliminate paradoxes?

As in the previous version, we have complete freedom for the variables a and x, and this, if we recall the signs of paradoxes, is a very dangerous easing of restrictions. Such freedom in the cases shown above led to the possibility of specifying two contradictory limitations in one phrase or formula. In addition, the system-forming element y in the new formula is again treated equally with everyone, since the substitution of y instead of x is still permissible . Therefore, there is a theoretical possibility to set a formula P (x) that would contradict the rest of the constructions of the general formula, which can lead to a contradiction.

But we will not look for such a substitution, but simply give an assessment of possible options for any substitutions in the new formula. To do this, first consider the case when a equal to the empty set, then $$impracticable and to achieve equivalence will have to choose y for which impracticable$$ .Such a value y can be an empty set. That is, with such substitutions, the formula does not contain contradictions. But since a can be any, we need to check what happens if a is a non-empty set. Then everything will depend on the possibility of choosing such a y , so that for any x and any P (x) the formula remains true. It is worth noting here that such a formula in set theory is accepted as an axiom, and therefore its falsity with some substitutions will become a somewhat inconvenient moment for the whole theory.

Given a non-empty set a, the set y can take the following values:

1) empty set
2) non-empty set:
2.1) not intersecting with a
2.2) intersecting with a :
2.2.1) including additional elements to the intersection:
2.2.1.1) intersection is less than a
2.2.1.2) intersection is equal to a
2.2.2) not including the additional elements to the intersection:
2.2.2.1) the intersection is less than a
2.2.2.2) the intersection is equal to a.

Following are the restrictions on x and the values ​​of P (x) for which the axiom becomes false. Here $$ - logical and $$ - logical or.

one) $$
2.1) $$
2.2.1.1) $$
2.2.1.2) $$
2.2.2.1) $$$$
2.2.2.2) $$

As we can see, if a contains any elements, there is not a single variant of the substitution y , for which it is impossible to specify such x and / or P (x) , so that the axiom is always true.

What conclusion can be drawn from this result? In the personal opinion of the author of this text, the conclusion could be this: when translating sound ideas about applying a filter to a dry formula language, an error was made in the form of a loss of connection with reality, or speaking differently, not all the properties of the original system were identified and formalized in a proper way. . Well, to recognize the conclusions or reject, of course, to choose the reader, who is now precisely aware of how to independently sort out such issues.