Chapter 10 Appendix A - Well ordering principle
In Chapter 1 we introduced the Well Ordering principle and the weak and strong principles of Mathematical induction. We show here that they are all equivalent.
Recall the Well Ordering Principle (axiom A10 from Chapter 1)
(WO)
Any non-empty set of positive integers contains a least member.
In Chapter 1 we defined the Principle of (weak) Mathematical Induction (Theorem 1.17) as:
(WI)
If \[P(1)\land \forall n\ge 1\left[\ P(n)\implies P(n+1)\right]\] then \(\forall n\ge1\ P(n)\).
(notice that the converse is automatically true).
We also considered the Principle of (strong) Mathematical Induction as:
(SI)
If \[P(1)\land \forall n\ge 1\left[\left(P(1)\land\ldots\land P(n)\right)\implies P(n+1)\right]\] then \(\forall n\ge1\ P(n)\).
There is a useful alternative way to view these principles. Let \(\emptyset\ne A \subseteq\mathbb N\). Then the principles are equivalent to
(WI’)
\[\text{if }(1\in A)\text{ and }(n\in A\implies n+1\in A)\] then \(A=\mathbb N\).
(SI’)
\[\text{if }(1\in A)\text{ and }\left(\left(1\in A,\ldots,n\in A\right)\implies n+1\in A\right)\] then \(A=\mathbb N\).
The principles (WI), (WI’), (SI), (SI’) and (WO) are all equivalent.
Proof. We show that (SI)\(\implies\)(WI)\(\implies\)(SI’)\(\implies\)(WO)\(\implies\)(WI’)\(\implies\)(SI)
(SI)\(\implies\)(WI). Let \(P\) satisfy the hypothesis of (WI). Let \(Q(n)\) be the statement \(P(1)\land\ldots\land P(n)\). In particular, \(Q(1)=P(1)\) and so \(Q(1)\) is true since \(P(1)\) is. If \(Q(1),\ldots, Q(n)\) hold then in particular \(P(n)\) holds and so, by hypothesis, \(P(n+1)\) holds. Hence \(Q(n+1)\) holds and so \(Q(n)\) holds for all \(n\ge1\). This means that \(P(n)\) holds for all \(n\ge 1\) as required.
(WI)\(\implies\)(SI’). Suppose that \(A\) satisfies the hypothesis of (SI’) and let \(P(n)\) be the statement that \(1,\ldots, n\in A\). Then since \(1\in A\) then \(P(1)\) is true. Now if \(P(n)\) is true then \(1,\ldots, n\in A\) and so \(n+1\in A\) (by hypothesis). Hence \(1,\ldots, n+1\in A\) and so \(P(n+1)\) is true (by definition). So \(P\) satisfies the hypothesis of (WI) and we deduce that \(P(n)\) holds for all \(n\ge1\). Therefore for all \(n\in \mathbb N\) \(1,\ldots,n\in A\) and so in particular \(n\in A\). Thus \(A=\mathbb N\) as required.
(SI’)\(\implies\)(WO). We prove the contrapositive by showing that if \(A\subseteq\mathbb N\) and \(A\) has no least element, then \(A\) is empty. Let \(B=\mathbb N\setminus A\) be the complement of \(A\) in \(\mathbb N\). Then \(1\in B\) since otherwise \(1\in A\) woud be the smallest element of \(A\). If \(1,\ldots, n\in B\) then \(1,\ldots, n\notin A\) and so it follows that \(n+1\not\in A\) since then \(n+1\) would be the least element of \(A\). Hence \(n+1\in B\) and so \(B\) satisfies the hypothesis of (SI’) and it follows that \(B=\mathbb N\). This means that \(A=\emptyset\) as required.
(WO)\(\implies\)(WI’). Suppose that \(A\) satisfies the hypothesis of (WI’) and let \(B=\mathbb N\setminus A\). If \(B\) is non-empty then it has a least element \(b\). But \(b>1\) since \(1\in A\). Hence \(b-1\in A\) since \(b-1\in\mathbb N\) but \(b-1<b\) and so \(b-1\notin B\). But if \(b-1\in A\) then \(b=(b-1)+1\in A\) which is a contradiction. Hence \(B\) is empty and so \(A=\mathbb N\).
(WI’)\(\implies\)(SI). Suppose that \(P\) satisfies the hypothesis of (SI) and let \(A=\{n\in\mathbb N|P(1)\land\ldots\land P(n)\}\). Then \(1\in A\) since \(P(1)\) is true. If \(n\in A\) then \(P(1)\land\ldots\land P(n)\) and so by hypothesis, it follows that \(P(n+1)\) is true. Hence \(n+1\in A\) and so by (WI’) we deduce that \(A=\mathbb N\). Consequently \(P(n)\) is true for all \(n\ge1\).