Proofs

Overview

A direct proof is a sequence of statements, either givens or deductions of previous statements, whose last statement is the conclusion to be proved.

An indirect proof works by assuming the denial of the desired conclusion leads to a contradiction in some way.

Conditional Proofs

A conditional proof is a proof method used to prove a conditional statement, i.e. statements of form: $P_{1} \land \dots \land P_{n} \Rightarrow Q$ Note we can assume all the hypotheses are true since if one were false, the implication holds regardless. Direct proofs of the above form are called conditional proofs (CP).

Proof by Contraposition

Since a conditional and its contrapositive are logically equivalent, we can instead prove the negation of the conclusion leads to the negation of our hypotheses.

Proof by Contradiction

To prove a proposition $P$ by contradiction, we assume $\neg P$ and derive a statement known to be false. Since mathematics is (in most cases) consistent, $P$ must be true.

Existence Proofs

An existence proof is a proof method used to prove an existential statement, i.e. statements of form: $\exists x, P (x)$

An existence proof is said to be constructive if it demonstrates the existence of an object by creating (or providing a method for creating) the object. Otherwise it is said to be non-constructive.

Induction

Weak Induction

Let $P (n)$ be a predicate depending on a number $n \in N$ . Assume that

Base case: $P (n_{0})$ is true for some $n_{0} \geq 0$ , and
Inductive case: for all $k \geq n_{0}$ , $P (k) \Rightarrow P (k + 1)$ .

Then $P (n)$ is true for all $n \geq n_{0}$ .

Within the inductive case, $P (k)$ is known as the inductive hypothesis. The formal justification of proof by induction is intimately tied to the idea of inductive sets.

Strong Induction