πŸͺ΄ Notes

Methods of Proof

3 min read

Course: CSCI 1900

Why?

  • Verification of truth
  • Remove ambiguity
  • Build more knowledge (such as new theorems)
  • Problem solving

Modus Ponens (Law of Detachment)

  • Fundamental rule of logic
  • If π‘β†’π‘ž is true and 𝑝 is true, then π‘ž must be true
    • If a number is even then it is divisible by 2 β†’ 4 is even so therefore it must be divisible by 2

QED (Quod Erat Demonstrandum)

  • β€œWhich was to be demonstrated”
  • Written at the end of a proof to conclude
  • Also indicated with ∎ or β–‘

Proof by Definition

  • Definition-based proofs establish truth by referring to a mathematical definition
  • Example β†’ prove that 3 is an odd number
    • Odd definition β†’ a number of the form 2π‘˜+1,π‘˜βˆˆβ„€
    • Since 3=2(1)+1, 3 is odd. β–‘

Direct Proof

  • Starts from known facts, then uses logic to arrive at a conclusion
  • Example β†’ prove that the sum of two even numbers is an even number
    • Even definition β†’ a number of the form 2π‘˜,π‘˜βˆˆβ„€
    • Let π‘₯=2π‘š and 𝑦=2𝑛, where π‘›βˆˆβ„€
    • π‘₯+𝑦=2π‘š+2𝑛=2(π‘š+𝑛)≑2π‘˜
    • ∴2(π‘š+𝑛) is even. β–‘

Proof by Contrapositive

  • Instead of proving π‘β†’π‘ž, we prove Β¬π‘žβ†’Β¬π‘
  • Example β†’ prove that if 𝑛2 is odd, then 𝑛 is odd.
    • Contrapositive β†’ if 𝑛 is even, then 𝑛2 is even.
    • Let 𝑛=2π‘˜ where π‘˜ is an integer
    • Then 𝑛2=(2π‘˜)2=4π‘˜2, which is even
    • Since contrapositive is true, the original statement is true. β–‘

Proof by Contradiction

  • We assume the opposite of what we want to prove and derive a contradiction
  • Example β†’ prove that there are infinitely many prime numbers (Euclid’s theorem)
    • Assumption (negation) β†’ there are a finite number of primes
    • Let those primes be 𝑝1,𝑝2,𝑝3,…,𝑝𝑛
    • Define a new number 𝑃=𝑝1𝑝2𝑝3…𝑝𝑛+1
    • ∴ P must either by prime itself or be divisible by a β€œnew prime”
    • This contradicts our assumption that we had listed all primes
    • ∴ There are infinitely many primes. β–‘

Pigeonhole Principle

  • If more objects are placed into fewer containers, then at least one container must contain multiple objects.
  • Example β†’ prove that in a group of 367 people, then at least 2 share a birthday.
    • There are only 366 possible birthdays and 367>366
    • ∴ By the pigeonhole principle, at least 2 people share a birthday. β–‘

Proof by Counterexample

  • To disprove a statement, provide one counterexample.
  • Example β†’ disprove that all prime numbers are odd
    • Counterexample β†’ 2 is a prime number β–‘

Proof by Induction

  • Induction β†’ used to prove statements that apply to all β„•
    • Base case β†’ prove statement for the smallest 𝑛 (typically 𝑛=1)
    • Inductive hypothesis β†’ assume statement is true for some arbitrary π‘˜, 𝑛=π‘˜
    • Inductive step β†’ prove that if statement holds for 𝑛=π‘˜, then it also holds for 𝑛=π‘˜+1
  • Example β†’ the sum of the first 𝑛 natural numbers is 1+2+3+…+4=𝑛(𝑛+1)2
    • Base case (𝑛=1) β†’ 1=1(1+1)2=1(2)2=22=1
    • Inductive hypothesis β†’ 1+2+3+…+π‘˜=π‘˜(π‘˜+1)2
    • Inductive step β†’ 1+2+3+…+π‘˜+(π‘˜+1)=π‘˜(π‘˜+1)2+(π‘˜+1)
      • Factor π‘˜+1 out β†’ π‘˜(π‘˜+1)+2(π‘˜+1)2=(π‘˜+1)(π‘˜+2)2β‰‘π‘˜(π‘˜+1)2β–‘

Graph View