# Complete Induction

1. Jun 18, 2010

### jgens

1. The problem statement, all variables and given/known data

Prove the principle of complete induction using either the well-ordering principle or ordinary mathematical induction.

2. Relevant equations

N/A

3. The attempt at a solution

Suppose that $A$ is a collection of natural numbers such that $1 \in A$ and $n+1 \in A$ whenever $1, \dots, n \in A$. Now suppose that $B$ is the collection of those natural numbers not in $A$. If $B \neq \emptyset$, then by the well-ordering principle, $B$ must have some least element. Clearly, this least element cannot be 1 so suppose instead that $k+1$ is the least element in $B$, in which case $1, \dots, k$ are all in $A$; however, this implies that $k+1 \in A$ which is a contradiction. Thus our assumption that $B$ was non-empty must have been incorrect and $A = \mathbb{N}$.

Is this correct?

2. Jun 19, 2010

### jgens

Since it's been roughly a day, does anyone have feedback?