Proof

• a valid argument that establishes the truth of a statement

• Informal (shorter) proofs are generally used:

  • More than one rule of inference often used in a step
  • Steps may be skipped
  • Rules of inference may not be explicitly stated
  • Easier to understand but also easier to introduce errors

Theorem

• a statement that can be shown to be true using:

  • definitions
  • other theorems
  • axioms
  • rules of inference

• a “helping” theorem needed to prove the “main” theorem

• a result that follows directly from a theorem

• less important theorems

• • A statement being proposed to be true
    • Once a proof is found, the conjecture becomes a theorem
    • It may turn out to be false, though

Forms of theorems

• Many theorems assert that a property holds for all elements in a domain
  • The universal quantifier is often omitted
• Many theorems have the form: $(*) \ \ \ \forall x (P(x) \implies Q(x))$
  • If for $c$, an arbitrary element in the domain, $P(c) \implies Q(c)$, then $(*)$ follows by universal generalization
  • So, we need to prove $p \implies q$… how do we do that?

Proving conditional statements: $p \implies q$

• No work needed if:
  • $q$ is true (trivial proof)
  • $p$ is false (vacuous proof)
• Otherwise, a proof needs to be constructed. Two options:
  • Direct proof: Assume $p$ is true; show that $q$ must be true as a result
  • Proof by contraposition (indirect proof): Assume $q$ is false; show that $p$ is false as well
    • This is a direct proof of the contraposition. This is valid because the contrapositive is logically equivalent to the original statement

References