5
$\begingroup$

Well-ordering principle on $\mathbb N \iff$ Principle of induction $\iff$ Principle of strong induction

How to prove one of them ?

On Proofwiki there is an article proving the equivalence of the statements listed above. However the proof of an individual statement depends on the proof of one of the others, so in order to prove them all, one must prove one of them ?

I know we can prove the Principle of induction by assuming there is a smallets $n \in \mathbb N$ such that $P(n)$ doesnt hold and then get a contradiction, since we have already proved $P(0) \land P(n-1) \Rightarrow P(n)$, so $P(n)$ is indeed true.

However in this proof we are actually relying on the well-ordering principle on $\mathbb N$ ? Otherwise how can one assume there is a smallets $n\in \mathbb N$ such that $P(n)$ is false ?

$\endgroup$
  • $\begingroup$ These "equivalences" makes no sense without a lot more information. Before you can even begin to prove any of this, you need an introductory sentence like: "Let $\mathbb{N}$ denote a set equipped with... Then the following are equivalent: ..." In the absence of this background information, this "theorem" is meaningless. $\endgroup$ – goblin Jun 25 '15 at 8:29
5
$\begingroup$

These are principles, not theorems.

If one principle holds, then they all must hold. If one principle fails to hold, they all fail to hold. Hence, the principles are equivalent. (This is why we see the biconditional $\iff$ being used.)

Put another way, what we have is the following true assertion:

Well-ordering principle on $\mathbb N \iff$ Principle of induction $\iff$ Principle of strong induction.

This assertion claims nothing about the truth value of any one of the principles: it claims only that if one principle is true, they all must be true, and if one principle is false, they all must be false.

And hence, we adopt the well-ordering principle on $\mathbb N$ as an axiom, or else derived from the principle of induction, which is itself basic (taken to be true).

$\endgroup$
  • $\begingroup$ Aha, but in order to show they all hold, we must show that one holds - or am I wrong ? Are principles the same as axioms stated without proof ? Am I right we use the Well-ordering Principle in the proof of the Induction Principle in my proof ? $\endgroup$ – Shuzheng Jan 19 '14 at 18:17
  • $\begingroup$ Yes, they are like axioms stated without proof. $\endgroup$ – Namaste Jan 19 '14 at 18:21
  • $\begingroup$ What are the difference between an axiom and a principle ? And is the well-ordering principle on $\mathbb N$ an axiom of $\mathbb N$ that is well-accepted/official/general and listed in the definition of $\mathbb N$ ? Also amWhy, in the proof of the induction principle I gave, I indeed use the well-ordering principle on $\mathbb N$ $\endgroup$ – Shuzheng Jan 19 '14 at 18:25
  • $\begingroup$ In Peano Arithmetic, second-order arithmetic and related systems, and indeed in most (not necessarily formal) mathematical treatments of the well-ordering principle, the principle is derived from the principle of mathematical induction, which is itself taken as basic. $\endgroup$ – Namaste Jan 19 '14 at 18:29
  • $\begingroup$ So the Principle of Mathematical Induction is an axiom of $\mathbb N$, which imply that the Well-ordering Principle holds ? So the Well-ordering Principle is just derived and not an axiom ? About my proof, I use the Well-ordering Principle in proven the Principle of Induction, right ? $\endgroup$ – Shuzheng Jan 19 '14 at 19:03
2
$\begingroup$

Yes, the point of the equivalence is that if $\mathbb{N}$ has one of the three listed properties, it has them all.

It's interesting to think about what it would take to prove that one of these (say, well-ordering) does in fact hold for $\mathbb{N}$. Which axioms do you plan to use? You have the axioms of arithmetic, and the fact that $\mathbb{N}$ is totally ordered -- but these can't be enough, because the positive rational numbers $\mathbb{Q}^+$ also satisfy these axioms, and are not well-ordered. You need something else -- for instance, an axiom stating that there are no natural numbers between 0 and 1, and then also an axiom that prohibits elements "after" the elements $1, 1+1, 1+1+1, \ldots$, etc. Since the axioms of arithmetic are not enough to distinguish the natural numbers from other number systems like $\mathbb{Q}^+$, some extra axioms -- well-ordering, or others equivalent to it -- must be added.

$\endgroup$
  • $\begingroup$ This axiom that there are no natural numbers between $0$ and$1$ why is this enough ? Then if I give you the set of natural numbers $(1;3)$, then there could be infinite many numbers between $1$ and $2$ ? What you are saying is that these principles are like axioms ? They have no proof, and we should accept them like we accept axioms ? $\endgroup$ – Shuzheng Jan 19 '14 at 18:23
  • $\begingroup$ Right, exactly. $\endgroup$ – user7530 Jan 19 '14 at 18:42
  • $\begingroup$ "You need something else -- for instance, an axiom stating that there are no natural numbers between 0 and 1 --" ? Why should this be equivalent to adding well-ordering as an axiom of $\mathbb N$ ? $\endgroup$ – Shuzheng Jan 19 '14 at 19:06
  • $\begingroup$ You're right, it's not, since it doesn't prohibit nonstandard elements larger than the usual elements on $\mathbb{N}$. Edited. $\endgroup$ – user7530 Jan 19 '14 at 21:16
1
$\begingroup$

These are very basic properties of the natural numbers, so any proof will depend on your definition of (the set of) natural numbers. What is it?

$\endgroup$
  • $\begingroup$ Thank you, do I use the Well-ordering Principle in my proof of the Principle of Induction ? $\endgroup$ – Shuzheng Jan 19 '14 at 19:12
  • $\begingroup$ Yes, @NicolasLykkeIversen, just as you said, you are using it to deduce that if the set of numbers for which $P$ does not hold is non-empty, it has a smallest element. $\endgroup$ – Carsten S Jan 19 '14 at 20:12

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.