More ProofsDr. HolmesSeptember 4, 20091 Summary of Proof Strategies1.1 Basic Logical Conceptscontradiction: I’m introducing a symbol ⊥ for a sentence which is false,read “contradiction”.negation: If P is a sentence, ¬P means “It is not the case that P ”, “P isfalse”, “not P ”.conjunction: If P and Q are sentences, P ∧ Q means “P and Q”.disjunction: If P and Q are sentences, P ∨ Q means “P or Q (or both)”.This is the default meaning of “or” in mathematical English.implication: If P and Q are sentences, P → Q is read “if P then Q” or“P implies Q”. This is understood to be false only if P is true andQ is false: it is exactly equivalent to ¬(P ∧ ¬Q) or to ¬P ∨ Q. Thisis the default meaning of “if. . .then. . .” or “implies” in mathematicalEnglish.biconditional: If P and Q are sentences, P ↔ Q means “P if and only ifQ”, or “P implies Q and Q implies P ”. This is abbreviated “P iff Q00.universal quantifier: (∀x.P (x)) means “for all x, P (x)” and (∀x ∈ A.P (x))means “for all x in the set A, P (x)”.existential quantifier: (∃x.P (x)) means “for some x, P (x)” or “there ex-ists an x such that P (x), and (∀x ∈ A.P (x)) means “for some x in theset A, P (x)”, or “there exists an x in A such that P (x).11.2 Proving sentences of these formsIn this subsection we have techniques for proving statements of each of theselogical forms, and sample outlines of what such a proof (in a highly formalizedstyle) would look like.contradiction: To prove ⊥, prove A and prove ¬A (for some sentence A) [wecertainly hope that we cannot do this except under bad assumptions!]negation: To prove ¬A, assume A and prove ⊥ (which you can only do byproving some B and ¬B).Goal: ¬AAssume: AGoal: contradiction[proof of B][proof of ¬B]completing a contradiction: B might be any statement.conjunction: To prove P ∧ Q, prove P , then prove Q.Goal: P ∧ QGoal 1: P[proof of P ]Goal 2: Q[proof of Q]Notice that the single conjunction goal unpacks into two goals whicheach need to be proved separately.disjunction: To prove P ∨ Q, do one of four things (you do not need to domore than one!):Method 1: Assume ¬P (for the sake of argument) then prove Q; whendone with this proof of Q, one no longer can use the assumption¬P , which is local to that proof.Goal: P ∨ QAssume: ¬P2Goal: Q[proof of Q]Notice that the assumption ¬P and any conclusion proved using¬P (including the local conclusion Q) can only be used in theindented part of the proof.Method 2: Assume ¬Q (for the sake of argument) then prove P ; whendone with this proof of P , one no longer can use the assumption¬Q, as above.Goal: P ∨ QAssume: ¬QGoal: P[proof of P ]Notice that the assumption ¬Q and any conclusion proved using¬Q (including the local conclusion P ) can only be used in theindented part of the proof.Method 3: Notice that it is enough just to prove P .Goal: P ∨ QGoal: P[proof of P ]Method 4: Notice that it is enough just to prove Q.Goal: P ∨ QGoal: Q[proof of Q]implication: To prove P → Q, assume P (for the sake of argument), thenprove Q. The assumption P can only be used in this local proof of Q.Goal: P → QAssume: PGoal: Q[proof of Q]The assumption P and anything proved using it can only be used inthe indented part of the proof.3An alternative strategy (proof by contrapositive) is to assume ¬Q andthen prove ¬P .Goal: P → QAssume: ¬QGoal: ¬P[proof of ¬P ]biconditional: To prove P ↔ Q one needs a proof with two parts: in thefirst part one assumes P for the sake of argument then proves Q; in thesecond part one assumes Q for the sake of argument then proves P .Goal: P ↔ QPart 1: Assume: PGoal: Q[proof of Q]Part 2: Assume: QGoal: P[proof of P ]One or both of the embedded proofs of P → Q and Q → P could bereplaced with proofs by contrapositive.universal quantifier: To prove (∀x.P (x)), introduce an arbitrary object a(about which we may make no special assumptions; we should not haveever mentioned it before), and prove P (a). After the end of this proofwe should not refer to this a again.To prove (∀x ∈ A.P (x)), introduce an arbitrary object a (about whichwe may make no special assumptions; we should not have ever men-tioned it before), assume a ∈ A and prove P (a). After the end of thisproof we should not refer to this a again.existential quantifier: To prove (∃x.P (x)), find an object t such that youcan prove P (t).To prove (∃x ∈ A.P (x)), find an object t such that you can prove t ∈ Aand you can prove P (t).4proof by contradiction: To prove any statement A at all: assume ¬A anddeduce a contradiction.Goal: AAssume: ¬AGoal: contradiction[proof of B][proof of ¬B]where B can be any statement.1.3 Using theorems, assumptions or conclusions of theseformscontradiction: If you have assumed or concluded ⊥, you may assume orconclude any further conclusion A that you want (a false statementimplies anything).negation: If you have assumed or concluded ¬¬A, you may conclude A.The main use of a negative conclusion ¬A is to see if you can also proveA and thus prove a contradiction (⊥).Here is a proof fragment where a negative hyp ¬A is used in this way.¬AGoal: ¬BAssume: BGoal: contradictionGoal: A (for the sake of a contradiction)[proof of A](the point is that we now have a contradiction because¬A is already a conclusion above)conjunction: If you have assumed or concluded P ∧ Q, you may also con-clude P and you may also conclude Q.5disjunction: If you have assumed or concluded P ∨ Q and are trying toprove G, you can complete the proof using proof by cases: (case 1)assume P , then prove G; (case 2) assume Q, then prove G.Here is a bit of proof text:P ∨ QGoal: GCase 1: Assume: PGoal: G[proof of G]Case 2: Assume: QGoal: G[proof of G]implication: If you have assumed or concluded P → Q, and have alsoassumed or concluded P , you can further conclude Q (rule of modusponens).(1) P → Q(2) PQ, from (1) (2) by the rule of modus ponensIf you have assumed or concluded P → Q, and have also assumed orconcluded ¬Q, then you can further conclude ¬P . (modus tollens)(1) P → Q(2) ¬Q¬P , from (1) (2) by the rule of modus tollensIf you have just the assumption or conclusion P → Q and it is unclearwhat to do next, try proving P (because if you do you can furtherconclude Q), or proving ¬Q (because if you do you can further conclude¬P ).Here is a proof fragment:A → BGoal: G . . .6Goal: A (for the sake of