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\wedge \cdots \wedge 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

Let $P(n)$ be a predicate. To prove $P(n)$ is true for all $n\ge n_0$, we prove:

• Base case: Prove $P(n_0)$ is true. This is usually done directly.
• Inductive case: Prove $P(k)\Rightarrow P(k+1)$ for all $k\ge n_0$.

Within the inductive case, $P(k)$ is known as the inductive hypothesis.

Strong Induction

Strong induction expands the induction hypothesis. Let $P(n)$ be a predicate. To prove $P(n)$ is true for all $n\ge n_0$, we prove:

• Base case: Prove $P(n_0)$ is true. This is usually done directly.
• Inductive case: Assume $P(k)$ is true for all $n_0\le k<n$. Then prove $P(n)$ is true.

Bibliography

• “Constructive Proof,” in Wikipedia, April 4, 2024, https://en.wikipedia.org/w/index.php?title=Constructive_proof.
• Gries, David. The Science of Programming. Texts and Monographs in Computer Science. New York: Springer-Verlag, 1981.
• Oscar Levin, Discrete Mathematics: An Open Introduction, 3rd ed., n.d., https://discrete.openmathbooks.org/pdfs/dmoi3-tablet.pdf.
• Patrick Keef and David Guichard, “An Introduction to Higher Mathematics,” n.d.