Proof strategies
To prove a goal of the form $ P \rightarrow Q:
1. Assume P is true and then prove Q.
2. Assume Q is false and prove that P is false.
To prove a goal of the form $ \lnot P:
1. If possible, reexpress the goal in some other form and then use one of the proof strategies for this other goal form.
2. Assume P is true and try to reach a contradiction. Once you have reached a contradiction, you can conclude that P must be false.
To use a given of the form $ P \rightarrow Q:
If you are also given P, or if you can prove that P is true, then you can use this given to conclude that Q is true.
To prove a goal of the form $ \forall x P(x):
Let x stand for an arbitrary object and prove P(x). The letter x must be a new variable in the proof. If x is already being used in the proof to stand for something, then you must choose an unused variable, say y, to stand for the arbitrary object.
To prove a goal of the form $ \exists x P(x):
Try to find a value of x for which you think P(x) will be true. Then start your proof with “Let x = (the value you decided on)” and proceed to prove P(x) for this value of x.
To use a given of the form $ \exists x P(x):
Introduce a new variable x0 into the proof to stand for an object for which P(x0) is true. This means that you can now assume that P(x0) is true. This rule of inference is called existential instantiation.
To use a given of the form $ \forall x P(x):
You can plug in any value, say a, for x and use this given to conclude that P(a) is true. This rule of inference is called universal instantiation.
To prove a goal of the form $ P \land Q:
Prove P and Q separately.
To use a given of the form $ P \land Q:
Treat this given as two separate givens: P, and Q.
To prove a goal of the form $ P \leftrightarrow Q:
Prove$ P \rightarrow Q and $ Q \rightarrow Pseparately.
To use a given of the form $ P \leftrightarrow Q:
Treat this as two separate givens: $ P \rightarrow Q and $ Q \rightarrow P.
To use a given of the form $ P \lor Q:
1. Break your proof into cases. For case 1, assume that P is true and use this assumption to prove the goal. For case 2, assume Q is true and give another proof of the goal.
2. If you are also given ¬P, or you can prove that P is false, then you can use this given to conclude that Q is true. Similarly, if you are given ¬Q or can prove that Q is false, then you can conclude that P is true.
To prove a goal of the form $ P \lor Q:
1. Break your proof into cases. In each case, either prove P or prove Q.
2. If P is true, then clearly the goal P ∨ Q is true, so you only need to worry about the case in which P is false. You can complete the proof in this case by proving that Q is true.
$ P \lor Q \leftrightarrow \lnot P \rightarrow Q
$ P \lor Q \leftrightarrow \lnot Q \rightarrow P
To prove a goal of the form $ \exists !x P(x):
$ \exists !x P(x)
$ \leftrightarrow \exists x P(x) \land \forall y \forall z ((P(y) \land P(z)) \rightarrow y = z)
$ \leftrightarrow \exists x ( P(x) \land \forall y ( P(y) \rightarrow y = x ))
1. Prove existance and uniqueness by$ \exists x P(x) and $ \forall y \forall z ((P(y) \land P(z)) \rightarrow y = z).
2. Prove $ \exists x ( P(x) \land \forall y ( P(y) \rightarrow y = x ))
To prove a goal of the form$ \forall n \in \mathbb{N} P(n):
First prove P(0), and then prove $ \forall n \in \mathbb{N} (P(n) \rightarrow P(n + 1) ) .
The first of these steps is called the base case and the second the induction step.