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 ${\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.

Nonstandard models

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}}}$.

Relations between the principles

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]

Reverse mathematics

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]

References

1. Hájek, Petr; Pudlák, Pavel (2016). Metamathematics of First-Order Arithmetic. Association for Symbolic Logic c/- Cambridge University Press. ISBN   978-1-107-16841-1. OCLC   1062334376.
2. Paris, J.B.; Kirby, L.A.S. (1978), "Σn-Collection Schemas in Arithmetic", Logic Colloquium '77, Elsevier, pp. 199–209, doi:10.1016/s0049-237x(08)72003-2, ISBN   978-0-444-85178-9 , retrieved 2021-04-14
3. Slaman, Theodore A. (2004-08-01). "${\displaystyle \Sigma _{n}}$-bounding and ${\displaystyle \Delta _{n}}$-induction". Proceedings of the American Mathematical Society . 132 (8): 2449. doi: 10.1090/s0002-9939-04-07294-6 . ISSN   0002-9939.
4. Hirst, Jeffry (August 1987). Combinatorics in Subsystems of Second Order Arithmetic (PhD). Pennsylvania State University.