Proofs (How to prove)

Proving Theorems

Trivial Proof (자명한 증명)

• q = True
• p→q = True
• “If it is raining the 1=1.”
• 결론이 항시 True임을 증명

Vacuous Proof (무의미한 증명)

• p = False
• p→q = True
• “If n is both odd and even, then 2 + 2 = 5”
• 가정이 False임을 증명

Direct Proof (직접 증명)

• p가 True라고 가정할 때 q가 True임을 증명
• using rules of inference, axioms, logical equivalences
• Ex1)
  “If n is an odd integer, the n^2 is odd”
  Assume that n is odd. n = 2k+1 (k: integer)
  n^2 = (2k+1)^2 = 4k^2+4k+1 = 2(2k^2+2k)+1 = 2r+1 (r = 2k^2+2k) : odd
• Ex2)
  the sum of two rational numbers is rational
  Assume r and s are two rational numbers.
  
  
  
  the sum is rational

Proof by Contraposition (대우에 의한 증명)

• ¬q가 True라고 가정할 때 ¬p가 True임을 증명
• Indirect proof (간접 증명)
• Ex1)
  “If n is an integer and 3n+2 is odd, then n is odd.”
  ¬q: n is even, n = 2k
  3n+2 = 3(2k) + 2 = 6k + 2 = 2(3k+1) : even, ∴¬q → ¬p
  => p → q
• Ex2)
  “If n^2 is odd, the n is odd(n: integer)”
  ¬q: n is even, n = 2k
  n^2 = 4k^2 = 2(2k^2) : even, ∴¬q → ¬p
  => p → q

Proof by Contradiction (모순에 의한 증명)

• 주어진 가정(p)을 부정(false)했을 때(¬p)
  항상 False가 되는 명제가 있음을 보이면(¬p→F)
  p의 가정이 잘못되었으므로 p는 True가 됨(T→p)
• Ex)
  “is irrational”
  ¬p: is rational = a/b (b≠0, a and b have no common factors)
  
  
  a^2: even → a: even, a=2c(c: integer)
  
  
  b^2: even → b: even
  This contradicts our assumption that a and b have no common factors.(even 2)
  ¬p → F => T → p

Theorems that are Biconditional Statements

• p → q and q →p are both true임을 증명
• Ex)
  “n is odd iff n^2 is odd when n is an integer.”

---

Proof Methods and Strategy

Proof by Cases (사례에 의한 증명)

• 각각의 (pi → q)를 증명함으로써 전체를 증명하는 방법
  
  위 conditional statement를 증명하기 위해 아래 tautology를 사용
  
  

Existence Proofs (존재 증명)

• ∃xP(x) 형태의 theorems 증명
• Constructive(생산적 존재 증명)
  • P(c)를 true로 하는 하나 이상의 c를 찾아 증명하는 방법 (Existential Generalization(EG))
  • Ex)
    
    <one example> 1729 = 10^3 + 9^3 = 12^3 + 1^3
• Nonconstructive(비생산적 존재 증명)
  • P(c)를 true로 하는 값이 존재하지 않는다고 가정하고 모순을 도출하여 존재를 증명하는 방법
  • Ex)
    p: There exist irrational numbers x and y such that x^y is rational
    ¬p: There is no irrational numbers x and y such that x^y is rational -> x^y must be irrational
    x^y, x are irrational -> must be irrational
    <one counter example> : rational
    ∴ ¬p is wrong, p is proved

Counterexamples

• ∃x¬P(x) ≡ ¬∀xP(x)
• ¬P(c) is true or P(c) is false -> ¬∀xP(x) is true
• ‘c’: counterexample

Uniqueness Proofs

• ∃!xP(x) : “there exists a unique x satisfying P(x)” or “there is exactly one x such that P(x)”
• 증명과정
  • Existence(존재): 특성을 가진 element x의 존재를 증명
  • Uniqueness(유일성): y≠x이면 y는 특성을 갖지 않음을 증명
• Ex)
  “If a and b are real numbers and a≠0, there is a unique real number r such that ar+b=0”
  Existence: r=-b/a <- a(-b/a) + b = -b + b =0
  Uniqueness: s is a real number such that as + b = 0(s≠r)
  ar+b = 0 = as + b -> r =s (contradiction)
  ∴-b/a is the only real number for r such that ar + b =0

Proof Strategies

• Choose a method
  • First Direct method
  • 안되면 Second Indirect method ( or contrapositive…)
• Choose a strategy
  • First Forward reasoning
  • 안되면 Second Backward reasoning

Universally Quantified Assertions

• ∀xP(x) 형태의 theorems 증명
• x is an arbitrary member of the domain -> P(x) must be true(Universal Generalization(UG))
• Ex)
  “An integer x is even if and only if x^2 is even”
  p ↔︎ q ≡ (p→q)∧(q→p)
  case 1: (p→q) If x is even x=2k, x^2 = 4k^2 = 2(2k^2) : even
  case 2: (q→p)=>(¬p→¬q)<contraposition>
  Assume x is not even then x^2 is not even -> x is odd and x^2 is odd
  x = 2k+1, x^2 = (2k+1)^2 = 4k^2+4k+1 = 2(2k^2+2k)+1 : odd