# Well - ordering principle vs Induction

I've always used induction when something has to do with natural numbers. Actually the only time I used the well - ordering principle was to prove the equivalence to the induction principle.

My question is then if there are some sort of problems that are solved easier by using one of these principles over the other or they are all the same in the structure of natural numbers.

Also I have this feeling that the well- ordering principle is more general that induction because it is actually defined in terms of orderings, though I'm not sure (this in reference to any structure or ordering other than the natural numbers).

• Actually the only time I used the well - ordering principle was to prove the equivalence to the induction principle $\color{red}{\text{VS}}$ I have this feeling that the well- ordering principle is more general that induction. Please clarify. – Git Gud Jul 23 '13 at 10:48
• @GitGud The equivalence of both principles is in the structure of $\mathbb{N}$. I'm not sure if there is an equivalence in different structures or orderings. – Daniela Diaz Jul 23 '13 at 10:49
• There are ordinal numbers greater than $\mathbb N$ (or in that context rather $\omega$). Induction in the form that $\Phi(0)$ and $\forall x\colon (\Phi(x)\to\Phi(x+1))$ would imply $\forall x\colon \Phi(x)$ does not hold for these. But they are still well-ordered so that $(\forall y<x\colon \Phi(y))\to\Phi(x)$ implies $\forall x\colon \Phi(x)$. – Hagen von Eitzen Jul 23 '13 at 10:56

Imagine you have to prove $\phi(x), x\in\mathbb{Z}$ and you have proven this $\forall\ x<0: \phi(x)$. Now the well-ordering principle allows to use $\forall\ y<x: \phi(y) \Rightarrow \phi(x)$ as a means of proof, where induction would only permit to use $\forall\ x_0 \leq y < x: \phi(y) \Rightarrow \phi(x)$.
• $\mathbb{Z}$ is not well-ordered, and the proposed proof would not be valid, since the implication would hold for any statement that was false for all integers. – Tobias Kildetoft Jul 23 '13 at 11:22
• The remaining proof would have to prove $\phi(x) \forall\ x\in [0, \infty)$, which indeed is well-ordered. – AlexR Jul 23 '13 at 11:41
• I do not see the problem in my argumentation, considering $(-\infty, 0) \subset \mathbb{Z}$ as proven and then proving "by induction" with starting point $-1$ (wich is proven) and inducing $\phi(0), \phi(1), \ldots$. From this point of view, the two principles are equivalent though, if you permit induction to use $\forall\ y\in [-1 =x_0, x): \phi(x) \Rightarrow \phi(x)$ (as opposed to $\phi(x-1) \Rightarrow \phi(x)$, "forgetting" previous results). – AlexR Jul 23 '13 at 11:55