- #1
mathemasochist
- 5
- 0
Homework Statement
Prove induction from the well-ordering principle.
Homework Equations
The Attempt at a Solution
So my attempt is similar to what Spivak uses to prove well-ordering from induction. Let A be the set equipped with the following properties:
1. 1 is in A
2. For every k in A, k+1 is also in A.
Now for the sake of contradiction, assume a nonempty set B of natural numbers such that none of the elements in B are in A. By well-ordering, there exists a smallest member of B, call it n, and by the conditions on A, n is greater than 1. This means n-1 is in A. However, if n-1 is in A, n is in A as well. Contradiction. So no such nonempty subset B exists. Therefore, all natural numbers are in A.
I feel like I messed up somewhere. In particular, is it valid to assume that, in set A, all members are natural numbers? Sorry, I'm not used to this level of rigor. When I was working through this problem, I had like 10 flashes of circular reasoning that assumed an informal version of induction somewhere.