Induction, bounding and least number principles

Informally, for a first-order formula of arithmetic ${\displaystyle \varphi (x)}$ with one free variable, the induction principle for ${\displaystyle \varphi }$ expresses the validity of mathematical induction over ${\displaystyle \varphi }$, while the least number principle for ${\displaystyle \varphi }$ asserts that if ${\displaystyle \varphi }$ has a witness, it has a least one. For a formula ${\displaystyle \psi (x,y)}$ in two free variables, the bounding principle for ${\displaystyle \psi }$ states that, for a fixed bound ${\displaystyle k}$, if for every ${\displaystyle n<k}$ there is ${\displaystyle m_{n}}$ such that ${\displaystyle \psi (n,m_{n})}$, then we can find a bound on the ${\displaystyle m_{n}}$'s.

Formally, the induction principle for ${\displaystyle \varphi }$ is the sentence:[1]

${\displaystyle {\mathsf {I}}\varphi$ :\quad {\big [}\varphi (0)\land \forall x{\big (}\varphi (x)\to \varphi (x+1){\big )}{\big ]}\to \forall x\ \varphi (x)}

There is a similar strong induction principle for ${\displaystyle \varphi }$:[1]

${\displaystyle {\mathsf {I}}'\varphi$ :\quad \forall x{\big [}{\big (}\forall y<x\ \ \varphi (y){\big )}\to \varphi (x){\big ]}\to \forall x\ \varphi (x)}

The least number principle for ${\displaystyle \varphi }$ is the sentence:[1]

${\displaystyle {\mathsf {L}}\varphi$ :\quad \exists x\ \varphi (x)\to \exists x'{\big (}\varphi (x')\land \forall y<x'\ \,\lnot \varphi (y){\big )}}

Finally, the bounding principle for ${\displaystyle \psi }$ is the sentence:[1]

${\displaystyle {\mathsf {B}}\psi$ :\quad \forall u{\big [}{\big (}\forall x<u\ \,\exists y\ \,\psi (x,y){\big )}\to \exists v\ \,\forall x<u\ \,\exists y<v\ \,\psi (x,y){\big ]}}

More commonly, we consider these principles not just for a single formula, but for a class of formulae in the arithmetical hierarchy. For example, ${\displaystyle {\mathsf {I}}\Sigma _{2}}$ is the axiom schema consisting of ${\displaystyle {\mathsf {I}}\varphi }$ for every ${\displaystyle \Sigma _{2}}$ formula ${\displaystyle \varphi (x)}$ in one free variable.

It may seem that the principles ${\displaystyle {\mathsf {I}}\varphi }$, ${\displaystyle {\mathsf {I}}'\varphi }$, ${\displaystyle {\mathsf {L}}\varphi }$, ${\displaystyle {\mathsf {B}}\psi }$ are trivial, and indeed, they hold for all formulae ${\displaystyle \varphi }$, ${\displaystyle \psi }$ in the standard model of arithmetic ${\displaystyle \mathbb {N} }$. However, they become more relevant in nonstandard models. Recall that a nonstandard model of arithmetic has the form ${\displaystyle \mathbb {N} +\mathbb {Z} \cdot K}$ for some linear order ${\displaystyle K}$. In other words, it consists of an initial copy of ${\displaystyle \mathbb {N} }$, whose elements are called finite or standard, followed by many copies of ${\displaystyle \mathbb {Z} }$ arranged in the shape of ${\displaystyle K}$, whose elements are called infinite or nonstandard.

Now, considering the principles ${\displaystyle {\mathsf {I}}\varphi }$, ${\displaystyle {\mathsf {I}}'\varphi }$, ${\displaystyle {\mathsf {L}}\varphi }$, ${\displaystyle {\mathsf {B}}\psi }$ in a nonstandard model ${\displaystyle {\mathcal {M}}}$, we can see how they might fail. For example, the hypothesis of the induction principle ${\displaystyle {\mathsf {I}}\varphi }$ only ensures that ${\displaystyle \varphi (x)}$ holds for all elements in the standard part of ${\displaystyle {\mathcal {M}}}$ - it may not hold for the nonstandard elements, who can't be reached by iterating the successor operation from zero. Similarly, the bounding principle ${\displaystyle {\mathsf {B}}\psi }$ might fail if the bound ${\displaystyle u}$ is nonstandard, as then the (infinite) collection of ${\displaystyle y}$ could be cofinal in ${\displaystyle {\mathcal {M}}}$.

The relations between the induction, bounding and least number principles.

The following relations hold between the principles (over the weak base theory ${\displaystyle {\mathsf {PA}}^{-}+{\mathsf {I}}\Sigma _{0}}$):[1][2]

• ${\displaystyle {\mathsf {I}}'\varphi \equiv {\mathsf {L}}\lnot \varphi }$ for every formula ${\displaystyle \varphi }$;
• ${\displaystyle {\mathsf {I}}\Sigma _{n}\equiv {\mathsf {I}}\Pi _{n}\equiv {\mathsf {I}}'\Sigma _{n}\equiv {\mathsf {I}}'\Pi _{n}\equiv {\mathsf {L}}\Sigma _{n}\equiv {\mathsf {L}}\Pi _{n}}$;
• ${\displaystyle {\mathsf {I}}\Sigma _{n+1}\implies {\mathsf {B}}\Sigma _{n+1}\implies {\mathsf {I}}\Sigma _{n}}$, and both implications are strict;
• ${\displaystyle {\mathsf {B}}\Sigma _{n+1}\equiv {\mathsf {B}}\Pi _{n}\equiv {\mathsf {L}}\Delta _{n+1}}$;
• ${\displaystyle {\mathsf {L}}\Delta _{n}\implies {\mathsf {I}}\Delta _{n}}$, but it is not known if this reverses.

Over ${\displaystyle {\mathsf {PA}}^{-}+{\mathsf {I}}\Sigma _{0}+{\mathsf {exp}}}$, Slaman proved that ${\displaystyle {\mathsf {B}}\Sigma _{n}\equiv {\mathsf {L}}\Delta _{n}\equiv {\mathsf {I}}\Delta _{n}}$.[3]

The induction, bounding and least number principles are commonly used in reverse mathematics and second-order arithmetic. For example, ${\displaystyle {\mathsf {I}}\Sigma _{1}}$ is part of the definition of the subsystem ${\displaystyle {\mathsf {RCA}}_{0}}$ of second-order arithmetic. Hence, ${\displaystyle {\mathsf {I}}'\Sigma _{1}}$, ${\displaystyle {\mathsf {L}}\Sigma _{1}}$ and ${\displaystyle {\mathsf {B}}\Sigma _{1}}$ are all theorems of ${\displaystyle {\mathsf {RCA}}_{0}}$. The subsystem ${\displaystyle {\mathsf {ACA}}_{0}}$ proves all the principles ${\displaystyle {\mathsf {I}}\varphi }$, ${\displaystyle {\mathsf {I}}'\varphi }$, ${\displaystyle {\mathsf {L}}\varphi }$, ${\displaystyle {\mathsf {B}}\psi }$ for arithmetical ${\displaystyle \varphi }$, ${\displaystyle \psi }$. The infinite pigeonhole principle is known to be equivalent to ${\displaystyle {\mathsf {B}}\Pi _{1}}$ and ${\displaystyle {\mathsf {B}}\Sigma _{2}}$ over ${\displaystyle {\mathsf {RCA}}_{0}}$.[4]