Lecture 21 min.
The importance of proofs in our lives, and especially in science, cannot be overstated. And yet proofs are not encountered as often as we would like. Sometimes something that is not a proof at all is passed off as one. Everyone resorts to proofs, but few people stop to think about what it means to "prove," why a proof "proves," whether every statement can be proved or refuted, whether everything needs to be proved, and so on.
Proof is reasoning according to definite logical rules that establishes the truth of some assumption, statement, hypothesis, or theory. In different fields of science, art, and other human activity, this term can take on different meanings.
Refutation is a logical operation aimed at destroying a proof by establishing the falsity or groundlessness of a previously advanced proposition, the thesis. The proposition that must be refuted is called the thesis of the refutation.
Our conception of proof as a special intellectual operation is formed in the course of carrying out specific proofs. By studying different areas of knowledge, we also absorb the proofs that belong to them. On this basis we gradually form, most often without noticing it, a general intuitive idea of proof as such, of its general structure, which does not depend on the particular material, of the aims and meaning of proof, and so on.
The study of mathematics plays a special role here. Since time immemorial, mathematical reasoning has been regarded as the universally recognized standard of proof. When we want to praise someone's argumentation, we call it mathematically rigorous and impeccable.
Studying proof through concrete examples is both interesting and useful. But it is also necessary to become familiar with the foundations of the logical theory of proof, which speaks about proofs irrespective of their field of application. Practical skills in proving and an intuitive idea of it are sufficient for many purposes, but far from all. Here, as usual, practice needs theory.
The logical theory of proof is simple and accessible in its basis, although working out its details requires a special symbolic language and other sophisticated techniques of modern logic.
In logic, proof is understood as a procedure for establishing the truth of some statement by citing other statements whose truth is already known and from which the first follows of necessity.
In a proof one distinguishes the thesis — the statement that must be proved, the grounds (arguments) — the propositions by means of which the thesis is proved, and the logical connection between the arguments and the thesis. The concept of proof thus always presupposes that the premises on which the thesis rests are specified, along with the logical rules by which statements are transformed in the course of the proof. In ordinary practice we rarely state all the premises we use, and in essence we never pay attention to the rules of logic we apply.
One of the main tasks of logic is to give the concept of proof a precise meaning. But although this concept is almost the central one in logic, it has no precise, strictly universal definition applicable in all cases and in all scientific theories.
"The concept of proof," writes the logician and mathematician V. A. Uspensky, "in all its fullness belongs to mathematics no more than to psychology: after all, a proof is simply reasoning that convinces us so thoroughly that with its help we are ready to convince others."
Proof is one of many ways of persuading. In science it is one of the main methods. One can say that the scientific method of persuasion is, above all, a method of rigorous and exact proofs. The requirement that scientific reasoning be demonstrative determines the "general illumination" that modifies the colors that fall within its sphere of action. All other requirements for scientific argumentation are permeated by this "general illumination." Without it, argumentation inevitably degenerates into an unproven set of general declarations and admonitions, into an appeal to faith and emotions.
Each of us bears the "burden of proof" for the propositions we put forward. It is important to keep thinking about the substantive side of the matter. At the same time, it is also essential that the unity of substance and demonstrability always be ensured. No artificial devices, no eloquence, can help if there are no well-founded ideas and convincing proofs.
The task of a proof is to establish exhaustively the validity of the thesis being proved.
Since a proof is concerned with complete confirmation, the connection between the arguments and the thesis must be deductive in character. In its form, a proof is a deductive inference or a chain of such inferences leading from true premises to the proposition being proved.
An old Latin proverb says: "Proofs are weighed by quality, not by quantity." Indeed, deduction from truth yields only truth. If correct arguments have been found and the proposition to be proved has been deductively derived from them, the proof has been accomplished, and nothing more is required.
Often a broader meaning is given to the concept of proof. In this case, proof is understood as any procedure for substantiating the truth of a thesis, including both deduction and inductive reasoning, references to the connection of the proposition being proved with facts, observations, and so on. A broad interpretation of proof is usual in the humanities. It is also found in experimental reasoning that relies on observation.
As a rule, proof is also understood broadly in everyday life. To confirm an idea that has been put forward, facts, phenomena typical in some respect, and the like are actively brought in. There is of course no deduction in this case; only induction can be involved. But, nevertheless, the supposed substantiation is often called a proof.
The broad use of the concept of "proof" does not in itself lead to misunderstandings. But only on one condition. One must constantly keep in mind that inductive generalization, the transition from particular facts to general conclusions, yields not certain but merely probable knowledge.
Many of our statements are neither true nor false. Evaluations, rules, pieces of advice, demands, and warnings do not describe the situation under consideration. They indicate what it should become, in what direction it should be transformed. From descriptions we are entitled to demand that they be true. But a successful order, piece of advice, and so on we characterize as effective or expedient, but not as true.
The standard definition of proof uses the concept of truth. To prove a thesis means to derive it logically from other propositions that are true. But there are statements that are not connected with truth. It is also obvious that in operating with them one can and should be both logical and demonstrative.
Thus the question arises of a substantial extension of the concept of proof. It must cover not only descriptions but also statements of the type of evaluations and demands.
The task of redefining proof is successfully solved by modern logic. Such of its branches as the logic of evaluations and the logic of norms convincingly show that reasoning about values and norms is also subject to the requirements of logic and does not go beyond the sphere of the logical.
Types of Proof
Fig. . Features of proof as a type of argumentation
The way of connecting arguments from the condition to the conclusion of a proposition is called a method of proof. Methods of proof are divided into direct and indirect. The techniques of direct proof are distinguished as follows: transformation of the condition of the proposition (synthetic); transformation of the conclusion of the proposition (ascending analysis); finding necessary criteria for the validity of the proposition with subsequent verification of the reversibility of the reasoning (descending analysis); and successive transformation now of the condition, now of the conclusion of the proposition.
The condition of any theorem is a sufficient condition with respect to the conclusion. In turn, the conclusion is a necessary condition with respect to the condition of that theorem.
The techniques of indirect proof include:
1) the method of proof by contradiction (the truth of the statement being proved is established by refuting the proposition that contradicts it);
2) the disjunctive method (the statement being proved is regarded as one of the possible alternatives, when all the assumptions are rejected except one).
The proof of a mathematical statement is called synthetic if it is carried out according to the following logical scheme:
P1(x)→P2(x)→P3(x)→…Pn-1(x)→Pn(x) = P(x),
where Pi is a definite set of propositions of the mathematical theory within which the given statement is proved. Thus, in the synthetic method of proving a theorem, the chain of syllogisms is constructed so that thought moves from the condition of the theorem to its conclusion.
Example. Let us consider the synthetic proof of the theorem "on the sum of the interior angles of a triangle."
Given: ABC is a triangle
Prove:
∟1+∟2+∟3=180°
Proof:
1. "Consider triangle ABC."
2. "Draw through vertex B a line, a, parallel to AB."
3. "Consider ∟1 and ∟4. What are these angles called?"
"Correct, they are alternate interior angles formed by the intersection of the parallel lines a and AC with the transversal AB, and therefore ∟1=∟4."
4. "Now consider ∟3 and ∟5. What can you say about them?"
"Correct, they are alternate interior angles formed by the intersection of the parallel lines a and AC with the transversal BC, and therefore ∟3=∟5."
5. "Look at angles 3, 4, and 5. What can be said about them?"
"Correct, they form a straight angle."
"We already know that the sum of a straight angle is equal to 180°, ∟4+∟3+∟5= 180°."
6. "And since ∟1=∟4 and ∟3=∟5, we can rewrite our expression as ∟1+∟2+∟3=180°."
7. "We have proved that the sum of the interior angles of a triangle is equal to 180°."
In the analytic proof of a theorem, the chain of syllogisms is constructed so that thought moves from the conclusion of the theorem to its condition. Two kinds of analytic method are distinguished: ascending analysis (the analysis of Pappus) and descending analysis (the analysis of Euclid).
Ascending analysis (perfect analysis) is the variety of the analytic method in which, starting from the conclusion P(x), one selects a sufficient condition for it, a proposition
P1(x) such that P1(x)→P(x), then selects a sufficient condition
P2(x) for P1(x), such that P2(x) →P1(x)
is true, and so on until one obtains a sufficient condition
Pn(x) for Pn-1(x) such that Pn(x)→Pn-1(x) and Pn(x) = S(x).
Example: Prove the theorem "If in a quadrilateral the opposite sides are pairwise equal, then the quadrilateral is a parallelogram" by the method of ascending analysis.
Given: ABCD is a quadrilateral.
Prove: ABCD is a parallelogram.
Proof
1. "Let us recall the definition: what kind of quadrilateral is called a parallelogram?"
2. "By the condition, we are given that AB=CD, AD=BC."
3. "So, to prove that quadrilateral ABCD is a parallelogram, it is sufficient to prove that BC‖AD and AB‖CD."
4. "To prove that the sides of a quadrilateral are parallel, it is sufficient to prove the equality of the alternate interior angles formed when two lines are intersected by a third."
5. "To do this, let us draw the diagonal from ∟A to ∟C."
6. "We get ∟ACB and ∟CAD; ∟BAC and ∟ACD."
7. "To prove the equalities ∟ACB = ∟CAD and ∟BAC = ∟ACD, it is sufficient to prove the equality of triangles ABC and CDA."
8. "We have two triangles: ΔABC and ΔADC."
9. "Now we will prove that these triangles are equal. How can this be done?"
10. "AB=CD, AD=BC by the condition, AC is a common side, so the triangles are equal by the third criterion (SSS)."
11. "If the triangles are equal, then the angles inside the triangles will also be equal, so ∟ACB = ∟CAD and ∟BAC = ∟ACD."
12. "Since ∟BAC =∟ACD, the lines AB and CD are parallel: AB ∥ CD by the criterion for parallel lines."
13. "Similarly, since ∟ACB = ∟CAD, the lines BC and AD are parallel: BC ‖AD by the criterion for parallel lines."
14. "The theorem is proved."
Descending analysis (imperfect analysis) is the variety of the analytic method in which, starting from the conclusion P(x), the reasoning proceeds by successively obtaining logical consequences:
P(x) ⇒ P1(x) ⇒ P2(x) ⇒ … ⇒Pn(x),
where Pn(x) is a proposition whose truth value is known to us with certainty. When deriving consequences from P(x), it is temporarily assumed to be true. In descending analysis, just as in ascending analysis, the reasoning starts from the conclusion of the theorem, but what are selected are no longer sufficient conditions but necessary ones.
The derivation of necessary conditions continues until an obvious consequence is reached that is either the condition of the theorem or a previously established true statement. If it turns out to be possible to carry out the reasoning in reverse order, with the condition of the theorem or the obvious statement serving as the starting premise, then we obtain the desired proof.
Example: Carry out a descending analysis to prove the theorem: "If in a quadrilateral the opposite sides are pairwise equal, then the quadrilateral is a parallelogram."
Given: ABCD is a quadrilateral,
Prove: ABCD is a parallelogram.
Proof:
1. "Suppose that ABCD is a parallelogram."
2. "Then BC = AD and AB = CD."
3. "Let us draw the diagonal AC. Then ∟ACB = ∟CAD, ∟BAC = ∟ACD as alternate interior angles formed by parallel lines and a transversal."
4. "We get two equal triangles:" ΔABC = ΔCDA; they are equal by side AC and the two angles adjacent to it).
5. "Since the triangles are equal, the sides will also be equal: AB = CD, AD =BC, AC = AC."
6. "We have proved the truth of the assumption that we made at the beginning of our proof. So we have proved that the given quadrilateral is a parallelogram."
The aim of descending analysis is to search for a proof. The proof itself is carried out in reverse order, and as a result a synthetic proof is obtained.
The analytic-synthetic method of proof consists in the fact that, in the course of the proof, the condition of the theorem and the conclusion are transformed in succession, now one, now the other.
Example: proof of the theorem "If the diagonals of a quadrilateral intersect and are bisected by the point of intersection, then this quadrilateral is a parallelogram."
Given: ABCD is a quadrilateral,
AB = CD, AD =BC.
Prove: ABCD is a parallelogram.
Proof:
It is required to prove that BC‖ AD.
For this it is sufficient to prove that the alternate interior angles ∟BCO and ∟OAD, formed by the lines BC and AD and the transversal AC, are equal.
And to prove that these angles are equal, one must prove the equality of ∟BOC and ∟DOA, and that the angles in question lie opposite correspondingly equal sides. The latter can be seen from the figure, since BO=OD by the condition.
For ΔBOC and ΔDOA to be equal, it is sufficient to prove the first, the second, or the third criterion of congruence of triangles. In this case it is more convenient for us to prove the first criterion, since BO=OD and CO=OA by the condition of the theorem, and ∟BOC = ∟DOA as vertical angles.
Next we draw up a scheme of the analysis carried out:
|
To prove -> |
It is necessary to prove |
| I. BC || AD | II. ∟BCO=∟OAD, as alternate interior angles formed by the lines BC, AD and the transversal AC |
| II. ∟BCO=∟OAD | III. ∟BOC=∟ DOA, and the angles BCO and OAD lie opposite equal sides |
| III. Δ BOC= Δ DOA | IV. The equality of three of its elements, and to determine the criterion of congruence of triangles OA=OC – by the condition BO=OD – by the condition ∟AOD=∟COB – vertical angles Δ BOC= ΔDOA by criterion I |
| THEN | <- IF |
Thus II>III>IV), moving each time from the conclusion to its ground, the reasoning proceeds by the scheme: "to prove (I), it is necessary to prove (II), and so on."
Put more simply, we create a certain chain of definite actions and conditions: each upper proposition is a necessary condition for the one below. After the analysis has been carried out, everything must be brought together into one whole, that is, synthesis must be carried out. Suppose the reasoning is conducted from right to left (IV>III>II>I), stringing together a chain of sufficient conditions from the ground to the conclusion, and reasoning thus: "if IV, then III; if III, then II, and so on."
The method of proof by contradiction consists in beginning the proof of a theorem with the assumption that P(x) does not follow from S(x). Then S(x) is true and P(x) is false. Consequences are derived from S(x) until a consequence is obtained that contradicts either the condition of the theorem or a previously studied theoretical fact. This method is based on the use of the law of contraposition:
Descending analysis is a component of the method of proof by contradiction.
Let S be the set of proved theorems. It is required to prove An ⇒Bn .
Suppose that An ⇒Bn is false; then it is true that 
(every statement is either true or false – the law of excluded middle).
Let 
deny the truth of 
.
In this case we have arrived at a contradiction, an absurdity, so 
is false. But then Bn is rejected.
By the law of excluded middle we must acknowledge that Bn is true.
Proof by reduction to absurdity is an indirect proof:
the truth of 
is established by proving the falsity of .
Proof "by contradiction" has features in common with the analytic method. It begins with a consideration of what is required to be proved.
is broken down into possible cases (elementary analysis), and in every case it is shown that this analysis leads to a contradiction.
Having introduced the proposition 
and adding it to the set of known propositions S, one obtains consequences from 
until a contradictory consequence is reached. This brings proof by contradiction close to descending analysis.
Plan of proof "by contradiction" (A. V. Pogorelov):
1. Suppose that the conclusion of the theorem is false. Assume that the proposition opposite to what is asserted in the theorem is true.
2. By reasoning, relying on axioms and theorems, we arrive at a conclusion that contradicts either the condition of the theorem, or one of the axioms,
or a previously proved theorem.
3. The presence of contradictions forces us to give up the assumption that was made.
4. We acknowledge the correctness of the conclusion of the theorem being proved.
Students should be asked to restate the content of the proof plan in their own words.
Students need to be prepared for the situations that arise when proving theorems by the method "by contradiction" (examples of
exercises):
1) Two line segments a and b are given. What relations can there be between the lengths of these segments?
2) c and d are two line segments: c ⩽ d . What relations can there be between the lengths of these segments?
3) a and b are two line segments, and a ≠ b. What relations can there be between the lengths of these segments?
4) c and d are two line segments, and c is not less than d. What relations can there be between the lengths of these segments?
5) A and B are two angles. Angle A is not less than angle B. What conclusions can be drawn about the magnitudes of these angles?
6) C and D are two angles, and ∟C ≠ ∟D; moreover, angle C is not greater than angle D. What relation exists between angles C and D?
7) AB and CD are two lines lying in the same plane. What cases of the mutual position of these lines are possible?
Example: Let us prove the theorem "A scalene triangle cannot be divided into two equal triangles" by the method of contradiction.
Proof:
1) Suppose ΔABM=ΔBMC, AB ≠BC ≠AC.
2) In these equal triangles BM is a common side, and by the theorem that in equal triangles equal angles lie opposite equal sides, we conclude that ΔBAM = ΔBCM.
3) By the theorem that if the angles at the base of a triangle are equal, then the triangle is isosceles, we conclude that AB = BC.
4) We have obtained that AB = BC, but by the condition of the theorem AB≠BC. We have obtained a contradiction.
5) So our assumption is false, and what is true is that ΔABM ≠ ΔBMC.
1. Into what types are proofs divided?
2. What is proof?
3. What is refutation?
Comments