Қарсылық арқылы дәлелдеу

Proof by showing that the negation is impossible

In logic, proof by contradiction is a form of proof that establishes the truth or the validity of a proposition, by showing that assuming the proposition to be false leads to a contradiction. Although it is quite freely used in mathematical proofs, not every school of mathematical thought accepts this kind of nonconstructive proof as universally valid. More broadly, proof by contradiction is any form of argument that establishes a statement by arriving at a contradiction, even when the initial assumption is not the negation of the statement to be proved. In this general sense, proof by contradiction is also known as indirect proof, proof by assuming the opposite, and reductio ad impossibile. A mathematical proof employing proof by contradiction usually proceeds as follows:

The proposition to be proved is P.
We assume P to be false, i. e., we assume ¬P. It is then shown that ¬P implies falsehood. This is typically accomplished by deriving two mutually contradictory assertions, Q and ¬Q, and appealing to the law of noncontradiction. Since assuming P to be false leads to a contradiction, it is concluded that P is in fact true. An important special case is the existence proof by contradiction: in order to demonstrate that an object with a given property exists, we derive a contradiction from the assumption that all objects satisfy the negation of the property.

Proof by contradiction is equivalent to the law of the excluded middle, first formulated by Aristotle, which states that either an assertion or its negation is true, P ∨ ¬P.

The law of noncontradiction was first stated as a metaphysical principle by Aristotle. It posits that a proposition and its negation cannot both be true, or equivalently, that a proposition cannot be both true and false. Formally the law of non contradiction is written as ¬(P ∧ ¬P) and read as "it is not the case that a proposition is both true and false". The law of non contradiction neither follows nor is implied by the principle of Proof by contradiction. The laws of excluded middle and non contradiction together mean that exactly one of P and ¬P is true.

Euclid's theorem states that there are infinitely many primes. In Euclid's Elements the theorem is stated in Book IX, Proposition 20:

Prime numbers are more than any assigned multitude of prime numbers. Depending on how we formally write the above statement, the usual proof takes either the form of a proof by contradiction or a refutation by contradiction. We present here the former, see below how the proof is done as refutation by contradiction. If we formally express Euclid's theorem as saying that for every natural number there is a prime bigger than it, then we employ proof by contradiction, as follows. Given any number , we seek to prove that there is a prime larger than Suppose to the contrary that no such p exists (an application of proof by contradiction). Then all primes are smaller than or equal to , and we may form the list of them all. Let be the product of all primes and Because is larger than all prime numbers it is not prime, hence it must be divisible by one of them, say Now both and are divisible by , hence so is their difference , but this cannot be because 1 is not divisible by any primes. Hence we have a contradiction and so there is a prime number bigger than

The following examples are commonly referred to as proofs by contradiction, but formally employ refutation by contradiction (and therefore are intuitionistically valid).

The classic proof that the square root of 2 is irrational is a refutation by contradiction. Indeed, we set out to prove the negation ¬ ∃ a, b ∈ a/b = by assuming that there exist natural numbers a and b whose ratio is the square root of two, and derive a contradiction.

Russell's paradox, stated set theoretically as "there is no set whose elements are precisely those sets that do not contain themselves", is a negated statement whose usual proof is a refutation by contradiction.

Proofs by contradiction sometimes end with the word "Contradiction!". Isaac Barrow and Baermann used the notation Q. E. A., for "quod est absurdum" ("which is absurd"), along the lines of Q. E. D., but this notation is rarely used today. A graphical symbol sometimes used for contradictions is a downwards zigzag arrow "lightning" symbol (U+21AF: ↯), for example in Davey and Priestley. Others sometimes used include a pair of opposing arrows (as or ), struck out arrows , a stylized form of hash (such as U+2A33: ⨳), or the "reference mark" (U+203B: ※), or .

G. H. Hardy described proof by contradiction as "one of a mathematician's finest weapons", saying "It is a far finer gambit than any chess gambit: a chess player may offer the sacrifice of a pawn or even a piece, but a mathematician offers the game."

In automated theorem proving the method of resolution is based on proof by contradiction. That is, in order to show that a given statement is entailed by given hypotheses, the automated prover assumes the hypotheses and the negation of the statement, and attempts to derive a contradiction.