Proof by Contradiction

Definition

Proof by contradiction is a method of proving a statement by assuming its negation is true and then logically deriving a contradiction, such as:

• a statement and its negation both being true,
• a result that violates a known fact,
• an impossible condition like $1 = 0$,
• a contradiction with an assumption already accepted as true.

If the assumption that “the statement is false” leads to contradiction, then the original statement must be true.

Formally, to prove a proposition $P$:

1. Assume $\neg P$ is true.
2. Use logical reasoning, definitions, axioms, and known results.
3. Derive a contradiction $C$, where $C$ is impossible or false.
4. Conclude that $\neg P$ cannot be true, so $P$ must be true.

A contradiction is usually represented as:

• $Q \land \neg Q$, meaning both a statement and its negation hold,
• or an impossibility like $0 > 1$,
• or a violation of an established theorem or axiom.

---

Main Content

1. Logical Basis of Proof by Contradiction

• The foundation of this technique lies in classical logic and the law of non-contradiction, which states that a statement and its negation cannot both be true at the same time in the same context.
• If assuming the negation of a statement leads to an impossible conclusion, then the original statement must be accepted as true because the false assumption cannot be consistently maintained.

For example, suppose we want to prove a statement $P$. We assume $\neg P$. If this assumption gives us:

• a direct violation of a definition,
• an invalid arithmetic statement,
• or a contradiction with a theorem already proven,

then the assumption is rejected.

A simple logical structure is:

• Assume $\neg P$
• Derive $R$
• Derive $\neg R$
• Therefore, contradiction exists
• Hence, $P$ is true

This style is very useful when:

• the statement is negative in form,
• the direct proof is hard to construct,
• or the contradiction arises naturally from definitions.

Example: Proving that $\sqrt{2}$ is irrational

Assume $\sqrt{2}$ is rational. Then: $$\sqrt{2} = \frac{a}{b}$$ where $a$ and $b$ are integers with no common factor.

Squaring both sides: $$2 = \frac{a^2}{b^2}$$ $$a^2 = 2b^2$$

So $a^2$ is even, which implies $a$ is even. Let $a = 2k$. Then: $$(2k)^2 = 2b^2$$ $$4k^2 = 2b^2$$ $$2k^2 = b^2$$

So $b^2$ is even, hence $b$ is even. Now both $a$ and $b$ are even, which contradicts the assumption that $a/b$ was in lowest terms.

Therefore, $\sqrt{2}$ is irrational.

---

2. Structure of a Contradiction Proof

• A contradiction proof must be organized carefully so that each step follows from the previous one using valid logic, definitions, and mathematical properties.
• The proof usually begins with the negation of the conclusion and ends when an impossible statement is reached.

A standard structure is:

1. State the theorem clearly.
2. Assume the opposite of the theorem.
3. Use definitions, properties, and intermediate results.
4. Reach a contradiction.
5. Conclude that the original theorem is true.

There are different kinds of contradictions:

Direct contradiction

• : obtain both $P$ and $\neg P$.

Numerical contradiction

• : obtain something impossible like $0 = 1$.

Theoretical contradiction

• : violate a proven theorem or property.

Definition-based contradiction

• : conflict with the definition of a term.

This technique is especially common in:

• set theory, when proving equality or inequality of sets,
• relation theory, when proving a relation is not possible,
• function theory, when proving uniqueness or impossibility,
• number theory, when proving irrationality or divisibility properties.

Example: Proving there is no smallest positive rational number

Assume there is a smallest positive rational number $r$.
Then $\frac{r}{2}$ is also a positive rational number, and: $$0 < \frac{r}{2} < r$$ This contradicts the assumption that $r$ is the smallest positive rational number.

Therefore, no smallest positive rational number exists.

This example shows how contradiction can prove the nonexistence of an object.

---

3. Applications in Set Theory, Relations, and Functions

• In set theory, contradiction is often used to prove set equalities, subset relations, and impossibility of certain set properties. For example, to show $A \subseteq B$, one may assume there exists an element in $A$ not in $B$ and then derive a contradiction with the given conditions.
• In relations and functions, contradiction helps prove properties like injectivity, surjectivity, uniqueness, existence, and nonexistence. It is also useful when proving that a relation cannot satisfy both symmetry and antisymmetry unless it is very restricted.

Set theory example

To prove: $$A \cap B \subseteq A$$ Assume there exists an element $x \in A \cap B$ but $x \notin A$.
Since $x \in A \cap B$, by definition $x \in A$ and $x \in B$.
This contradicts $x \notin A$.
Hence, $A \cap B \subseteq A$.

Function example

To prove a function $f(x)=2x+1$ is injective, we often use contradiction or direct reasoning. Assume: $$f(a)=f(b)$$ Then: $$2a+1 = 2b+1$$ $$2a = 2b$$ $$a=b$$ If we had assumed $a \ne b$, this would contradict the equality. Therefore, the function is injective.

Relation example

Suppose a relation is claimed to be both symmetric and antisymmetric in a set with more than one element. If $aRb$ and $bRa$, symmetry gives both directions, while antisymmetry forces $a=b$. If $a \ne b$, this is a contradiction. Thus, such a relation is impossible under those conditions.

---

Working / Process

1. Assume the negation of the statement

• Begin by writing the opposite of what you want to prove.
• If the statement is “$P$ is true,” assume “$P$ is false.”
• If the statement is an inequality, assume the reverse inequality.

2. Apply definitions, properties, and logical deductions

• Use algebra, set identities, relation properties, function rules, or known theorems.
• Keep every step valid and clearly justified.
• Move toward an outcome that cannot be true.

3. Reach a contradiction and conclude

• Identify the impossible result clearly.
• State why it is impossible.
• Reject the assumption and conclude that the original statement must be true.

A useful format for writing:

• Assume the opposite.
• Work through consequences.
• Obtain contradiction.
• Therefore, the original statement holds.

Example flow

Prove: “There is no rational number whose square is 2.”

1. Assume there exists a rational number $\frac{a}{b}$ such that $\left(\frac{a}{b}\right)^2 = 2$.
2. Simplify to get $a^2 = 2b^2$.
3. Show both $a$ and $b$ must be even.
4. This contradicts the assumption that $\frac{a}{b}$ is in lowest terms.
5. Therefore, no such rational number exists.

---

Advantages / Applications

• It is very useful for proving statements that are difficult to establish directly, especially when the negation is easier to work with.
• It is widely used in proving irrationality, uniqueness, impossibility, and nonexistence results in algebra, number theory, set theory, relations, and functions.
• It strengthens logical thinking because it forces careful reasoning, precise use of definitions, and recognition of impossible conclusions.

---

Summary

• Proof by contradiction proves a statement by showing its negation leads to an impossible result.
• It is a key theorem proving technique in logic, set theory, relations, and functions.
• The method is especially useful for irrationality proofs, nonexistence proofs, and uniqueness arguments.
• Important terms to remember: assumption, negation, contradiction, irrational number, subset, injective function, antisymmetric relation