Lesson 4

Theorem. The following properties of order \(P\) are equivalent:

1. every non-empty set has a minimal element;
2. any descending chain is finite;
3. the principle of mathematical induction holds (for any predicate \(A \colon P \to \{0,1\}\)):

   if for any \(p \in P\), the statement \(A(p)\) is true if \(A(q)\) is true for all \(q \prec p\), then \(A(p)\) is true for all \(p \in P\).

Proof.

• \(1 \Rightarrow 2\).  If there is an infinite descending chain, then the set of its elements has no minimal element.


• \(2 \Rightarrow 1\).  If there is a non-empty set without a minimal element, then we can construct an infinite strictly descending sequence: start with an arbitrary element \(x_{0}\); since it is not minimal, choose a smaller element \(x_{1}\); since it is also not minimal, choose a smaller element \(x_{2}\)—and so on.


• \(1 \Rightarrow 3\).  Suppose the set \[\{x \in P \colon A(x) \text{ is false}\}\] is non-empty. Then it has a minimal element \(m\). But then \(A(y)\) is true for all \(y \prec m\), and hence, by the induction assumption, \(A(m)\) is true. This contradiction shows that the considered set must be empty, which means that \(A(x)\) is true for all \(x \in P\).


• \(3 \Rightarrow 1\).  Assume there exists a set \(X \subseteq P\) having no minimal element. Define a predicate \(A \colon P \to \{0,1\}\) as follows: \(A(p)=[p \not \in X]\). It is not difficult to see that the principle of mathematical induction works for \(A\). Indeed, if \(A(q)=1\) for all \(q \prec p\) (that is, \(q \not \in X\) for all \(q \prec p\)), then \(A(p)=1\): if this were not the case, then \(p\) would lie in \(X\) and hence would be minimal in \(X\). Hence, by the principle of mathematical induction, \(A(p)=1\) for all \(p \in P\) meaning that \(X\) is empty.

◼