Proof Strategies

Important

If the interpretation is clear, then a PL formula can be interpreted as a statement.

Proofs for implications $S⟹T$

Direct proof (of $S⟹T$)

• assume $S$ is true and prove $T$ under this assumption.
• simple example: if $a,b$ are perfect squares, then $a\cdot b$ is a perfect square
  • There exist $u,v$ with $a=u^2$ and $b=v^2$ (assumption $S$)
  • $⟹ab=(u\cdot u)(v\cdot v)$
  • $⟹ab=u\cdot (u\cdot v)\cdot v$
  • $⟹ab=u\cdot (v\cdot u)\cdot v$
  • $\stackrel{\cdot }{⟹}ab=(uv)(uv)$ (associativity of $\cdot$)
  • $⟹$ there exists $w$ with $ab=w\cdot w$
  • $⟹$ $a\cdot b$ is a perfect square

Indirect proof (of $S⟹T$)

• assume $T$ is false, show that $S$ is false
• Reason: $\neg G\to \neg F\models F\to G$
• Example: The square root of an irrational number $x>0$ is irrational
  • $S$: $x>0$ irrational
  • $T$: $\sqrt{x}$ irrational
  • $\sqrt{x}$ rational ($\neg T$) $\stackrel{\cdot }{⟹}$ there exist $m,n\in \mathbb{Z}$ with $\sqrt{x}=\frac{m}{n}$
  • $\stackrel{\cdot }{⟹}x=\frac{m^2}{n^2}$ rational ($\neg S$)

by transitivity

• Definition: Allgemein
• Example: Equivalent Statements to linear dependence
• Reason: $(F\to G)\wedge (G\to H)\models F\to H$
• Variant: find $R_1,R_2$ with $S⟹R_1$ and $S⟹R_2$ and $R_1\text{ and }{R}_2⟹T$

Proofs for general statements S

Modus Ponens

Modus Ponens

Ziel: Aussage $S$ Vorgehen:

1. Finde geeignete Aussage $R$
2. Beweise $R$
3. Beweise $R⟹S$

Falsches Beispiel

Theorem $1<0$ Beweise: $1>0⟹2<1$ (+1 beide Seite) $⟹2>1$ (*1, weil 1 negativ ist)

Man sollte anders um beweisen, vom Wahres anfangen It’s crucial not to confuse the direction of implication. Proving S⟹R and R is true does not imply that S is true.

Link to original

Case distinction

(generalization of Modus Ponens)

• find $R_1,R_2,\dots ,R_n$, prove that $R_1$ or $R_2$,…, or $R_n$ holds, prove that for all $i$, $R_i⟹S$

Proof by contradiction

• find $T$, prove that $T$ is false, prove that $S$ is false $⟹$ $T$ true
• Reason: $(\neg F\to G)\wedge \neg G\models F$
• Example: $\sqrt{2}$ irrational
  • $\sqrt{2}\text{ rational}⟹\sqrt{2}=\frac{m}{n},gcd(m,n)=1$
  • $⟹2=\frac{m^2}{n^2}⟹m^2=2n^2⟹2|m^2⟹2|m$
  • $⟹4|m^2⟹4|2n^2⟹2|n^2⟹2|n$
  • $⟹gcd(m,n)\ge 2$
  • false

Pigeonhole principle

just write “Pigeonhole principle” to prevent complicated explanations

Proofs for statements of the form $\forall nP(n)$ (universe $U=\mathbb{N}$)

1. prove $P(0)$ true
2. prove for all n that $P(n)\text{ true}⟹P(n+1)\text{ true}$ Reason: For $U=\mathbb{N}$ and any predicate $P$, the following holds $P(0)\wedge \forall n(P(n)\to P(n+1))\models \forall nP(n)$