Negation and Proof by Contradiction

Negation

The negation of a statement $P$, written $\neg P$, is true when $P$ is false and false when $P$ is true.

Truth Table

$P$	$\neg P$
T	F
F	T

Double Negation

$\neg(\neg P) \equiv P$

Negation of Compound Statements

Negation of Conjunction and Disjunction

$\neg(P \land Q) \equiv \neg P \lor \neg Q$ $\neg(P \lor Q) \equiv \neg P \land \neg Q$

Negation of Implication

$\neg(P \Rightarrow Q) \equiv P \land \neg Q$

This is because $P \Rightarrow Q \equiv \neg P \lor Q$, so:

$\neg(P \Rightarrow Q) \equiv \neg(\neg P \lor Q) \equiv P \land \neg Q$

Negation of Quantifiers

$\neg(\forall x. P(x)) \equiv \exists x. \neg P(x)$ $\neg(\exists x. P(x)) \equiv \forall x. \neg P(x)$

Negation of Bi-implication

$\neg(P \Leftrightarrow Q) \equiv (P \land \neg Q) \lor (\neg P \land Q)$

The negation says “exactly one of $P$, $Q$ holds.”

Proof by Contradiction

The Principle

To prove $P$ by contradiction:

1. Assume $\neg P$
2. Derive a contradiction (e.g., $Q \land \neg Q$ for some statement $Q$)
3. Conclude $P$ must be true

This is also called reductio ad absurdum.

Logical Justification

From $\neg P \Rightarrow \text{False}$, we conclude $P$.

Since $\neg P \Rightarrow \text{False}$ is equivalent to $\neg(\neg P) \lor \text{False} \equiv P \lor \text{False} \equiv P$.

Examinable Proof: Irrationality of $\sqrt{2}$

Theorem: $\sqrt{2}$ is irrational.

Proof by contradiction:

Suppose $\sqrt{2}$ is rational. Then $\sqrt{2} = \frac{p}{q}$ for integers $p, q$ with $\gcd(p, q) = 1$ (the fraction is in lowest terms).

Squaring: $2 = \frac{p^2}{q^2}$, so $p^2 = 2q^2$.

This means $p^2$ is even. Since $n$ even implies $n^2$ even, and $n^2$ even implies $n$ even (contrapositive), we have $p$ is even.

Write $p = 2k$ for some integer $k$.

Substituting: $4k^2 = 2q^2$, so $q^2 = 2k^2$.

Thus $q^2$ is even, so $q$ is even.

But $p$ and $q$ are both even, contradicting $\gcd(p, q) = 1$.

Therefore $\sqrt{2}$ is irrational.

Examinable Proof: Infinitude of Primes

Theorem: There are infinitely many prime numbers.

Proof by contradiction (Euclid):

Suppose there are finitely many primes: $p_1, p_2, \ldots, p_n$.

Let $N = p_1 \cdot p_2 \cdot \cdots \cdot p_n + 1$.

Since $N > 1$, the Fundamental Theorem of Arithmetic says $N$ has a prime divisor $p$.

If $p = p_i$ for some $i$, then $p \mid p_1 \cdot p_2 \cdot \cdots \cdot p_n$ and $p \mid N$.

This implies $p \mid (N - p_1 \cdot p_2 \cdot \cdots \cdot p_n) = 1$.

But no prime divides 1. Contradiction.

Therefore $p$ is not in our list, so there is a prime not among $p_1, \ldots, p_n$.

This contradicts the assumption of finitely many primes.

Therefore there are infinitely many primes.

When to Use Contradiction

Contradiction is useful when:

1. The negation gives better structure (e.g., proving irrationals)
2. Direct proof seems impossible or awkward
3. The statement asserts non-existence or impossibility

Example: Negation Simplifies Structure

Statement: There are no integers $a, b$ such that $a^2 = 2b^2$.

If we negate: “There exist integers $a, b$ such that $a^2 = 2b^2$.”

This gives us something to work with algebraically.

Contradiction vs Contrapositive

If you find yourself assuming $\neg P$ and deriving $\neg Q$, you might instead prove the contrapositive $Q \Rightarrow P$ directly.

Both are valid; contrapositive is often clearer when applicable.

Example

Statement: If $n^2$ is even, then $n$ is even.

• Contrapositive proof: If $n$ is odd, then $n^2$ is odd. (Direct)
• Contradiction proof: Suppose $n^2$ is even and $n$ is odd. Then $n^2$ is odd. Contradiction.

Both work; contrapositive is simpler here.

Common Pitfalls

Forgetting to Negate Assumptions

Trap: In proof by contradiction, you assume $\neg P$. Some students assume $P$ instead.

Circular Reasoning

Trap: Assuming what you want to prove within the proof.

This defeats the purpose of proof by contradiction.

Overusing Contradiction

Trap: Using contradiction when a direct proof is simpler.

Direct proofs are often clearer. Use contradiction when necessary.

---

Summary

• $\neg(P \land Q) \equiv \neg P \lor \neg Q$ and $\neg(P \lor Q) \equiv \neg P \land \neg Q$
• $\neg(P \Rightarrow Q) \equiv P \land \neg Q$
• Proof by contradiction: assume $\neg P$, derive $\text{False}$
• Examinable proofs: irrationality of $\sqrt{2}$, infinitude of primes