Contradiction in Proofs

Introduction

students, in discrete mathematics, one of the most powerful ways to prove a statement is to show that the opposite idea leads to something impossible. This method is called proof by contradiction. Instead of starting by proving a claim directly, you temporarily assume the claim is false and then use logical reasoning to reach a contradiction, meaning a statement that cannot be true at the same time as its negation. 🧠

By the end of this lesson, you will be able to:

Explain the main ideas and terminology behind contradiction.
Use contradiction to prove statements in discrete mathematics.
Recognize how contradiction connects to direct proof and contrapositive proof.
Identify contradictions in logical arguments and mathematical statements.
Summarize why contradiction is useful in proof techniques.

This method appears often in number theory, graph theory, and set theory because many important statements are easier to prove by showing that the opposite would create an impossible situation. For example, if a claim says “there is no smallest positive rational number,” one effective approach is to assume that there is such a number and then show that a smaller one must also exist. That contradiction proves the claim.

What a Proof by Contradiction Means

A proof by contradiction begins with a statement you want to prove, often called the conclusion. You then assume the negation of that conclusion is true. From that assumption, you follow logical steps until you derive a contradiction. A contradiction might look like $0=1$, a statement and its negation both being true, or a conflict with a known fact.

The logical structure is this:

Assume the negation of the statement you want to prove.
Use definitions, facts, and logical reasoning.
Reach an impossible conclusion.
Therefore, the original statement must be true.

A contradiction is often written as $P \land \neg P$, which means a proposition $P$ and its negation both hold at the same time. Since that cannot happen, the assumption must be false.

This technique is especially useful when a direct approach is hard. For example, proving that a number is irrational can be easier by assuming it is rational and showing that the assumption causes a conflict. This style of reasoning is a central part of Proof Techniques I because it trains you to think carefully about truth, negation, and logical consequences.

The Logic Behind Contradiction

To use contradiction correctly, it helps to understand negation. If a statement says, “All students in the class have a notebook,” its negation is not “No students have notebooks.” The negation is “At least one student in the class does not have a notebook.” The wording matters because the proof must begin with the exact opposite of the original claim.

For a statement $S$, a contradiction proof works by assuming $\neg S$ and then proving $\bot$, which represents falsehood or impossibility. In everyday math writing, the impossible result might be:

a number is both even and odd,
a quantity is both greater than and less than itself,
a fraction is in lowest terms and not in lowest terms,
or a fact contradicts a known theorem.

The strength of contradiction comes from the law of noncontradiction, a basic logical principle saying a statement cannot be both true and false in the same sense at the same time. If your assumptions force such a clash, then one of the assumptions must be wrong. Since the reasoning steps are valid, the false assumption is the negation you started with.

students, this is why contradiction is so important: it lets you prove statements even when there is no simple “start here and build forward” route. It is a tool for seeing hidden structure in a problem. 🔍

Example 1: Proving There Is No Smallest Positive Rational Number

Let’s prove a famous statement: there is no smallest positive rational number.

Claim

There is no smallest positive rational number.

Proof by contradiction

Assume the opposite: suppose there is a smallest positive rational number, call it $r$.

Now consider the rational number $\frac{r}{2}$. Since $r$ is positive, $\frac{r}{2}$ is also positive. And since rational numbers are closed under division by $2$, $\frac{r}{2}$ is rational.

But $\frac{r}{2} < r$, which means we found a positive rational number smaller than the supposed smallest one. That is a contradiction.

Therefore, the assumption that a smallest positive rational number exists must be false. So there is no smallest positive rational number. □

Why this works

The contradiction comes from the fact that the number assumed to be smallest was beaten by an even smaller positive rational number. This example shows how contradiction often works with “minimum” or “maximum” claims. If you assume an extreme object exists, you may be able to build a smaller or larger one and break the assumption.

Example 2: The Square Root of 2 Is Irrational

One of the most famous proofs by contradiction shows that $\sqrt{2}$ is irrational.

Claim

$\sqrt{2}$ is not a rational number.

Proof by contradiction

Assume $\sqrt{2}$ is rational. Then it can be written as a reduced fraction $\frac{a}{b}$, where $a$ and $b$ are integers with no common factor other than $1$, and $b \neq 0$.

So,

$\sqrt{2} = \frac{a}{b}$

Squaring both sides gives

$2 = \frac{a^2}{b^2}$

which means

$a^2 = 2b^2.$

So $a^2$ is even, which implies $a$ is even. Let $a = 2k$ for some integer $k$.

Substitute back:

$(2k)^2 = 2b^2$

$4k^2 = 2b^2$

$2k^2 = b^2.$

Now $b^2$ is even, so $b$ is even.

But if both $a$ and $b$ are even, then they share a factor of $2$. That contradicts the assumption that $\frac{a}{b}$ was in reduced form.

Therefore, the assumption that $\sqrt{2}$ is rational must be false. Hence $\sqrt{2}$ is irrational. □

What to notice

This proof uses number properties and parity. The contradiction is not a random mistake; it is a logical conflict with the definition of a reduced fraction. This is a classic discrete mathematics argument because it uses integer reasoning, divisibility, and careful definitions.

Example 3: Proving an Integer Cannot Be Both Even and Odd

Let’s prove that no integer can be both even and odd.

Claim

There is no integer $n$ such that $n$ is both even and odd.

Proof by contradiction

Assume there exists an integer $n$ that is both even and odd.

If $n$ is even, then $n = 2k$ for some integer $k$.

If $n$ is odd, then $n = 2m + 1$ for some integer $m$.

So we would have

$2k = 2m + 1.$

The left side is even, but the right side is odd. That is impossible because an integer cannot be both even and odd.

So the assumption is false. Therefore, no integer is both even and odd. □

Lesson from this example

Sometimes the contradiction appears immediately from definitions. The proof is short, but it still follows the same pattern: assume the opposite, derive impossibility, conclude the original statement is true.

How Contradiction Fits with Other Proof Techniques

Contradiction is part of the larger family of proof methods in Proof Techniques I, along with direct proof and contrapositive proof.

Direct proof starts with known facts and definitions and moves straight to the conclusion.
Contrapositive proof proves a statement of the form $P \rightarrow Q$ by proving its logically equivalent contrapositive $\neg Q \rightarrow \neg P$.
Contradiction assumes the opposite of the desired conclusion and shows that the assumption leads to falsehood.

These methods are closely connected. In fact, proving $P \rightarrow Q$ by contradiction often means assuming $P \land \neg Q$ and deriving a contradiction. This is logically valid because if $P$ were true and $Q$ false led to impossibility, then $P \rightarrow Q$ must be true.

The main difference is the path of reasoning:

Direct proof builds the result forward.
Contrapositive flips the statement and proves an equivalent one.
Contradiction shows the negation cannot work.

students, knowing all three gives you flexibility. Some problems are best solved one way, while others are much easier using a different method. In discrete mathematics, choosing the right proof strategy is an important skill. ✅

Common Tips for Writing Contradiction Proofs

When writing a contradiction proof, keep these steps in mind:

State the claim clearly. Know exactly what you want to prove.
Assume the negation. Do not assume a weaker or different statement.
Use definitions carefully. Many contradictions come from parity, divisibility, sets, or inequality definitions.
Show each step logically. Every line should follow from the previous one.
Point out the contradiction. Explain why the result is impossible.
Conclude clearly. State that the original claim is true because the negation leads to a contradiction.

A common mistake is assuming something too broad or too narrow. Another mistake is failing to identify the contradiction explicitly. For example, if you derive $n < n$, that is a contradiction because no number is less than itself.

Conclusion

Proof by contradiction is a powerful and widely used method in discrete mathematics. It works by assuming the negation of the statement you want to prove and then showing that this assumption leads to an impossible result. The contradiction can appear as a conflict with definitions, arithmetic, logic, or a known theorem.

This technique is closely related to direct proof and contrapositive proof, and it is especially helpful when a statement is difficult to prove directly. Examples such as proving that $\sqrt{2}$ is irrational, showing there is no smallest positive rational number, or proving that no integer is both even and odd demonstrate how contradiction works in real mathematical reasoning. students, mastering this method will strengthen your ability to read, write, and analyze proofs across discrete mathematics. 🧩

Study Notes

Proof by contradiction starts by assuming the negation of the statement you want to prove.
A contradiction is a result that cannot be true, such as $P \land \neg P$ or $n < n$.
If the negation leads to impossibility, then the original statement must be true.
Contradiction is useful when direct proof is difficult or when the statement involves impossibility, divisibility, or extremes.
A correct contradiction proof must use the exact negation of the original statement.
Example: assuming $\sqrt{2}$ is rational leads to a conflict with the definition of a reduced fraction.
Example: assuming a smallest positive rational number exists leads to a smaller one, which is impossible.
Contradiction fits into Proof Techniques I alongside direct proof and contrapositive proof.
Direct proof moves forward from facts to conclusion.
Contrapositive proof proves an equivalent statement $\neg Q \rightarrow \neg P$ instead of $P \rightarrow Q$.
Contradiction proves a statement by showing the opposite cannot happen.