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?

#NumberTheory #Polls #HelpMe! #Proofs #Math #Opinions

Easy Math Editor

This discussion board is a place to discuss our Daily Challenges and the math and science related to those challenges. Explanations are more than just a solution — they should explain the steps and thinking strategies that you used to obtain the solution. Comments should further the discussion of math and science.

When posting on Brilliant:

Use the emojis to react to an explanation, whether you're congratulating a job well done , or just really confused .
Ask specific questions about the challenge or the steps in somebody's explanation. Well-posed questions can add a lot to the discussion, but posting "I don't understand!" doesn't help anyone.
Try to contribute something new to the discussion, whether it is an extension, generalization or other idea related to the challenge.
Stay on topic — we're all here to learn more about math and science, not to hear about your favorite get-rich-quick scheme or current world events.

Markdown	Appears as
`italics` or `_italics_`	italics
`bold` or `__bold__`	bold
- bulleted - list	bulleted list
1. numbered 2. list	numbered list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1 paragraph 2	paragraph 1 paragraph 2
`[example link](https://brilliant.org)`	example link
`> This is a quote`	This is a quote
# I indented these lines # 4 spaces, and now they show # up as a code block. print "hello world"	# I indented these lines # 4 spaces, and now they show # up as a code block. print "hello world"

Math	Appears as
Remember to wrap math in `$` ... `$` or `\[` ... `\]` to ensure proper formatting.
`2 \times 3`	$2 \times 3$
`2^{34}`	$2^{34}$
`a_{i-1}`	$a_{i-1}$
`\frac{2}{3}`	$\frac{2}{3}$
`\sqrt{2}`	$\sqrt{2}$
`\sum_{i=1}^3`	$\sum_{i=1}^3$
`\sin \theta`	$\sin \theta$
`\boxed{123}`	$\boxed{123}$

Comments

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 - 8 years, 4 months ago

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 - 8 years, 4 months ago

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 - 8 years, 4 months ago

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

o b - 8 years, 4 months ago

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

Soham Chanda - 8 years, 4 months ago

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

Omid Rooholfada - 8 years, 4 months ago

Math	Appears as
Remember to wrap math in `\(` ... `\)` or `\[` ... `\]` to ensure proper formatting.
`2 \times 3`	$2 \times 3$
`2^{34}`	$2^{34}$
`a_{i-1}`	$a_{i-1}$
`\frac{2}{3}`	$\frac{2}{3}$
`\sqrt{2}`	$\sqrt{2}$
`\sum_{i=1}^3`	$\sum_{i=1}^3$
`\sin \theta`	$\sin \theta$
`\boxed{123}`	$\boxed{123}$