Chapter 7 — Appendix 1: Proofs in Mathematics

A proof is a sequence of statements where each statement is justified by a definition, axiom, or a proposition previously established by deduction using allowed logical rules — forming a chain of deductive arguments with premises and conclusions.

Direct proof and indirect proof. A direct proof starts from what is given in the proposition; an indirect proof establishes the result by proving an equivalent proposition.

The straight forward approach (step-by-step chain of implications from hypothesis to conclusion), mathematical induction (base case for n=1 plus inductive step from n=k to n=k+1), and proof by cases or exhaustion (splitting the hypothesis into mutually exhaustive sub-cases and proving each implies the conclusion).

Mathematical induction is a deductive strategy for proving propositions about natural numbers. It relies on the axiom: for a subset S of ℕ, if 1∈S and k+1∈S whenever k∈S, then S = ℕ. A proof shows the base case S(1) is true, then shows S(k) true implies S(k+1) true.

An indirect method where you assume the given statement is false, then use logical rules to arrive at a conclusion that contradicts the assumption. The contradiction shows the assumption was wrong, proving the original statement is true. For example, assuming the set of all prime numbers is finite leads to a contradiction, so the set must be infinite.

The contrapositive of p⇒q is ~q⇒~p, formed by interchanging the hypothesis and conclusion and negating both. Since the contrapositive is logically equivalent to the original conditional, proving ~q⇒~p is sufficient to prove p⇒q.

A counterexample is a specific instance that shows a general statement is false. Because disproving a proposition requires only one failure case, a single counterexample is enough. For instance, φ(x)=|x| is continuous everywhere but not differentiable at x=0, which disproves the statement 'every continuous function is differentiable'.

When the hypothesis p can be split into mutually exhaustive sub-cases r, s, t so that p = r∨s∨t, it suffices to prove r⇒q, s⇒q, and t⇒q separately. Together they cover all possibilities and so p⇒q is established.

Starting from the given hypothesis p, each step deduces a new statement using axioms, definitions, or previously proved theorems, forming the chain p⇒r⇒s⇒…⇒q until the conclusion q is reached.

Yes — the PDF is available free with no sign-up required.