0

Just recently , I came to knopw that mathematical induction and well ordering principle are eqivalent. b

So, I'VE trying to solve this inductipn problem using WOP but haven't got anything useful except the irst few obvious things and statements like Assuming a set say S which consists of all those natural numbers for which the proposition is assumed to be false.

So, Instead of giving me a whole solution using this method of any particular problem , can anyone suggest me the steps required to do so. thanks a lot in advance.

Andrés E. Caicedo
  • 79,201
Shreya
  • 3,035
  • 1
    I don't see why you would want to do this. Induction is a proof technique which works on any set that is well-ordered (assuming you define induction correctly). This does not mean that well-ordering is a good way to prove things. – Tobias Kildetoft Aug 05 '13 at 09:11
  • @Andres : oops, hit enter too early on my part. My bad on the retag. – Willie Wong Aug 05 '13 at 15:37
  • (@WillieWong No problem. I was expecting set theory when I began reading the question.) – Andrés E. Caicedo Aug 05 '13 at 15:39

1 Answers1

2

The key is to go back and look at the proof of the equivalency. That is pretty instructive about what to do. So let $P(n)$ be the statement you want to prove. Let $\mathcal{S}=\{n: P(n)$ is false $\}$. Assume that $P(n)$ is nonempty. So by well-ordering it has a least element, call it $n_0$. Show that $P(0)$, or $P(1)$ or some other small example is true, just depending on where you want to start, (this is the analogy of the base case).

This shows that $n_0>0$, (or whatever other number you chose). Not show that if $P(n)$ is true then so is $P(n+1)$ is true as well. Then we know that since $n_0>0$ then $n_0-1\in\mathbb{N}$ and by the definition of $n_0$ we know $P(n_0-1)$ is true. So by what you have proven $P(n_0)$ is true which is a contradiction.

Notice that for the proof you basically are just doing induction and this is the key. The principle of induction and the well-ordering principle are equivalent, in this proof we never used the principle of induction, but that doesn't change the proof, except instead of writing "by induction" at some point we write "by well-ordering" at a different point.

Owen Sizemore
  • 6,440
  • The proof you propose is not correct just assuming well-ordering. In a general well-ordered set, it is not enough to show that $P(n)$ implies $P(n+1)$ since not all elements need to have an immediate predecessor. – Tobias Kildetoft Aug 05 '13 at 09:21
  • @Tobias: Right that's why you need the base case I mention. – Owen Sizemore Aug 05 '13 at 09:24
  • You seem to be thinking that an arbitrary well-ordered set is the same as the natural numbers. This is not the case. It is only for the natural numbers that this version of induction works. – Tobias Kildetoft Aug 05 '13 at 09:26
  • @Tobias: No, I'm only using the well-ordering principle (which only deals with the natural numbers.) I am not considering any larger ordinal. – Owen Sizemore Aug 05 '13 at 09:32
  • Ohh, sorry, I assumed that since the equivalence with induction was mentioned, it would not be just about the integers (after all, stating that two things are equivalent is fairly silly when they are both true). – Tobias Kildetoft Aug 05 '13 at 09:34