2
$\begingroup$

From analysis 1 by Terence Tao, I learn that the principle of induction is a peano axiom. In many other analysis books, like analysis by Bartle and Sherbert, the well ordering principle is used to derive the principle of induction. I am thinking now: either both are equivalent statements or one of them is the axiom.

$\endgroup$
1
  • 1
    $\begingroup$ So your question is...? $\endgroup$
    – AlexJaynMF
    Feb 15, 2021 at 22:37

2 Answers 2

2
$\begingroup$

Strictly speaking it's an axiom schema, i.e. an infinite family of axioms, one for each unary predicate. For example, there's one for the predicate $\sum_{k=1}^n=\tfrac12n(n+1)$. There's one for $\sum_{k=1}^n=\tfrac12n(n+1)+1$, but only the former has a true base step, so, unlike the latter, it allows a proof by induction.

Anyway, the basic answer to your question is that which is the axiom (schema) is a matter of convention. Just about every text will take induction to the be the schema presented in a definition of the Peano axioms.

Something similar happens in set theory, where the axiom of choice is equivalent in ZF to all sets having a well-ordering. Combining either with ZF gives ZFC. The C is short for choice, so you can guess which version of the axiom (it's not a schema this time) is added - again, conventionally.

$\endgroup$
4
  • 1
    $\begingroup$ Strictly speaking, many many authors of analysis book work in second-order logic anyway (otherwise what is the axiom of completeness when it comes to the reals, and what are the reals anyway), so the axiom of induction is a single axiom. $\endgroup$
    – Asaf Karagila
    Feb 15, 2021 at 22:59
  • $\begingroup$ I don't have the book by Bartle and Sherbert to hand, but beware that the term well-ordering principle is generally used for a much weaker statement than the well-ordering theorem. You haven't really talked about the former, but I suspect it is what the OP is interested in (and either presented as a schema or as a second order axiom, it is equivalent to induction, qua schema or second order axiom). $\endgroup$
    – Rob Arthan
    Feb 15, 2021 at 23:03
  • 1
    $\begingroup$ @RobArthan My point was the WOP is equivalent to induction while the WOT is equivalent to AC, but neither WO formulation is the default one when we list axioms. $\endgroup$
    – J.G.
    Feb 15, 2021 at 23:19
  • $\begingroup$ Sure, but I'm guessing that the OP may not know about WOT and AC and will confuse WOT in your answer with WOP. $\endgroup$
    – Rob Arthan
    Feb 15, 2021 at 23:26
0
$\begingroup$

The answer, unfortunately, is that it depends on the circumstances. In some cases, the two statements are equivalent (and therefore either one could properly function as the fifth Peano axiom). In other cases, induction is stronger than the well-ordering principle in the sense that induction implies well-ordering, but not vice versa.

This is expounded upon more fully in the wonderful article:

Öhman, L. Are Induction and Well-Ordering Equivalent?. Math Intelligencer 41, 33–40 (2019). https://doi.org/10.1007/s00283-019-09898-4

which can briefly be summarized by his two conclusions:

(A) The induction principle and the well-ordering principle are not equivalent relative to the common first 4 axioms of the Peano system, since the resulting axiomatic systems admit different models.

(B) In the axiomatic system consisting of the common first 4 axioms together with the well-ordering principle, induction cannot be a theorem, since there is a model Ord ($\omega+\omega$) in which all five of these axioms are satisfied, but induction is not true.

He goes on to state:

We may also note that the axiomatic system consisting of the Peano axioms with induction admits only models that are isomorphic to the natural numbers, and since the natural numbers are well-ordered, in this system well-ordering principle is in fact a theorem. Induction is therefore stronger than well-ordering in this context, in that it has the power to rule out more possible models.

$\endgroup$
1
  • 1
    $\begingroup$ To clarify Ohman's result, the "missing axiom" which when added to Peano's first four axioms lets us prove that well-ordering and induction equivalent is: "Every number other than zero has an immediate predecessor." $\endgroup$ Feb 17, 2021 at 20:35

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .