Proofs

Mathmetical proof #

  • Universal generalisation: show that something holds for some arbitrary values ($\forall$ Itroduction)
  • Exsistential
    • Prove: provide a witness ($\exists$ Introduction)
    • Disprove: show that for all P leads to contradiction
  • Proving equivalences
    • Annotated linear proof: $P \Leftrightarrow ... \Leftrightarrow Q$ (if and only if, iff)
    • Proof both directions seperately: $(P \leftrightarrow Q) \Leftrightarrow ((P \rightarrow Q) \land (Q \rightarrow P))$
  • Proof by contradiction: if something leads to a contradiction, the opposite must be true
  • Proof by contraposition (somtimes easier): $(P \rightarrow Q) \Leftrightarrow (\neg Q \rightarrow \neg P)$
  • Proof by case analysis: $P_1 \lor P_2 \lor ... \lor P_n \rightarrow Q$. Show that each case leads to the same conclusion ($\lor$ Elimination).

To disprove something: give a counterexample where the arguments hold but the conclusion is false.

Mathematical Induction #

Mathematical induction is a proof method that used to prove statements about natural numbers. It is based on the idea that, if a statement is true for a certain number, then it is true for the next number as well.

  1. Base case: show that $P(n_0)$ is true
  2. Induction step: show that for any $k$, $P(k) \Rightarrow P(k+1)$.
    • Induction hypothesis: assumme that $P(k)$ is true
    • Start with $P(k+1)$ on the left hand side and work towards the right hand side.
      • Often you can substitute IH

Strong induction #

Strong mathematical induction requires that the statement is true for all natural numbers up to some arbitrary natural number. You need to show that the statement holds for all natural numbers up to the arbitrary natural number, not just for the arbitrary natural number itself.

  1. Base case: show that $P(n_0)$ is true
  2. Induction step: $P(n_0) \land P(n_0 + 1) \land \dots \land P(k) \Rightarrow P(k+1)$
    • Induction hypothesis: assumme that $P(0), P(1), \dots, P(k)$ is true