S1, C3: Induction

Question 1

Strong Induction

Answer 1

1. Base Case

2. For all k, if P(0), P(1),…, P(k) are true, then p(k+1) is also true.

Question 2

Well Ordered

Answer 2

A set is well ordered if every non-empty subset has a least element. The natural numbers are well ordered.