The Central Idea
Suppose we want to prove a statement \(P\).
A proof by contradiction begins by assuming its negation:
\[ \neg P. \]We then reason from that assumption until we obtain a contradiction, written symbolically as
\[ \bot. \]The structure is
\[ \boxed{\neg P\Longrightarrow\bot.} \]Since the assumption \(\neg P\) leads to an impossibility, \(\neg P\) cannot be true. Therefore \(P\) must be true.
What Counts as a Contradiction?
A contradiction is a conclusion that cannot consistently hold with the assumptions and known facts.
Common forms include:
- obtaining both \(R\) and \(\neg R\);
- deriving an impossible equality such as \(0=1\);
- showing an integer must be both even and odd;
- violating a known inequality;
- contradicting a stated hypothesis;
- contradicting a previously established theorem or definition.
The contradiction must arise logically from the assumption being tested.
The Law of Noncontradiction
Classical mathematical reasoning does not allow a proposition and its negation to both be true:
\[ \neg(P\land\neg P). \]For example, an integer cannot simultaneously satisfy
\[ n\text{ is even} \]and
\[ n\text{ is not even}. \]Proof by contradiction exploits this incompatibility.
The Basic Procedure
To prove \(P\) by contradiction:
- Identify the claim \(P\).
- Negate it carefully.
- Assume \(\neg P\).
- Combine that assumption with the hypotheses and known facts.
- Derive an impossibility or inconsistency.
- Reject the assumption \(\neg P\).
- Conclude that \(P\) is true.
Negation Comes First
The method depends on beginning with the correct negation of the desired claim.
If the claim is
\[ x>5, \]its negation is
\[ x\le5. \]If the claim is
\[ n\text{ is even}, \]for an integer \(n\), its negation is
\[ n\text{ is odd}. \]If the claim is
\[ x\in A, \]its negation is
\[ x\notin A. \]Example: No Integer Is Both Even and Odd
Suppose, for contradiction, that an integer \(n\) is both even and odd.
Then there exist integers \(a\) and \(b\) such that
\[ n=2a \]and
\[ n=2b+1. \]Therefore,
\[ 2a=2b+1. \]Rearranging gives
\[ 2(a-b)=1. \]The left side is even, while the right side is odd.
This is impossible. Therefore no integer can be both even and odd.
Contradiction through an Impossible Equality
Sometimes a contradiction appears as an equation that no permitted objects can satisfy.
For example, if valid reasoning from an assumption produces
\[ 2k=2k+1, \]then subtraction gives
\[ 0=1. \]Since this equality is false, at least one assumption leading to it must be false. In a proof by contradiction, the deliberately introduced negation is the assumption we reject.
Example: \(\sqrt{2}\) Is Irrational
One of the classic applications of contradiction proves that
\[ \sqrt{2} \]cannot be written as a ratio of integers.
Assume, for contradiction, that \(\sqrt{2}\) is rational. Then
\[ \sqrt{2}=\frac{a}{b} \]for integers \(a,b\) with \(b\ne0\), where the fraction is in lowest terms.
Squaring gives
\[ 2=\frac{a^2}{b^2}, \]so
\[ a^2=2b^2. \]Thus \(a^2\) is even, so \(a\) is even.
Write
\[ a=2k. \]Substitute:
\[ (2k)^2=2b^2. \]Hence
\[ 4k^2=2b^2, \]and therefore
\[ b^2=2k^2. \]Thus \(b^2\) is even, so \(b\) is even.
Both \(a\) and \(b\) are even, so they share a factor of \(2\). This contradicts the assumption that \(a/b\) was in lowest terms.
Therefore,
\[ \boxed{\sqrt{2}\text{ is irrational}.} \]Why Lowest Terms Matter in the \(\sqrt{2}\) Proof
Rationality alone gives
\[ \sqrt{2}=\frac{a}{b} \]for some integers \(a,b\).
We may choose a representation in lowest terms because every rational number has one.
The contradiction is then precise:
\[ \gcd(a,b)=1 \]was assumed, but the argument shows that
\[ 2\mid a \quad\text{and}\quad 2\mid b. \]Those two facts cannot both hold.
Proof by Contradiction and Conditional Statements
To prove
\[ P\Longrightarrow Q \]by contradiction, we assume the hypothesis \(P\) and also assume that the conclusion fails:
\[ P\land\neg Q. \]The goal is to derive
\[ \bot. \]Thus the structure is
\[ \boxed{P\land\neg Q\Longrightarrow\bot.} \]Example: If \(n^2\) Is Even, Then \(n\) Is Even
Prove:
\[ n^2\text{ even}\Longrightarrow n\text{ even}. \]Assume \(n^2\) is even.
Suppose, for contradiction, that \(n\) is not even. Since \(n\) is an integer, \(n\) must be odd:
\[ n=2k+1 \]for some integer \(k\).
Then
\[ n^2=(2k+1)^2 \] \[ =4k^2+4k+1 \] \[ =2(2k^2+2k)+1. \]Therefore \(n^2\) is odd.
But the hypothesis says \(n^2\) is even. This contradiction shows that \(n\) cannot be odd.
Hence
\[ \boxed{n\text{ is even}.} \]Contradiction versus Contrapositive
The previous theorem can also be proved by contrapositive.
Contrapositive:
\[ n\text{ odd}\Longrightarrow n^2\text{ odd}. \]Contradiction:
assume \(n^2\) is even and \(n\) is odd, then derive that \(n^2\) is odd.
The algebra may be identical, but the logical structure is different.
How to Distinguish the Two Methods
For a theorem
\[ P\Longrightarrow Q, \]a contrapositive proof assumes
\[ \neg Q \]and proves
\[ \neg P. \]A contradiction proof assumes
\[ P\land\neg Q \]and derives an impossibility.
The destination of the argument is the clearest distinction.
Contradiction Can Prove Nonexistence
Suppose the claim says that no object with certain properties exists.
A natural contradiction strategy is:
- assume such an object exists;
- use its required properties;
- derive an impossibility;
- conclude that no such object exists.
Nonexistence statements are therefore common candidates for contradiction.
Example: There Is No Greatest Integer
Suppose, for contradiction, that there is a greatest integer \(N\).
Since \(N\) is an integer,
\[ N+1 \]is also an integer.
But
\[ N+1>N. \]This contradicts the assumption that \(N\) is the greatest integer.
Therefore,
\[ \boxed{\text{there is no greatest integer}.} \]Example: There Is No Smallest Positive Rational Number
Suppose, for contradiction, that \(r\) is the smallest positive rational number.
Since \(r>0\),
\[ \frac{r}{2}>0. \]Since the rationals are closed under division by the nonzero integer \(2\),
\[ \frac{r}{2} \]is rational.
But
\[ 0<\frac{r}{2}Hence no smallest positive rational number exists.
Contradiction Can Prove Uniqueness
To prove that an object is unique, contradiction often begins by assuming there are two distinct objects satisfying the required property.
The goal is then to show that the two objects must actually be equal.
The contradiction has the form
\[ a\ne b \]together with
\[ a=b. \]Example: An Additive Identity Is Unique
Suppose \(e\) and \(f\) are both additive identities in a number system.
Since \(f\) is an additive identity,
\[ e+f=e. \]Since \(e\) is an additive identity,
\[ e+f=f. \]Therefore,
\[ e=f. \]Thus two distinct additive identities cannot exist.
Hence the additive identity is unique.
Contradiction Can Use Order Properties
Suppose an assumption leads to
\[ xLikewise, if an argument produces both
\[ a and \[ b\le a, \]the two conclusions are incompatible.
Example: A Positive Number Cannot Equal Its Negative
Let \(x>0\). We claim
\[ x\ne -x. \]Suppose, for contradiction, that
\[ x=-x. \]Adding \(x\) to both sides gives
\[ 2x=0. \]Therefore
\[ x=0. \]But this contradicts the hypothesis \(x>0\).
Hence
\[ \boxed{x\ne -x}. \]Contradiction through Divisibility
Divisibility arguments often produce contradictions by forcing an integer to have incompatible remainder or factor properties.
For example, if one assumption implies
\[ 3\mid n \]while another gives
\[ 3\nmid n, \]the contradiction is immediate.
Example: Two Consecutive Integers Cannot Both Be Even
Suppose, for contradiction, that \(n\) and \(n+1\) are both even.
Then there exist integers \(a\) and \(b\) such that
\[ n=2a \]and
\[ n+1=2b. \]Substituting \(n=2a\) gives
\[ 2a+1=2b. \]Therefore,
\[ 1=2(b-a). \]The right side is even, but \(1\) is odd. This is impossible.
Hence two consecutive integers cannot both be even.
Contradiction and the Pigeonhole Principle
Some counting proofs begin by denying the conclusion and then showing that the assumed arrangement cannot fit within the available possibilities.
For example, if \(n+1\) objects are placed into \(n\) boxes, suppose every box contains at most one object.
Then the boxes could contain at most \(n\) objects.
But there are \(n+1\) objects.
This contradiction shows that some box must contain at least two objects.
Contradiction and Extremal Reasoning
Another common pattern is to assume an extremal object exists and then construct one that is even larger, smaller, earlier, later, or otherwise more extreme.
The proof that there is no greatest integer follows this pattern:
\[ N\quad\longrightarrow\quad N+1>N. \]The construction directly violates the assumed extremal property.
Example: Infinitely Many Prime Numbers
Suppose, for contradiction, that there are only finitely many primes:
\[ p_1,p_2,\ldots,p_n. \]Form the integer
\[ N=p_1p_2\cdots p_n+1. \]Since \(N>1\), it has a prime divisor \(q\).
If \(q\) were one of the listed primes, then \(q\) would divide
\[ p_1p_2\cdots p_n. \]Because \(q\mid N\), it would also divide the difference
\[ N-p_1p_2\cdots p_n=1. \]No prime divides \(1\).
Therefore \(q\) is a prime not on the supposedly complete list, a contradiction.
Hence,
\[ \boxed{\text{there are infinitely many prime numbers}.} \]The New Number Need Not Be Prime
In the previous proof,
\[ N=p_1p_2\cdots p_n+1 \]does not need to be prime.
It only needs to have a prime divisor that is absent from the original list.
This is an important proof-reading habit: use only the claim the argument actually establishes.
Contradiction and Set Arguments
Set proofs may use contradiction by assuming that an element belongs to one set while failing to belong to another set that should contain it.
For example, to prove
\[ A\subseteq B, \]one may suppose there exists
\[ x\in A \]with
\[ x\notin B, \]and then derive an inconsistency from the definitions of \(A\) and \(B\).
Example: Intersection Containment by Contradiction
Prove
\[ A\cap B\subseteq A. \]Suppose, for contradiction, that this containment fails.
Then there exists some \(x\) such that
\[ x\in A\cap B \]but
\[ x\notin A. \]By the definition of intersection,
\[ x\in A\cap B \]implies
\[ x\in A. \]Thus \(x\in A\) and \(x\notin A\), a contradiction.
Therefore,
\[ \boxed{A\cap B\subseteq A}. \]Contradiction Can Be Short
A contradiction proof does not need to be long.
Suppose \(a
If \(a=b\), then substituting into \(a
Therefore \(a\ne b\).
The Contradiction Must Depend on the Negated Claim
It is not enough to find any false statement during a proof.
The contradiction must result from the hypotheses together with the assumption that the desired conclusion is false.
If the contradiction arises only because an unrelated invalid step was introduced, the proof establishes nothing.
Every inference still has to be valid.
Do Not Manufacture a Contradiction
A proof cannot intentionally perform an illegal operation merely to obtain something absurd.
For example, dividing by a quantity that might be zero can produce false equations.
A legitimate contradiction must follow from valid mathematics applied to the assumptions.
Common Error: Negating the Claim Incorrectly
Suppose the claim is
\[ x>4. \]The contradiction assumption must be
\[ x\le4, \]not merely \(x<4\).
Leaving out equality means the proof does not address every way the claim could fail.
Common Error: Assuming the Claim Instead of Its Negation
To prove \(P\) by contradiction, begin with
\[ \neg P. \]Beginning by assuming \(P\) does not set up a contradiction proof.
The entire method depends on testing the consequences of the claim being false.
Common Error: Confusing Contradiction with Contrapositive
For
\[ P\Longrightarrow Q, \]contrapositive proof seeks
\[ \neg Q\Longrightarrow\neg P. \]Contradiction instead assumes
\[ P\land\neg Q \]and seeks
\[ \bot. \]Both may begin with \(\neg Q\), but contradiction retains the original hypothesis \(P\) and aims for impossibility rather than \(\neg P\).
Common Error: Declaring a Contradiction Too Early
Two statements are not contradictory merely because they look different.
For example,
\[ n=2k \]and
\[ n=4r \]can both be true.
A genuine contradiction requires logically incompatible statements, such as
\[ n\text{ even} \]and
\[ n\text{ odd}. \]Common Error: Forgetting to Identify the Contradiction
A reader should not have to guess which statements are incompatible.
Instead of ending with
\[ n^2=2m \quad\text{and}\quad n^2=2r+1, \]explicitly state:
The first equation makes \(n^2\) even, while the second makes \(n^2\) odd. An integer cannot be both even and odd. This is a contradiction.
Common Error: Failing to Close the Proof
After deriving a contradiction, finish the logical argument.
A standard ending is:
This contradiction shows that our assumption was false. Therefore the original claim is true.
The contradiction invalidates the temporary negation, not the theorem being proved.
Common Error: Rejecting the Wrong Assumption
A contradiction proof may involve several assumptions.
The original hypotheses are part of the theorem and remain in force.
The assumption introduced specifically for contradiction is the negation of the desired claim.
When a contradiction appears, it is that temporary assumption that is rejected.
Quantifiers and Contradiction
Contradiction often appears in quantified statements.
To negate
\[ \forall x\,P(x), \]write
\[ \exists x\,\neg P(x). \]To negate
\[ \exists x\,P(x), \]write
\[ \forall x\,\neg P(x). \]Correct quantifier negation is essential when contradiction is used for universal or existential claims.
Example: Negating a Universal Claim
Suppose we want to prove
\[ \forall n\in\mathbb Z,\;P(n). \]A contradiction proof assumes the negation:
\[ \exists n\in\mathbb Z\text{ such that }\neg P(n). \]The proof then works with that hypothetical counterexample and shows that it cannot exist.
Example: Negating an Existence Claim
Suppose we want to prove
\[ \exists x\in S\text{ such that }P(x). \]Its negation is
\[ \forall x\in S,\;\neg P(x). \]A contradiction proof assumes that no element of \(S\) has property \(P\), then derives an impossibility.
Contradiction and Counterexamples
A counterexample disproves a universal statement.
A contradiction proof of a universal theorem may begin by assuming that a counterexample exists and then showing that no such counterexample can satisfy the required conditions.
In this sense, contradiction can prove that every attempted counterexample fails.
Choosing When to Use Contradiction
Proof by contradiction is particularly useful when:
- the claim is a nonexistence statement;
- the claim is a uniqueness statement;
- the negation produces a concrete object to analyze;
- the hypotheses and negated conclusion quickly become incompatible;
- direct construction of the conclusion is awkward;
- an extremal assumption can be violated by a new construction.
Prefer Simpler Proofs When Available
A theorem that admits a short direct proof does not become better merely because it can also be proved by contradiction.
Proof strategy should reduce complexity and expose structure.
Use contradiction when the assumption of failure creates a useful route, not simply because the method is available.
A Reliable Contradiction Workflow
- State exactly what must be proved.
- Write its logical negation.
- Assume that negation temporarily.
- Retain all original hypotheses.
- Unpack definitions and quantify variables carefully.
- Apply only valid algebraic and logical steps.
- Track consequences until two facts become incompatible.
- State explicitly what the contradiction is.
- Reject the temporary negation.
- Conclude the original statement.
Example: Full Contradiction Workflow
Prove that there is no smallest positive integer greater than \(1\) that is divisible by every positive integer.
Step 1: Assume the opposite.
Suppose such an integer \(N>1\) exists.
Step 2: Use the required property.
Since \(N\) is divisible by every positive integer, it must be divisible by
\[ N+1. \]Therefore there exists an integer \(k\) such that
\[ N=(N+1)k. \]Step 3: Use size information.
Because \(N>0\) and \(N+1>N\), no positive multiple of \(N+1\) can equal the smaller positive number \(N\).
The only possible integer multiple with smaller absolute value would be \(k=0\), which would give \(N=0\), also impossible.
Step 4: Identify the contradiction.
The assumption requires \(N+1\mid N\), but the size relation
\(0
Step 5: Conclude.
Therefore no such positive integer exists.
Practice 1: Parity
Prove by contradiction that no integer is both even and odd.
Practice 2: Consecutive Integers
Prove by contradiction that two consecutive integers cannot both be even.
Practice 3: Greatest Integer
Prove by contradiction that there is no greatest integer.
Practice 4: Smallest Positive Rational
Prove by contradiction that there is no smallest positive rational number.
Practice 5: Conditional Statement
Prove by contradiction:
\[ n^2\text{ even}\Longrightarrow n\text{ even}. \]Practice 6: Order
Suppose \(a
Practice 7: Set Containment
Prove by contradiction:
\[ A\cap B\subseteq B. \]Practice 8: Negate the Statement
Write the negation of
\[ \forall n\in\mathbb Z,\;n^2\ge0. \]Practice 9: Identify the Contradiction
A proof derives both
\[ 3\mid n \]and
\[ n=3k+1 \]for some integer \(k\).
Explain why these statements are incompatible.
Practice 10: Contradiction or Contrapositive?
To prove \(P\Rightarrow Q\), a student assumes \(P\) and \(\neg Q\) and works until obtaining \(R\land\neg R\).
Identify the proof method.
Practice Answers
Practice 1
Suppose \(n\) is both even and odd. Then
\[ n=2a=2b+1 \]for integers \(a,b\). Hence
\[ 2(a-b)=1, \]which is impossible because the left side is even and the right side is odd.
Practice 2
Suppose \(n\) and \(n+1\) are both even. Then
\[ n=2a,\qquad n+1=2b. \]Substitution gives
\[ 2a+1=2b, \]so
\[ 1=2(b-a), \]impossible.
Practice 3
Suppose \(N\) is the greatest integer. Then \(N+1\) is also an integer and
\[ N+1>N, \]contradicting the definition of \(N\).
Practice 4
Suppose \(r>0\) is the smallest positive rational. Then \(r/2\) is rational and
\[ 0<\frac r2Practice 5
Assume \(n^2\) is even and suppose \(n\) is odd. Then
\[ n=2k+1 \]and therefore
\[ n^2=2(2k^2+2k)+1, \]which is odd. Thus \(n^2\) is both even and odd, a contradiction. Therefore \(n\) is even.
Practice 6
Suppose \(a=b\). Substituting into \(a
Practice 7
Suppose there exists \(x\in A\cap B\) with \(x\notin B\). By definition of intersection, \(x\in B\). Thus \(x\in B\) and \(x\notin B\), a contradiction. Hence
\[ \boxed{A\cap B\subseteq B}. \]Practice 8
The negation is
\[ \boxed{\exists n\in\mathbb Z\text{ such that }n^2<0.} \]Practice 9
The equation
\[ n=3k+1 \]means that \(n\) leaves remainder \(1\) upon division by \(3\), so \(3\nmid n\). This contradicts \(3\mid n\).
Practice 10
This is proof by contradiction.
The student assumes the hypothesis together with the negation of the conclusion:
\[ P\land\neg Q, \]and derives an explicit contradiction.
What to Remember
Proof by contradiction has the basic form
\[ \boxed{\neg P\Longrightarrow\bot.} \]For a conditional statement \(P\Rightarrow Q\), it often appears as
\[ \boxed{P\land\neg Q\Longrightarrow\bot.} \]- negate the desired claim carefully;
- retain the original hypotheses;
- use only valid mathematical steps;
- derive a genuine incompatibility or impossibility;
- state the contradiction explicitly;
- reject the temporary negation, not the theorem's hypotheses;
- distinguish contradiction from contrapositive proof;
- use the method when assuming failure creates a useful mathematical structure.
The strategic question is: If the claim were false, what consequences would follow, and can those consequences coexist with the mathematics already known?
Where We Go Next
Direct proof, contrapositive proof, and contradiction all establish claims through logical implication. The next major method addresses statements indexed by the natural numbers and proves infinitely many cases through a repeatable logical step.
The next lesson, Mathematical Induction, develops the base-case and inductive-step structure used to prove sequences of related statements.