Basic Mathematical Proofs (1.7-1.8)

[1.7] Basic Proof Techniques

What’s the difference between a mathematical proof & the formal proofs of section 1.6?

• Formal Proof: state and reference ever rule of inference and logical equivalence used.
• Mathematical Proof: don’t usually reference rules of inference, logical equivalences, or well-known proven facts… context!
• Rule of thumb: Justify any statement that is similar to the proposition being proven.

Definitions

• Lemma : A statement that can be proven for the purpose of using it in the proof of a theorem.
• Proposition : A statement that can be proven but is not considered important.
• Conjecture : A statement that is believed to be true, but cannot yet be proven.
• Axiom : A statement that is assumed to be true without proof.
• Theorem : An important statement that can be proven.
• Corollary : A statement that can be proven directly from a proven theorem.

Basic tips for writing Proofs

1. Write the proposition and relevant definitions using mathematical notation.
2. Choose a proof strategy. A direct proof is preferred when it’s straightforward. Finding the best proof strategy often requires trial and error.
3. Set up the proof - see proof templates
4. Hard part: write a mathematical arguement to complete the proof.
5. Finish by stating what you’ve proven.
6. No formula - takes practice & creativity

Basic Proof Templates

General strategies for proving a proposition, $P$

• Direct Proof

  • $\langle$ Prove P using axioms (Appendix 1), previously proven theorems/propositions/lemmas (w/ reference), logical equivalences, & rules of inference. $\rangle$

• Proof by Contradiction

  • Basis: $\neg P \implies F$ $\equiv$ $P \lor F$ $\equiv P$ (Table 7 Equivalence 1, double negation law, identity law)
  • Proof: Suppose $\neg P$. $\langle$ Find a contradiction. $\rangle$ Therefore, P.

Conditional Statements: Prove $p \implies q$

• Direct Proof

  • Proof: Assume p. $\langle$ Prove $\neg p$. $\rangle$ Therefore, $p \implies q$

• Proof by Contraposition

  • Basis: ($p \implies q$) $\equiv$ ($\neg q \implies \neg p$)
  • Proof: Assume $\neg q$. $\langle$ Prove $\neg p$ $\rangle$ Therefore, by contraposition, $p \implies q$

• Proof by Contradiction

  • Basis: $\neg$($p \implies q$) $\equiv$ ($p \land \neg q$)
  • Proof: Suppose $p \land \neg q$. $\langle$ Find a contradiction. $\rangle$ Therefore, $p \implies q$

• Disprove $p \implies q$

  • Basis: $p \implies q$
  • Proof: $p \implies q$

Biconditional Statements: Prove $p \Leftrightarrow q$

• Direct Proof

  • Basis: ($p \Leftrightarrow q$) $\equiv$ ($p \implies q$) $\land$ ($q \implies p$)
  • Proof:
    • ($\implies$) $\langle$ Prove $p \implies q$. $\rangle$
    • ($\gets$) $\langle$ Prove $q \implies p$. $\rangle$
      Therefore, $p \Leftrightarrow q$.

• Disprove $p \Leftrightarrow q

  • Basis: $\neg$($p \Leftrightarrow q$) $\equiv$ $\neg$[($p \land q$) $\lor$ ($\neg p \land \neg q$)] $\equiv$ $p \oplus q$.
  • Proof: $\langle$ Prove ($p \land \neg q$) or prove ($\neg p \land q$). $\rangle$ Therefore, $\neg$($p \Leftrightarrow q$)

Universal Quantifier: Prove $\forall x$ P(x), where the domain of P is D.

• Direct Proof

  • Basis: $P(x)$ for an arbitrary $x \implies \forall x$ P(x) (Universal generalization)
  • Proof: Let x be an element of D. $\langle$ Prove $P(x)$. $\rangle$ Therefore, $\forall x$ P(x).

• Proof by Contradiction

  • Basis: $\neg \forall x$ P(x) $\equiv$ $\exists x$ $\neg P(x)$ (De Morgan’s Law)
  • Proof: Suppose $\neg P(x)$ for some x in D. $\langle$ Find a contradiction. $\rangle$ Therefore, $\forall x$ P(x).

• Disprove $\forall x$ P(x)

  • Basis: $\neg \forall x$ P(x) $\equiv$ $\exists x$ $\neg P(x)$ (De Morgan’s Law)
  • Proof: Let x = $\langle$ write a counter-example, or element x of D such that $\neg P(x)$ $\rangle$. $\langle$ Prove $\neg P(x)$. $\rangle$ Therefore, $\neg \forall x$ P(x).

Existential Quantifier: Prove $\exists x$ P(x), where the domain of P is D.

• Direct Proof

  • Basis: P(x) for some element $x \implies \exists x$ P(x) (Existential generalization)
  • Proof: Let x = $\langle$ write an example, or element x of D such that $P(x)$ $\rangle$. $\langle$ Prove $P(x)$. $\rangle$ Therefore, $\exists x$ P(x).

• Proof by Contradiction

  • Basis: $\neg \exists x$ P(x) $\equiv$ $\forall x$ $\neg P(x)$ (De Morgan’s Law)
  • Proof: Suppose $\forall x$ $\neg P(x)$. $\langle$ Find a contradiction.i Therefore, $\exists x$ P(x).

• Disprove $\exists x$ P(x)

  • Basis: $\neg \exists x$ P(x) $\equiv$ $\forall x$ $\neg P(x)$ (De Morgan’s Law)
  • Proof: Let x be an element of D. $\langle$ Prove $\neg P(x)$. $\rangle$ Therefore, $\neg \exists x$ P(x).

Uniqueness Quantifier: Prove $\exists !x$ P(x), where the domain of P is D.

• Proof (direct)

  • Basis: $\exists !x$ P(x) $\equiv \exists x$ [$P(x) \land \forall y$ ($P(y) \implies y = x$)]
  • Proof: (existence) Let x=$\langle$ write an example, or element x of D such that P(x)$\rangle$. $\langle$ Prove P(x).$\rangle$ Therefore, $\exists x$ P(x). (uniqueness) Let y be an element of D. $\langle$ Prove $P(y) \implies y = x$ $\rangle$ Therefore, $\exists !x$ P(x).

• Disprove $\exists !x$ P(x)

  • Basis: $\neg \exists !x$ P(x) $\equiv$ $\neg \exists x$ P(x) $\lor$ $\exists x \exists y$ [$P(x) \land P(y) \land x 6= y$]
  • Proof: (Not existence) $\langle$ Prove $\neg \exists x$ P(x). $\rangle$; OR (Not uniqueness) Let x = $\langle$ write an example of x such that P(x).$\rangle$ Let y = $\langle$ write an example of y such that P(y) and y 6= x.$\rangle$ $\langle$ Prove $P(x) \land P(y)$. $\rangle$ Therefore, $\neg \exists !x$ P(x).