A problem in Spivak's Calculus, ch 2-10, asks to prove induction by the well-ordered principle. I have read a number of answers to that question on this site, but I would like to see the proof in a more formal and unprejudiced way. My approach so far:
Givens: well ordering $$ \forall S \subseteq\mathbb N(S\neq\emptyset\rightarrow\exists!x\in S \forall y \in S(x<y)) $$
Goal: induction $$ \forall S \subseteq\mathbb N[(x \in S \land (y \in S \rightarrow (y+1) \in S))\rightarrow S =\mathbb N] $$
This approach is somewhat mimicking Velleman's approach in " How to prove it"- a book I am familiar with. Please tell me if I actually expressed the two principles correctly in a formal way and how I would proceed from there. Thanks in advance.
Assume well ordering, and suppose $S\subseteq N$ satisfies $0\in S$ and $\forall y(y\in S\to y+1\in S)$. We can then prove $S=\mathbb N$ by contradiction.
Namely, suppose that you have an $S\ne \mathbb N$. Since $S\subseteq N$, this means that $\mathbb N\setminus S$ is a nonempty set, and therefore, by well-ordering has a least element $x$.
If $x=0$, then $0\notin S$, contradicting our assumption.
On the other hand if $x\ne 0$, then there is an $y$ such that $x=y+1$. (*) Since $x$ was the least element in $\mathbb N\setminus S$ and $y<x$ we must have $y\in S$. But then we have $y\in S$ and $y+1\notin S$, again contradicting the assumption.
(*) The fact that every natural number is either 0 or the successor of something is essential for the implication to hold. Otherwise, a counterexample would be the set $\mathbb N\times\mathbb N$ with the lexicographical ordering (that is, $(a,b)<(c,d)$ if $a<c$ or $a=c$ and $b<d$) and where the successor of $(a,b)$ is $(a,b+1)$. This is a well-ordered set, but does not satisfy the induction principle the way it is usually formulated for $\mathbb N$ -- it fails for $S=\{0\}\times\mathbb N$.