1.8 Induction

Consider the following three fundamental principles for reasoning about nonnegative integers:

• the Induction Principle,
• the Strong Induction Principle,
• the Well Ordering Principle.

Indicate the principle behind each of the inference rules over natural numbers below:

1. \(\dfrac{P(0), \forall m. (\forall k \leq m. P(k)) \text{ IMPLIES } P(m+1)}{\forall n. P(n)} \)

   This is a formulation of:

   Exercise 1

     Ordinary Induction Strong Induction Well Ordering None of the above Strong Induction 
   Notice "\((\forall k \leq m. P(k)) \)"
2. \(\dfrac{P(b), \forall k \geq b. P(k) \text{ IMPLIES } P(k+1)}{\forall m \geq b. P(m)} \)

   This is a formulation of:

   Exercise 2

     Ordinary Induction Strong Induction Well Ordering None of the above Ordinary Induction 
   This is just the induction rule with the base case starting at \(b\) instead of 0.
3. \(\dfrac{\exists n. P(n)}{\exists m. (P(m) \text{ AND } (\forall k. P(k) \text{ IMPLIES } k \geq m))} \)

   This is a formulation of:

   Exercise 3

     Ordinary Induction Strong Induction Well Ordering None of the above Well Ordering 
   If we let \(S\) be the set \(\{ k \; | \;P(k) \}\), then "\(\exists n. P(n)\)" tells us that \(S\) is nonempty, and "\(P(m) \text{ AND } \forall k. P(k) \text{ IMPLIES } k \ge m)\)" says that \(m\) is the smallest number in \(S\).
4. \(\dfrac{P(0), \forall k > 0. P(k) \text{ IMPLIES } P(k+1)}{\forall n. P(n)} \)

   This is a formulation of:

   Exercise 4

     Ordinary Induction Strong Induction Well Ordering None of the above None of the above 
   The rule looks like ordinary induction, but in the antecedent, \(k \) is strictly greater than 0, which leaves the possibility that \(P(0)\) does not imply \(P(1)\). Thus, the induction hypothesis \(P(n)\) may not propagate from 0 to all other nonnegative numbers.
5. \(\dfrac{\forall m. (\forall k < m. P(k)) \text{ IMPLIES } P(m)}{\forall n. P(n)} \)

   This is a formulation of:

   Exercise 5

   &nbsp; Ordinary Induction Strong Induction Well Ordering None of the above Strong Induction&nbsp;
   This rule looks identical to the rule for strong induction, as in Part 1, except with \(P(0) \) missing. It is still a strong induction because the base case is provided: when \(m\) is 0, the assumption of the implication is "vacuously" true, and the conclusion in this case would be precisely that \(P(0)\) is true.
   CheckShow Answer