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 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]