Question

Let P be some predicate. Check the box next to each scenario in which ∀n ∈ N, P(n) must be true.

a) For every natural number k > 0 , if P(i) holds for every natural number i < k, then P(k) holds.
b) P(0) holds and for every natural number k > 0, if P(i) does not hold, then there is some natural number i < k such that P(i) does not hold.
c) For every natural number k, if P(i) holds for every natural number i < k, then P(k) holds.
d) For every natural number k, if P(k) does not hold, then there is a smaller natural number i < k such that P(i) does not hold.

Answer 1

A

Explanation:

a) ✔️

This is the principle of mathematical induction. If P holds for the base case k=1 and we can show that if it holds for any arbitrary k (e.g. k=n) then it must also hold for the next value (e.g. k=n+1), then we have shown it holds for all natural numbers.

b) ❌

There is no guarantee that P holds for all natural numbers from the statement alone. It only guarantees that for any k where P does not hold, there exists a smaller number i where P does not hold.

c) ❌

This is the principle of weak mathematical induction. It only shows that if P holds for a given k and for all smaller values i then it must hold for k+1. It does not guarantee that P holds for all natural numbers.

d) ❌

This statement is the negation of the principle of mathematical induction. It is known as the "strong induction" principle, which assumes that if P does not hold for k, then there exists a smaller i where P does not hold. However, this principle is not sufficient to prove that P holds for all natural numbers k.