Waste less time on Facebook — follow Brilliant.

Mathematical Induction and Well-Ordering Principle?

We all know about mathematical induction and well-ordering principle. Both so obvious that they can be taken as axioms. But recently I read a proof of both. In the proof of the Principle of Mathematical Induction, the author (of the book I read) uses the well-ordering principle. And surprisingly, the principle of mathematical induction is also used in proving well-ordering principle. And further, the author says that both the principles are equivalent.

How can these two principles be equivalent? They are stated differently.

Also, shouldn't one of these principles be taken as an axiom? I think that Well-ordering principle is more suitable to be taken as an axiom. Isn't it? What do you think?

Note by Avinash Pandey
4 years, 9 months ago

No vote yet
12 votes


Sort by:

Top Newest

Them being equivalent means that if you assume the Well-Ordering Principle holds, then you can prove Induction is a valid method of proof and vice versa. Indeed one of them is taken as an axiom, most authors take induction as the axiom they choose.

Lawrence Sun - 4 years, 9 months ago

Log in to reply

Yes, equivalent just means that the statements imply each other.

Since the statements are equivalent, it doesn't really matter which you choose as an axiom. Induction is often used as the axiom mainly because it is the one [edit: method of proof] that's more often used. If you took the well-ordering principle, in a proof that's stripped down to the axioms, you'd still have to show that well-ordering principle implies mathematical induction.

Calvin Lin Staff - 4 years, 9 months ago

Log in to reply

Well actually you don't have to. Instead you could do something like define \(S\) as the set of all counterexamples to the statement. Then by the Well-Ordering Principle there is a least element. If the element is \(1\), go do the base case. If the element is \(> 1\), do the inductive step. So induction is not necessarily better in terms of efficiency actually.

Lawrence Sun - 4 years, 9 months ago

Log in to reply

In case anyone is interested, here is a link containing a proof of the equivalence of Induction and the Well-Ordering Principle.

Omid Rooholfada - 4 years, 9 months ago

Log in to reply

You talking bout "elementary number theory" by d.m.burton?

Soham Chanda - 4 years, 9 months ago

Log in to reply

Traditionally, in Peano arithmetic, we generally take the axiom of induction. http://en.wikipedia.org/wiki/Well-ordering_principle

O B - 4 years, 9 months ago

Log in to reply


Problem Loading...

Note Loading...

Set Loading...