Lesson 2

As we have already seen, the principle of mathematical induction is equivalent to the following property of positive integers (called the well-ordering principle): every non-empty subset has a minimal element.

At this point, it is natural to ask: for which other ordered sets does the principle of mathematical induction hold? In other words, for which orders \((P, \preceq)\) is the following statement true for any predicate \(A \colon P \to \{0,1\}\)? \[\frac{\forall n \in P \colon [(\forall m \prec n \colon A(m)) \Rightarrow A(n)]}{\forall n \in P \colon A(n)}\ .\] The simplest example of an order where this statement does not hold is \((\mathbb{R}, \le)\), i.e., the set of real numbers with the standard order relation. Indeed, let the predicate \(A \colon \mathbb{R}\to \{0,1\}\) be defined as \(A(n)=[n \le 1]\). Clearly, this predicate is not true at all points. However, the transition holds. Indeed, for the statement \([(\forall m \prec n \colon A(m)) \Rightarrow A(n)]\) to be false, it must be true that \((\forall m \prec n \colon A(m))\) but not \(A(n)\). But this does not happen: if \(A(n)\) is false, then \(n>1\), but then there exists \(m\) such that \(n>m>1\), and then \((\forall m \prec n \colon A(m))\) will be false. In other words, among the points where \(A\) is false, we cannot find a minimal one.