Induction, bounding and least number principles
# Induction, bounding and least number principles

In first-order arithmetic, the induction principles, bounding principles, and least number principles are three related families of first-order principles, which may or may not hold in nonstandard models of arithmetic. These principles are often used in reverse mathematics to calibrate the axiomatic strength of theorems.

## Definitions

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

Formally, the induction principle for $\varphi$ is the sentence:

    ${\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 $\varphi$:

    ${\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 $\varphi$ is the sentence:

    ${\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 $\psi$ is the sentence:

    ${\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, ${\mathsf {I}}\Sigma _{2}$ is the axiom schema consisting of ${\mathsf {I}}\varphi$ for every $\Sigma _{2}$ formula $\varphi (x)$ in one free variable.

## Nonstandard models

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

Now, considering the principles ${\mathsf {I}}\varphi$, ${\mathsf {I}}'\varphi$, ${\mathsf {L}}\varphi$, ${\mathsf {B}}\psi$ in a nonstandard model ${\mathcal {M}}$, we can see how they might fail. For example, the hypothesis of the induction principle ${\mathsf {I}}\varphi$ only ensures that $\varphi (x)$ holds for all elements in the standard part of ${\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 ${\mathsf {B}}\psi$ might fail if the bound $u$ is nonstandard, as then the (infinite) collection of $y$ could be cofinal in ${\mathcal {M}}$.

## Relations between the principles

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

* ${\mathsf {I}}'\varphi \equiv {\mathsf {L}}\lnot \varphi$ for every formula $\varphi$;
* ${\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}$;
* ${\mathsf {I}}\Sigma _{n+1}\implies {\mathsf {B}}\Sigma _{n+1}\implies {\mathsf {I}}\Sigma _{n}$, and both implications are strict;
* ${\mathsf {B}}\Sigma _{n+1}\equiv {\mathsf {B}}\Pi _{n}\equiv {\mathsf {L}}\Delta _{n+1}$;
* ${\mathsf {L}}\Delta _{n}\implies {\mathsf {I}}\Delta _{n}$, but it is not known if this reverses.

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

## Reverse mathematics

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

