What is a Proof?

What is a Proof?

A proof is a sequence of statements, each justified by a definition, an axiom, or a previously established proposition, using only allowed logical rules. Every proof is a chain of deductive arguments. Proofs are of two main types:

• Direct Proof – starts directly from what is given in the proposition.
• Indirect Proof – proves an equivalent proposition instead of the original one.

---

Direct Proof

Begin with the given hypothesis and apply a chain of logical arguments — using axioms, definitions, and already proved theorems — to reach the conclusion.

(i) Straightforward Approach

A direct chain of arguments from the given assumption to the conclusion.

Example: Show that if $x^2 - 5x + 6 = 0$, then $x = 3$ or $x = 2$.

• Given $x^2 - 5x + 6 = 0$, factor: $(x - 3)(x - 2) = 0$.
• Using $ab = 0 \Rightarrow a = 0$ or $b = 0$ (for $a, b \in \mathbb{R}$): $x - 3 = 0$ or $x - 2 = 0$.
• Hence $x = 3$ or $x = 2$.

Symbolic form: starting with $p$, we deduce $p \Rightarrow r \Rightarrow s \Rightarrow \dots \Rightarrow q$, proving $p \Rightarrow q$.

Example: Prove $f : \mathbb{R} \to \mathbb{R}$ defined by $f(x) = 2x + 5$ is one-one.

• A function is one-one if $f(x_1) = f(x_2) \Rightarrow x_1 = x_2$.
• $2x_1 + 5 = 2x_2 + 5 \Rightarrow 2x_1 = 2x_2 \Rightarrow x_1 = x_2$. Hence the function is one-one.

(ii) Mathematical Induction

Based on the axiom: for a subset $S$ of $\mathbb{N}$, if $1 \in S$ and $k + 1 \in S$ whenever $k \in S$, then $S = \mathbb{N}$.

Principle of Mathematical Induction: if $S(n)$ is true for $n = 1$ (or some starting point $j$), and $S(k) \Rightarrow S(k+1)$ for all $k \geq j$, then $S(n)$ is true for all $n \geq j$.

Example: Show that if $A = \begin{bmatrix} \cos\theta & \sin\theta \\ -\sin\theta & \cos\theta \end{bmatrix}$, then $A^n = \begin{bmatrix} \cos n\theta & \sin n\theta \\ -\sin n\theta & \cos n\theta \end{bmatrix}$.

• Base case $P(1)$: $A^1 = \begin{bmatrix} \cos\theta & \sin\theta \\ -\sin\theta & \cos\theta \end{bmatrix}$ is true.
• Inductive step: assume $P(k)$: $A^k = \begin{bmatrix} \cos k\theta & \sin k\theta \\ -\sin k\theta & \cos k\theta \end{bmatrix}$. Then

• Multiplying and applying the angle-sum identities gives

so $P(k+1)$ is true. By induction, $P(n)$ is true for all $n \geq 1$.

(iii) Proof by Cases (Exhaustion)

When the hypothesis $p$ splits into cases $p = r \lor s \lor t$ (where $\lor$ means "OR"), prove each case leads to the conclusion $q$. If $r \Rightarrow q$, $s \Rightarrow q$, and $t \Rightarrow q$, then $(r \lor s \lor t) \Rightarrow q$, so $p \Rightarrow q$.

Example: Show that in any triangle $ABC$, $a = b \cos C + c \cos B$.

• Case 1 ($\angle C$ acute): $BD = c \cos B$ and $CD = b \cos C$, so $a = BD + CD = c \cos B + b \cos C$.
• Case 2 ($\angle C$ obtuse): $BD = c \cos B$ and $CD = -b \cos C$ (since $\cos(180^\circ - C) = -\cos C$), so $a = BD - CD = c \cos B + b \cos C$.
• Case 3 ($\angle C$ right angle): $a = c \cos B$ and $b \cos C = b \cos 90^\circ = 0$, so $a = b \cos C + c \cos B$.

All three cases give the same result, so the statement holds for any triangle.

---

Indirect Proof

Instead of proving $p \Rightarrow q$ directly, we prove an equivalent proposition.

(i) Proof by Contradiction (Reductio Ad Absurdum)

Assume the given statement is false; deriving a contradiction shows the assumption is wrong, so the original statement is true.

Example: Show that the set of all prime numbers is infinite.

• Assume the primes are finite: $P_1, P_2, P_3, \dots, P_k$. Consider $N = (P_1 P_2 P_3 \dots P_k) + 1$.
• If $N$ is prime, it is a prime not in the list. If $N$ is composite, its prime divisor cannot be any listed prime (each leaves remainder $1$).
• Both cases contradict the assumption, so the set of primes is infinite.

(ii) Proof Using Contrapositive

Instead of proving $p \Rightarrow q$, prove its contrapositive $\sim q \Rightarrow \sim p$ (formed by interchanging and negating hypothesis and conclusion).

Example: Prove $f(x) = 2x + 5$ is one-one using the contrapositive.

• Contrapositive: $x_1 \neq x_2 \Rightarrow f(x_1) \neq f(x_2)$. …