In
logicLogic, from the Greek λογική is the art and science of reasoning. More specifically, it is defined by the Penguin Encyclopedia to be "The formal systematic study of the principles of valid inference and correct reasoning". As a discipline, logic dates back to Aristotle, who established its...
,
proof by contradiction is a form of
proofIn mathematics, a proof is a convincing demonstration that some mathematical statement is necessarily true. Proofs are obtained from deductive reasoning, rather than from inductive or empirical arguments. That is, a proof must demonstrate that a statement is true in all cases, without a single...
that establishes the truth or
validityThe term Validity in logic applies to arguments or statements.-Validity of arguments:An argument is valid if and only if the truth of its premises entails the truth of its conclusion. It would be self-contradictory to affirm the premises and deny the conclusion...
of a
propositionA proposition is a sentence expressing something true or false. In philosophy, particularly in logic, a proposition is identified ontologically as an idea, concept, or abstraction whose token instances are patterns of symbols, marks, sounds, or strings of words...
by showing that the premise that the proposition is false implies a
contradictionIn classical logic, a contradiction consists of a logical incompatibility between two or more propositions. It occurs when the propositions, taken together, yield two conclusions which form the logical inversions of each other...
. Since by the law of bivalence a proposition must be either true or false, and its falsity has been shown impossible, the proposition must be true.
In other words, to prove by contradiction that , show that or its equivalent . Then, since implies a contradiction, conclude .
Proof by contradiction is also known as
indirect proof,
apagogical argument,
reductio ad impossibile, or
reductio ad absurdumIn logic, proof by contradiction is a form of proof that establishes the truth or validity of a proposition by showing that the premise that the proposition is false implies a contradiction...
.
Examples
A classic proof by contradiction from mathematics is the proof that the square root of 2 is irrational. If it were rational, it could be expressed as a fraction
a/
b in lowest terms, where
a and
b are integers, at least one of which is odd. But if
a/
b = √2, then
a2 = 2
b2. Therefore
a2 must be even.
Because the square of an odd number is odd, that in turn implies that
a is even. This means that
b must be odd because a/b is in lowest terms.
On the other hand, if
a is even, then
a2 is a multiple of 4. If
a2 is a multiple of 4 and
a2 = 2
b2, then 2
b2 is a multiple of 4, and therefore
b2 is even, and so is
b.
So
b is odd and even, a contradiction. Therefore the initial assumption—that √2 can be expressed as a fraction—must be false.
Cubing-the-cube puzzle
A more recent proof by contradiction is the proof that a cube cannot be cut into a finite number of smaller cubes with no two the same size. Consider the smallest cube on the bottom face; on each of its four sides, either a neighbouring cube or the border of the main cube is rising above it. This means that any larger cube will not fit on top of it (the "footprint" of such a cube is too large). Since different cubes aren't permitted to have the same sizes, only smaller cubes can be placed directly on top of it. But then the smallest of these would likewise be surrounded by larger cubes, so could only have smaller cubes directly on top of
it... and so on, in an
infinite regressAn infinite regress in a series of propositions arises if the truth of proposition P1 requires the support of proposition P2, and for any proposition in the series Pn, the truth of Pn requires the support of the truth of Pn+1...
, requiring an infinite number of cubes, which violates our conditions. (This gives rise to a
proof by inductionProof by induction may refer to:*Proof by mathematical induction*Proof by inductive logic...
that the cubing-the-cube puzzle is also unsolvable in dimensions higher than three.)
In mathematics
Say we wish to disprove
propositionA proposition is a sentence expressing something true or false. In philosophy, particularly in logic, a proposition is identified ontologically as an idea, concept, or abstraction whose token instances are patterns of symbols, marks, sounds, or strings of words...
p. The procedure is to show that assuming
p leads to a logical
contradictionIn classical logic, a contradiction consists of a logical incompatibility between two or more propositions. It occurs when the propositions, taken together, yield two conclusions which form the logical inversions of each other...
. Thus, according to the law of non-contradiction,
p must be false.
Say instead we wish to prove proposition
p. We can proceed by assuming "not
p" (i.e. that
p is false), and show that it leads to a logical contradiction. Thus, according to the law of non-contradiction, "not
p" must be false, and so, according to the law of the excluded middle,
p is true.
In symbols:
To disprove
p: one uses the
tautologyIn propositional logic, a tautology is a propositional formula that is true under any possible valuation of its propositional variables. For example, the propositional formula is a tautology, because the statement is true for any valuation of A...
(
p → (
R ∧ ¬
R)) → ¬
p, where
R is any proposition and the ∧ symbol is taken to mean "and". Assuming
p, one proves
R and
¬R, and concludes from this that
p → (R ∧ ¬R). This and the tautology together imply
¬p.
To prove
p: one uses the tautology (¬
p → (
R ∧ ¬
R)) →
p where
R is any proposition. Assuming ¬
p, one proves
R and ¬
R, and concludes from this that ¬
p → (
R ∧ ¬
R). This and the tautology together imply
p.
For a simple example of the first kind, consider the proposition, ¬
p: "there is no smallest rational number greater than 0". In a proof by contradiction, we start by assuming the opposite,
p: that there
is a smallest rational number, say, .
Now let . Then
x is a rational number greater than 0 and less than . (In the above symbolic argument, "
x is the smallest rational number" would be
R and " (which is different from
x) is the smallest rational number" would be ¬
R.) But that contradicts our initial assumption,
p, that was the
smallest rational number. So we can conclude that the original proposition, ¬
p, must be true — "there is no smallest rational number greater than 0".
[Note: the choice of which statement is
R and which is ¬
R is arbitrary.]
It is common to use this first type of argument with propositions such as the one above, concerning the
non-existence of some mathematical object. One assumes that such an object exists, and then proves that this would lead to a contradiction; thus, such an object does not exist. For other examples, see proof that the square root of 2 is not rational and
Cantor's diagonal argumentCantor's diagonal argument, also called the diagonalisation argument, the diagonal slash argument or the diagonal method, was published in 1891 by Georg Cantor as a proof that there are infinite sets which cannot be put into one-to-one correspondence with the infinite set of natural numbers...
.
On the other hand, it is also common to use arguments of the second type concerning the
existence of some mathematical object. One assumes that the object doesn't exist, and then proves that this would lead to a contradiction; thus, such an object must exist. Although it is quite freely used in mathematical proofs, not every
school of mathematical thoughtThe philosophy of mathematics is the branch of philosophy that studies the philosophical assumptions, foundations, and implications of mathematics. The aim of the philosophy of mathematics is to provide an account of the nature and methodology of mathematics and to understand the place of...
accepts this kind of argument as universally valid. See further Nonconstructive proof.
In mathematical logic
In
mathematical logicMathematical logic is a subfield of mathematics with close connections to computer science and philosophical logic. The field includes both the mathematical study of logic and the applications of formal logic to other areas of mathematics...
, the proof by contradiction is represented as:
- if
- then
or
- if
- then
In the above,
p is the proposition we wish to prove or disprove; and
S is a set of statements which are given as true — these could be, for example, the axioms of the theory we are working in, or earlier theorems we can build upon. We consider
p, or the negation of
p, in addition to
S; if this leads to a logical contradiction
F, then we can conclude that the statements in
S lead to the negation of
p, or
p itself, respectively.
Note that the
set-theoretic unionIn set theory, the union of a collection of sets is the set of all distinct elements in the collection. The union of a collection of sets gives a set .- Definition :A simple example:...
, in some contexts closely related to
logical disjunctionIn logic and mathematics, or, also known as logical disjunction or inclusive disjunction, is a logical operator that results in true whenever one or more of its operands are true. E.g. in this context, "A or B" is true if A is true, or if B is true, or if both A and B are true. In grammar, or is a...
(or), is used here for sets of statements in such a way that it is more related to
logical conjunctionIn logic and mathematics, logical conjunction or and is a two-place logical connective that has the value true if both of its operands are true, otherwise a value of false.-Notation:...
(and).
Notation
Proofs by contradiction sometimes end with the word "Contradiction!".
Isaac BarrowIsaac Barrow was an English scholar and mathematician who is generally given credit for his early role in the development of calculus; in particular, for the discovery of the fundamental theorem of calculus. His work centered on the properties of the tangent; Barrow was the first to calculate the...
and Baermann used the notation Q.E.A., for "quod est absurdum" ("which is absurd"), along the lines of
Q.E.D.Q.E.D. is an abbreviation of the Latin phrase , which literally means "which was to be demonstrated". The phrase is written in its abbreviated form at the end of a mathematical proof or philosophical argument to signify that the last statement deduced was the one to be demonstrated; the...
, 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 arrowsThe Five Fingered Hand of Eris is the name given to "two opposing arrows converging into a common point." The "canonical" example is shown at right, but the passage quoted goes on to say, "It may be vertical, horizontal, or else such, and it may be elaborated or simplified as desired."The...
(as or ), struck-out arrows , a stylized form of hash (such as U+2A33: ⨳), or the "reference mark" (U+203B: ※). The "up tack" symbol (U+22A5: ⊥) used by philosophers and logicians (see
contradictionIn classical logic, a contradiction consists of a logical incompatibility between two or more propositions. It occurs when the propositions, taken together, yield two conclusions which form the logical inversions of each other...
) also appears, but is often avoided due to its usage for
orthogonalityIn mathematics, two vectors are orthogonal if they are perpendicular, i.e., they form a right angle. The word comes from the Greek , meaning "straight", and , meaning "angle".- Definitions :...
.
Quotations
In the words of
G. H. HardyG. H. Hardy FRS was a prominent English mathematician, known for his achievements in number theory and mathematical analysis....
(
A Mathematician's ApologyA Mathematician's Apology is a 1940 essay by British mathematician G. H. Hardy. It concerns the aesthetics of mathematics with some personal content, and gives the layman an insight into the mind of a working mathematician.-Summary:...
), "Reductio ad absurdum, which Euclid loved so much, is one of a mathematician's finest weapons. It is a far finer gambit than any
chessChess is a board game played between two players. The current form of the game emerged in Southern Europe during the second half of the 15th century after evolving from a similar, much older game of Indian origin...
gambitA gambit is a chess opening in which a player, most often White, sacrifices material, usually a pawn, with the hope of achieving a resulting advantageous position. Some well-known examples are the King's Gambit , Queen's Gambit , and Evans Gambit...
: a chess player may offer the sacrifice of a pawn or even a piece, but a mathematician offers the game."
Further reading
- J. Franklin and A. Daoud, Proof in Mathematics: An Introduction, Quakers Hill Press, 1996, ch. 6