Lesson 1

The classical formulation of the principle of mathematical induction is as follows: \[\frac{A(1) \land (\forall n \in \mathbb{Z}_{\ge 1} \colon A(n) \Rightarrow A(n+1))}{\forall n \in \mathbb{Z}_{\ge 1} \colon A(n)}\ .\] This reads as follows: if the predicate \(A \colon \mathbb{Z}_{\ge 1}\to \{0,1\}\) is true at \(n=1\), and also \(A(n+1)\) follows from \(A(n)\) (for all \(n\)), then \(A\) is true for all points. As we have already discussed, \(A(n+1)\) can be derived not only from the directly preceding statement \(A(n)\) but also from all preceding statements (complete induction): \[\frac{A(1) \land (\forall n \in \mathbb{Z}_{\ge 1} \colon \bigwedge_{i \in [n]}A(i) \Rightarrow A(n+1))}{\forall n \in \mathbb{Z}_{\ge 1} \colon A(n)}\ .\] The last formulation can be rewritten as follows (instead of explicitly listing all previous statements, we use the universal quantifier): \[\frac{A(1) \land (\forall n \in \mathbb{Z}_{\ge 1} \colon (\forall m < n \colon A(m)) \Rightarrow A(n))}{\forall n \in \mathbb{Z}_{\ge 1} \colon A(n)}\ .\] Finally, in this variant, the base case can be incorporated into the step: \[\frac{\forall n \in \mathbb{Z}_{\ge 1} \colon [(\forall m < n \colon A(m)) \Rightarrow A(n)]}{\forall n \in \mathbb{Z}_{\ge 1} \colon A(n)}\ .\] Here, the base case \(A(1)\) must hold because the statement \((\forall m<n \colon A(m))\) is true (since \(m<1\) does not occur).