Proof Strategies

Meta-strategies (i.e., strategies for using the strategies):

1. Determine the logical form of the theorem to be proved.
   Then use an appropriate strategy.

2. If more than one strategy is applicable,
   then try each of them until you find one that works.

Specific Strategies:

If the logical form is:	Then a strategy is:
p	Indirect Proof: Assume/suppose/make believe that ¬p & then try to derive a contradiction; i.e., try to find r such that (r ∧ ¬r)
PRED(c), where PRED(c) =def DEF(c)	Try to prove DEF(c) In general, wherever possible in a proof, try to replace predicates by their definitions
¬P(x), where P(x) is a compound proposition	Try to prove Q(x), where Q(x) ≡ ¬P(x), but the "¬" has been moved to the right by DeMorgan
(p → q), where p is a contradiction	"Vacuous" proof: (p → q) must be true!
(p → q), where q is a tautology	"Trivial" proof: (p → q) must be true!
(p → q)	Direct Proof: Assume p & then try to show q Hint: If p =def DEF(x) then suppose DEF(x) & try to show q
(p → q)	Indirect Proofs: Proof by Contraposition: Try to show (¬q → ¬p) (by using one of the other strategies for "→") Proof by Contradiction: Assume p Assume ¬q & then try to find a contradiction; i.e., try to find a proposition r such that (r ∧ ¬r)
(p1 ∨ p2) → q To make this simpler to understand, I just show the case for 2 propositions; see text for more details.	Proof by Cases: Try to show each of the following: (p1 → q) and (p2 → q) (by using any of the above strategies for "→")
(p ↔ q)	Try to show both (p → q) and (q → p) (by using any of the above strategies for "→")
(p1 ↔ p2 ↔ p3) To make this simpler to understand, I just show the case for 3 propositions; see text for more details.	Try to show all of the following: (p1 → p2) and (p2 → p3) and (p3 → p1) (by using any of the above strategies for "→")
∀x[P(x) → Q(x)]	Try to show [P(c) → Q(c)], for arbitrary c (by using one of the strategies for "→"; then apply UG)
∃xP(x)	Constructive Proof: Find c such that P(c) Non-constructive Proof by Contradiction: Assume ¬∃xP(x) & then try to find r such that (r ∧ ¬r)
¬∀xP(x)	Find a counterexample; i.e., try to show ∃x¬P(x)