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

No vote yet
12 votes

  Easy Math Editor

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold

- bulleted
- list

  • bulleted
  • list

1. numbered
2. list

  1. numbered
  2. 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"
MathAppears 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

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

Log in to reply

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

Soham Chanda - 5 years, 8 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 - 5 years, 8 months ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...