1
$\begingroup$

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).

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Git Gud Jul 23 '13 at 10:48
  • $\begingroup$ @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. $\endgroup$ – Daniela Diaz Jul 23 '13 at 10:49
  • 2
    $\begingroup$ 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)$. $\endgroup$ – Hagen von Eitzen Jul 23 '13 at 10:56
1
$\begingroup$

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)$.

$\endgroup$
  • 3
    $\begingroup$ $\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. $\endgroup$ – Tobias Kildetoft Jul 23 '13 at 11:22
  • $\begingroup$ The remaining proof would have to prove $\phi(x) \forall\ x\in [0, \infty)$, which indeed is well-ordered. $\endgroup$ – AlexR Jul 23 '13 at 11:41
  • $\begingroup$ That would still not work. You have either the inequality or the implication the wrong way, since the negative integers are only well-ordered when you reverse the usual ordering. $\endgroup$ – Tobias Kildetoft Jul 23 '13 at 11:47
  • $\begingroup$ 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). $\endgroup$ – AlexR Jul 23 '13 at 11:55
  • 1
    $\begingroup$ Ahh, I am sorry. I seem to have read this incorrectly. Yes, your argument is correct. I am not seeing how it is different from induction though. $\endgroup$ – Tobias Kildetoft Jul 23 '13 at 11:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.