Table of Contents

Proof techniques we’ve learned so far:

1 Apply Equivalence Rules

See also MCS 3.3 and MCS 3.4.2, our list of equivalences, and our guide to direct proof.

In a small step proof, write an equivalent expression and cite the rule used to reach it. If several rules are needed, write them out one by one.

The following uses a note per line to show how it is equivalent to the preceding line

1	A \lor (B \lor C)
2	(A \lor B) \lor C	Associative property of \lor
3	(B \lor A) \lor C	Commutative property of \lor
4	B \lor (A \lor C)	Associative property of \lor
5	(\lnot (\lnot B)) \lor (A \lor C)	Double negation
6	(\lnot B) \rightarrow (A \lor C)	Disjunction to implication

In a prose proof, write the original and the new expression, separated by can be re-written as or is equivalent to. Only include intermediate steps or identified proof rules if you believe your audience would take more than a few minutes to figure them out themselves. Common shortcut phrases for guiding through steps include

Rearranging: Utilizing the associative, commutative, and distributive properties of operators
Simplifying: Removing double negation and the ones and zeros effects of tautologies and contradictions

This is the same example as the previous one, but written in prose style instead.

A \lor (B \lor C) can be re-written as (\lnot \lnot B) \lor (A \lor C), which is equivalent to (\lnot B) \rightarrow A \lor C by the equivalence of implication and disjuction.

2 Case Analysis

See also MCS 1.7, ∀x 17.5, and our proof of one of De Morgan’s laws

State a disjunctive tautology. For a simple tautology like P \lor \lnot P, stating it is enough; for more complicated tautologies, you may need to add a sub-proof or lemma¹ that it is tautological.
Then proceed to consider several cases: one for each term of the disjunctive tautology, in each case assuming that that clause is true.
After completing all of the cases, the full proof is also completed: we may not know which case’s assumption is true, but because the disjunction is a tautology, we know at least one of them must be.

This is a full proof of one of our known equivalences

P \rightarrow Q \equiv \lnot P \lor Q

Either P is true or P is false.

Case 1: P is true

The expression P \rightarrow Q in this case is equivalent to \top \rightarrow Q, which can be simplified to Q.

The expression \lnot P \lor Q in this case is equivalent to \bot \lor Q, which can be simplified to Q.

Since the two are equivalent to the same thing, they are equivalent to each other.

Case 2: P is false

The expression P \rightarrow Q in this case is equivalent to \bot \rightarrow Q, which can be simplified to \top.

The expression \lnot P \lor Q in this case is equivalent to \top \lor Q, which can be simplified to \top.

Since the two are equivalent to the same thing, they are equivalent to each other.

Since P \rightarrow Q \equiv \lnot P \lor Q is true in both cases, it is true in general.

Case analysis in small-step proofs involves embedded sub-proofs, as is described in ∀x 17.5 and used in ∀x 17.1 and ∀x 19.6.

3 Apply Entailment

See also our list of entailments.

Applying entailment is very much like applying equivalence rule, except it only needs to work in one direction. Because A \equiv B implies A \vDash B, you can use equivalence rules in a proof that applies entailment.

There are many more entailments (sometimes called proof rules or inference rules) than there are equivalence rules, so using them can make proof construction much easier than limiting yourself to equivalences.

A proof that only uses proof rules is sometimes called a direct proof.

4 Proof by Contradiction

Assume the negation of what you want to prove.
Use other proof techniques to derive \bot.
State because assuming \lnot A led to a contradiction, A must be true or the equivalent in other words.

There is no largest real number.

Assume there is a largest real number. Call that largest real number x; because it is the largest, we know that \tag{1} \forall y \in \mathbb R \;.\; y \le x

Consider the number x+1. Because x and 1 are both real numbers and the reals are closed over addition, x+1 \in \mathbb R. Thus, we can instantiate (1) with y = x+1 to get x+1 \le x. But clearly x+1 > x, which is a contradiction.

Because assuming there is a largest real number led to a contradiction, there must be no largest real number.

5 Proof by Induction

Proof by induction, in its purest form, only works for theorems of the form \boxed{\forall n \in \mathbb N \;.\; P(n)} where P is a predicate. However, many other proofs can be reduced to that form.

State you are using induction.
Identify one or more base cases, which are P(0) and (if needed) P(1), P(2), etc.; prove each using other proof techniques.
Add an inductive step of the form assume P(n) and then prove P(n+1); if needed, you can assume \boxed{\forall i \in \big\{ i \;\big|\; i \in \mathbb N \land i \le n \} \;.\; P(i)} instead (called strong induction) if needed.
State that by the principle of induction, the theorem holds for all n \in \mathbb N.

\mathbb N \subseteq \mathbb R

Note that by the definition of subsets, this is equivalent to proving \boxed{\forall n \in \mathbb N \;.\; n \in \mathbb R}, so we’ll use P(n) = n \in \mathbb R as our predicate.

We proceed by induction.

Base case: 0 \in \mathbb R by definition.
Inductive case: Assume n \in \mathbb N and n \in \mathbb R. Consider x = n+1; because 1 \in \mathbb R and the reals are closed under addition, x \in \mathbb R.

By the principle of induction, it follows that \forall n \in \mathbb N \;.\; n \in \mathbb R. By the definition of subsets, that means \mathbb N \subseteq \mathbb R.

Induction is used so often that the template is often applied with fairly dramatic modifications, possibly even having multiple inductive steps, without explicitly noting those modifications.

If a string is created by starting with a and optionally replacing an a with ab or a b with aa, as many times as you want, the result will always have an odd number of as.

It is also true that any string consisting of an odd number of as, each followed by any number of bs, can be created with this process, but let’s start with this easier odd-number proof first.

We proceed by induction.

Base case

a has one a, which is an odd number.

Inductive case

Assume a string s has an odd number of as. Consider the a string t created in one step from s.

Case a to ab: Suppose t was created by replacing one a in s with ab. t has the same number of as as s, so by our assumption t has an odd number of as.
Case b to aa: Suppose t was created by replacing one b in s with aa. t has exactly two more as than s, and 2 + an odd number is still odd, so by our assumption t has an odd number of as.

Since t has an odd number of as in each case, it has an odd numebr of as in general.

By the principle of induction, it follows that all strings created using this process have an odd number of as.

Implicitly, the above proof used induction on the number of steps used to create the string, but that was never identified in the proof itself.

a lemma is a helper proof made before the main proof it will be used inside of↩︎