lat. Reductio ad absurdum) is a type of proof in which the validity of a certain judgment (proof thesis) is carried out through the refutation of a judgment that contradicts it - antithesis. The refutation of the antithesis is achieved by establishing its incompatibility with the obviously true judgment. Often proof by contradiction relies on the ambiguity principle.
Great Definition
Incomplete definition ↓
PROOF FROM THE CONTRARY
substantiation of a judgment by refutation by the method of "reduction to absurdity" (reductio ad absurdum) of some other judgment, namely that which is the denial of the justified (D. from p. 1st type) or that which is the denial of which is justified (D. from p. 2nd type); "reduction to absurdity" consists in the fact that from a refuted judgment a k.-l. an obviously false conclusion (for example, a formal logical contradiction), which indicates the falsity of this judgment. The need to distinguish between two types of D. from p. follows from the fact that in one of them (namely, in D. from p. of the 1st type) there is a logical transition from the double negation of the judgment to the affirmation of this judgment (i.e., the so-called double negation rule, which allows the transition from A to A, see Double negation laws), while in the other there is no such transition. The course of reasoning in D. from the item of the 1st type: it is required to prove judgment A; for the purposes of proof, we assume that proposition A is false, i.e. that its negation is true: ? (not-A), and, based on this assumption, we logically deduce c.-l. false statement, eg. contradiction, - we carry out "reduction to absurdity" of judgment A; this testifies to the falsity of our assumption, i.e. proves the truth of double negation: A; application to A of the rule of removal of double negation completes the proof of proposition A. The course of reasoning in D. from item 2 of the 2nd type: is it required to prove a proposition?; for the purposes of proof, we assume that proposition A is true and reduce this assumption to absurdity; on this basis we conclude that A is false, i.e. what is right?. The distinction between the two types of D. from p. is important because in the so-called intuitionistic (constructive) logic, the law of removal of double negation does not take place, which is why D. from p., which are essentially related to the application of this logical law, is also not allowed. See also Indirect Proof. Lit.: Tarsky?., Introduction to the logic and methodology of deductive sciences, trans. from English, M., 1948; Asmus VF, The doctrine of logic about proof and refutation, [M.], 1954; Kleene S. K., Introduction to Metamathematics, trans. from English, M., 1957; Church?., Introduction to Mathematics. logic, trans. from English, [vol.] 1, M., 1960.
THE METHOD FROM THE OPPOSITE (hereinafter referred to as the MOP) is a scientific and applied method named after the outstanding Ukrainian educator, the founder of a number of scientific schools and directions, Vasily Kozmich the Nasty. VK Nasty was born on February 29, 1513, according to the old style, in the village of Nizhnie Lopukhy near Chernigov. Vasya was a weak and flimsy boy from childhood, and constantly, starting from kindergarten, was subjected to ridicule by peers, which later predetermined his bad character.
In the future, the words "do everything in spite of others" actually became the motto of the life of V.K. Opposite. So, in spite of everyone, he left his native Kholmogory and entered the Moscow State University. Lomonosov (and not in Suvorov School, as his father wanted), to spite everyone, he never married anyone (although his grandmother Vasilisa Nasty found him at least 14 brides in his entire life), to spite everyone, citing mushroom season, did not receive the Fields Medal - the highest award in the field of mathematics.
The essence of the method from the opposite can be conveyed by the following points:
1. A wrong assumption is made.
2. It turns out what follows from this assumption on the basis of known knowledge.
3. A dead end is being entered.
4. A correct conclusion is drawn that an incorrect assumption is wrong.
Many scientists, philosophers, researchers and even artists have become ardent supporters of the ideas of the Ukrainian enlightener. For example, lobotomy was used for the first time in medical practice when an attempt was made to resolve the age-old philosophical dispute about the primacy of matter or consciousness with the help of a medical experiment. This is how Lobachevsky, a student of V.K.
The method from the opposite is often used at the present time in a variety of fields. human life. For example, Moscow Mayor Luzhkov successfully uses it to cultivate the artistic taste of Muscovites by installing sculptures by Tsereteli in the city. The leadership of the Central Internal Affairs Directorate, using this method, decided to find the killers of the well-known journalist Politkovskaya, since other methods, in view of the particular complexity of the case, do not give results. Armed with MOS, Moscow policemen know that by consistently identifying all the uninvolved, they will automatically go on the trail of the killers.
The whole life and even death of V.K. Opposite was a vivid illustration of his method. The scientist tragically passed away on February 29, 1613 at the age of 112, hanging himself in spite of his grandmother Vasily Nasty, who did not allow Vasily Kozmich to taste the jam from the refrigerator. Despite the ambivalent attitude towards V.K. Nasty because of his bad temper, most scientists and researchers still consider MOP to be one of the most powerful weapons. modern science in general and mathematics in particular.
____________________________________
Vasily Kozmich Nasty, an outstanding Ukrainian educator (1513 - 1613)
I express my gratitude
What is the method of proof "by contradiction"?
The essence of the method of proof by contradiction consists in two stages. The first in the proof of the EXISTENCE of the proof and the second in the proof of the UNIQUENESS of the proof. Clumsily described, but wanted to say the following. When proving theorems using this method, you need to show that there is a solution to a given problem or theorem, and then prove that this solution will be unique. This is not the only method used in proving theorems, but as a mathematical and logical tool it is not without interest.
The method of proof by contradiction is used not only in mathematics, although it has become quite widespread there as a tool for proving individual problems and theorems.
In fact, this is a logical method of proving any statements, which can be applied in any field of knowledge. Even in the humanities and social sciences. Simply, in the technical sciences we are dealing with numbers, and many people are convinced just by the presence of these icons, and in the world of logic we operate with conclusions that can never be considered absolute truth.
We studied this method of proof at school in the middle classes, when we take as a basis some statement that cannot be proven in any way, instead they take the directly opposite statement to it, prove that it is false, therefore, what we cannot prove is true, And this is the only correct solution to this issue.
In life, we talk about something, we cannot prove it, but we give an opposite example and prove that it is wrong: money was stolen from the cache, Vasya and Petya knew about it, but Petya had an alibi - he went to the dacha for the whole week, which means , Vasya stole the money.
By the method of proof by contradiction called the way in which an unprovable truth becomes true, only because something else is always wrong - and this is exactly what is provable. Accordingly, as a result of this method, albeit indirectly, we proved unprovable truth
This law is based on the law of double negation, if A is not true, then A is true.
For example, you think you have an ulcer. Your doctor, in order to refute this judgment, proves to you by refuting what you are sure of, that is, your statement and says that you do not have an ulcer, since gastroscopy showed that there is no damage in the stomach cavity, you do not lose weight and you can eat everything whatever you want.
Standard technique, for example, in mathematics. We need to prove statement A. And this is difficult. Then they take the opposite statement B, and prove that it is false. It follows that A is true. The same is true in life. A simple example: someone says: Mr. X is a thiefquot ;. His opponent: But how to prove it? First: Suppose he is an honest manquot ;. Second: Yes, this is a mockery of chickens! First: So we proved that X is a thief :)))
Practice No. 2
Topic: Logic and proof. Proof: direct, reverse, by contradiction. Method of mathematical induction.
The lesson is designed for 2 academic hours.
Target: explore various methods evidence (direct reasoning, the method of "by contradiction" and reverse reasoning), illustrating the methodology of reasoning. Consider the method of mathematical induction.
Theoretical material
Proof Methods
When proving theorems, logical reasoning is used. Evidence in computer science an integral part of checking the correctness of algorithms. The need for proof arises when we need to establish the truth of a proposition of the form (A V). There are several standard types of evidence, including the following:
- Direct reasoning (proof).
We assume that statement A is true and show the validity of B. This method of proof excludes the situation when A is true, a B is is false, since it is in this and only this case that the implication (A C) takes a false value (see table).
Thus, direct proof goes from considering the arguments to proving the thesis, i.e., the truth of the thesis is directly substantiated by the arguments. The scheme of this proof is as follows: from the given arguments(a, b, c, ...) a provable thesis must necessarily follow q.
This type of evidence is carried out in judicial practice, in science, in controversy, in the writings of schoolchildren, in the presentation of material by a teacher, etc.
Examples:
1. The teacher in the lesson with direct proof of the thesis “People history maker”, shows; Firstly that the people are the creator of material wealth, Secondly , substantiates the enormous role of the popular masses in politics, explains how in the modern era the people are actively fighting for peace and democracy, third , reveals its great role in the creation of spiritual culture.
2. In chemistry lessons, direct evidence of the combustibility of sugar can be presented in the form of a categorical syllogism: All carbohydrates are combustible. Sugar is a carbohydrate. Sugar is flammable.
In the modern fashion magazine “Burda”, the thesis “Envy is the root of all evil” is substantiated with the help of direct evidence with the following arguments: “Envy not only poisons people everyday life, but it can lead to more serious consequences, therefore, along with jealousy, anger and hatred, it undoubtedly belongs to the worst character traits. Creeping up imperceptibly, envy hurts painfully and deeply. A person envies the well-being of others, suffers from the consciousness that someone is more fortunate.
2. Reverse reasoning(proof ) . We assume that the statement B is false and show the fallacy of A. That is, in fact, in a direct way, we check the truth of the implication ((not B) (not A)) which, according to the table, is logically equivalent to the truth of the original statement (A B).
3. The method "by contradiction".
This method is often used in mathematics. Let a - a thesis or theorem to be proved. We assume by contradiction that a false, i.e. true nope (or). From the assumption we deduce consequences that contradict reality or previously proven theorems. We have, while- false, therefore, its negation is true, i.e., which, according to the law of two-valued classical logic (→ a) gives a. So, true a , which was to be proved.
There are a lot of examples of evidence “by contradiction” in school course mathematics. So, for example, the theorem is proved that from a point lying outside a straight line, only one perpendicular can be dropped to this straight line. By contradiction, the following theorem is also proved: “If two lines are perpendicular to the same plane, then they are parallel.” The proof of this theorem begins directly with the words: “Assume the contrary, i.e., that the lines AB and CD not parallel."
Mathematical induction
computer program in computer science, it is called correct or correct if it does what it says in its specification. Although testing a program may give the expected result in the case of some individual initial data, it is necessary to prove by the methods of formal logic that the correct output data will be obtained for any input initial values.
Checking the correctness of an algorithm containing cycles requires a rather powerful proof method called " mathematical induction».
At the heart of any mathematical research are deductive and inductive methods. The deductive method of reasoning is reasoning from the general to the particular, i.e. reasoning that starts with overall result, and the final moment is a partial result. Induction is applied when passing from particular results to general ones, i.e. is the opposite of the deductive method. The method of mathematical induction can be compared with progress. We start from the lowest, as a result logical thinking we come to the highest. Man has always striven for progress, for the ability to develop his thought logically, which means that nature itself has destined him to think inductively.
Principle of mathematical induction this is the following theorem:
Let we have an infinite sequence of statements P 1 , P 2 , ..., P n indexed by natural numbers, and: the statement P 1 true; if some statement P k - true, then the following statement P k +1 is also true.
Then the principle of mathematical induction states that all statements in the sequence are true.
In other words, the principle of mathematical induction can be formulated as follows: if a woman is the first in the queue, and there is a woman behind each woman, then everyone in the queue is a woman.
The method of reasoning based on the principle of mathematical induction is called the method of mathematical induction. To solve problems by the method of mathematical induction, it is necessary:
1) formulate the statement of the problem as a sequence of statements P 1 , P 2 , ..., P n , ... ;
2) prove that the statement P 1 true (this stage is called the base of induction); 3) prove that if the statement P n is true for some n= k, then it is also true for n = k + 1 (this step is called the induction step).
In view of the unreliability of the conclusion, induction cannot serve as a method of proof. But she ispowerful heuristic method, i.e., the method of discovering new truths.
Induction can lead to a false conclusion. So, for example, calculating the values of the expression n 2 +n+17 for n = 1,2,3, ..., 15, we get invariably prime numbers, and this suggests that the value of this expression for any natural n is a prime number. In other words, on the basis of fifteen particular premises, a general conclusion has been obtained that relates to an infinite number of special cases, and this conclusion turns out to be false, since even with n = 16 we obtain a composite number 16 2 +16+17=172.
There have been cases in the history of mathematics when famous mathematicians were wrong in their inductive conclusions. For example, P. Fermat suggested that all numbers of the form 22 n + 1 are simple, based on the fact that at n = 1,2,3,4 they are such, but L. Euler found that already at n = 5 the number 232 + 1 is not prime (it is divisible by 641). However, the possibility of obtaining a false conclusion with the help of induction is not a basis for denying the role of induction in schooling mathematics.
Guidelines
Example 1: Show by direct reasoning that the product xy of two odd integers x and y is always odd.
Solution. Any odd number, and in particular x, can be written as x = 2 m + 1, where m Z . Similarly, y = 2 n + 1, n Z .
Hence, the product xy = (2 m + 1)(2n + 1) = 4mn + 2m + 2n + 1 = 2(2 mn+m+n ) + 1 is also an odd number.
Example 2: Let n N . Show, using the reverse method of proof, that if n 2 is odd, then n is odd.
Solution. The negation of the statement about the odd number n 2 is the statement " n 2 even", and the statement about parity n is a negation of the statement "the number n odd." Thus, it is necessary to show in a direct way of reasoning that the parity of a number n implies the evenness of its square n2.
Since n is even, then n =2 m for some integer m . Therefore, n 2 \u003d 4 m 2 \u003d 2 (2 m 2) is an even number.
Example 3: Show by contradiction that the solution of the equation x 2 = 2 is ir rational number, i.e., cannot be written as a fraction with integer numerator and denominator.
Solution. Here we must assume that the solution x of the equation x 2 = 2 is rational, i.e. written as a fraction x = with integers m and n , and n 0. Assuming this, we need to obtain a contradiction either with the assumption or with some previously proven fact.
As you know, a rational number is ambiguously written
in the form of a fraction. For example, x = == etc. However, it can be considered that m and n have no common divisors. In this case, the ambiguity of the record disappears.
So, we additionally assume that the fraction x = is irreducible ( m and n do not have common divisors). By condition, the number x satisfies the equation x 2 = 2. Hence, () 2 = 2, whence m 2 = 2 n 2 .
It follows from the last equality that the number m2 even. Hence, m is also even and can be represented as m = 2p for some integer p. Substituting this information into the equation m 2 \u003d 2 n 2 , we get that 4p 2 \u003d 2 n 2, i.e. n 2 \u003d 2p 2.
But then n is also an even number. Thus, we have shown that m , and n - even numbers. Therefore, they have a common divisor of 2. If we now recall that we assumed the absence common divisor at the numerator and denominator of the fraction, we will see a clear contradiction.
The found contradiction leads us to an unambiguous conclusion: the solution of the equation x 2 = 2 cannot be a rational number, i.e. it is irrational.
Example 4: Let us prove the following equality by induction (which, of course, admits other proofs):
1 + 2 + 3 + ... + n = n(n + 1)/2.
Base. For n = 1, the equality turns into the identity 1 = 1 (1 + 1)/2.
Step. Let the equality hold for n = k: 1 + 2 + 3 + ... + k = k(k + 1)/2.
Let's add k + 1 to both sides of this equality. On the left side we get the sum 1+2+3+...+k+(k+1),and on the right - k(k+1)/2+(k+1)=(k(k+1)+2(k+1))/2=((k+2)(k+1))/ 2.
So, 1 + 2 + 3 + ... + k + (k + 1) = (k + 1)(k + 2)/2, and this is the required equality for n = k + 1, where n means arbitrary natural number.
Control questions
- What is the difference between proof by direct reasoning,the opposite, from the contrary?
- What does mathematical induction mean? Explain the principle of mathematical induction.
Individual tasks
1. Using proof methods:
1) By direct reasoning, prove the truth of the statement: n and m are even numbers n + m is an even number.
2) Give the opposite proof of the statement: n 2 - even number n - even.
3) Prove by contradiction that n+m - odd number one of the terms is even and the other is odd.
2. Prove each of the statements by mathematical induction.
1) 1 + 5 + 9 +…+(4 n - 3) = n (2 n 1) for everyone natural numbers n.
2) 1 2 +2 2 +…+ n 2 = n (n +1)(2 n +1)/6 for all natural numbers n.
3) d for all natural numbers n.
4) Number n 3 n is divisible by 3 for all natural values of the number n.
5) 1*1! + 2* 2!+…+- n * n ! = (n + 1)! 1 for all natural numbers n.
(The character n ! is read as " n factorial" and denotes the product of all natural numbers from 1 to n inclusive: n ! \u003d l * 2 * 3 *** (n - l) * n.)
1. Find the error in the following "proof" that all horses are of the same suit.
We will prove the following statement by induction on n: "In any herd of n these are horses, they are all of the same suit." The base (n = 1) is obvious: in this case all horses are one horse, it is obviously of the same suit. Ш: Let all horses in any herd of k horses have the same suit. Consider a herd of k + 1 horses. We choose two horses a and b in it and consider the remaining k – 1 horses. Let's make a herd of these remaining horses by adding a. There are k horses in it, so, by the induction hypothesis, they are all of the same suit. So horse a has the same suit as the remaining horses. It is proved similarly that horse b has the same suit. So all k + 1 horses have the same suit. The assertion has been proven.
2. On an infinite checkered sheet of paper, 100 cells are painted black, and all the rest are white. In one move, it is allowed to repaint any four cells forming a 2x2 square in the opposite color. Prove that in a few moves it is possible to achieve that all cells are white if and only if any horizontal and any vertical contains an even number of black cells.
Proof "from the contrary" (in Latin "reductio ad absurdum") is characterized by the fact that the very process of proving an opinion is carried out by refuting the opposite judgment. An antithesis can be proven false by establishing the fact that it is incompatible with a true proposition.
Usually such a method is visually demonstrated using a formula where A is the antithesis and B is the truth. If the solution turns out that the presence of variable A leads to results different from B, then A is proved to be false.
Proof "by contradiction" without the use of truth
There is also an easier proof of the falsity of the "opposite" - the antithesis. Such a formula-rule says: “If a contradiction arose in the formula when solving with variable A, A is false.” It does not matter whether the antithesis is negative or affirmative. In addition, a simpler way of proving by contradiction contains only two facts: the thesis and antithesis, truth B is not used. This greatly simplifies the proof process.
Apagogue
In the process of proving by contradiction (which is also called "reduction to absurdity"), apagogy is often used. This is a logical technique, the purpose of which is to prove the incorrectness of any judgment so that a contradiction is revealed directly in it or in the consequences arising from it. The contradiction can be expressed in the identity of obviously different objects or as conclusions: conjunction or pairs B and not B (true and not true).
Reception of evidence "by contradiction" is often used. In many cases, it is not possible to prove the incorrectness of a judgment in any other way. In addition to apagogy, there is also a paradoxical form of proof by contradiction. This form was used in Euclid's "Elements" and represents the following rule: A is considered proven if it is possible to demonstrate the "true falsity" of A.
Thus, the process of proving by contradiction (it is also called indirect and apogogical evidence) is as follows. An opposite opinion is put forward, consequences are deduced from this antithesis, among which the false is sought. They find evidence that among the consequences there is indeed a false one. From this it is concluded that the antithesis is wrong, and since the antithesis is wrong, the logical conclusion follows that the truth is contained in the thesis.