Induction, bounding and least number principles explained

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:^[1] I \varphi: [ \varphi( 0 ) \land \forall x ( \varphi(x) \to \varphi(x +1 ) ) ] \to \forall x \varphi (x)

There is a similar strong induction principle for

\varphi :I '\varphi: \forall x [ ( \forall y<x \varphi(y) ) \to \varphi(x) ] \to \forall x \varphi (x)

The least number principle for

\varphi is the sentence:L \varphi: \exists x \varphi (x) \to \exists x' ( \varphi (x') \land \forall y < x' ln ot \varphi(y) )

Finally, the bounding principle for

\psi is the sentence:B \psi: \forall u [ ( \forall x < u \exists y \psi(x,y) ) \to \exists v \forall x < u \exists y < v \psi(x,y) ]

More commonly, we consider these principles not just for a single formula, but for a class of formulae in the arithmetical hierarchy. For example,

I \Sigma _{2} is the axiom schema consisting of I \varphi for every \Sigma _{2} formula \varphi(x) in one free variable.

Nonstandard models

It may seem that the principles

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

Now, considering the principles

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

Relations between the principles

The following relations hold between the principles (over the weak base theory

PA ^{-} + I \Sigma _{0} ):I '\varphi \equiv L ln ot\varphi for every formula \varphi ;I \Sigma _{n} \equiv I \Pi _{n} \equiv I '\Sigma _{n} \equiv I '\Pi _{n} \equiv L \Sigma _{n} \equiv L \Pi _{n} ;I \Sigma _{n+1} \implies B \Sigma _{n+1} \implies I \Sigma _{n} , and both implications are strict;B \Sigma _{n+1} \equiv B \Pi _{n} \equiv L \Delta _{n+1} ;L \Delta _{n} \implies I \Delta _{n} , but it is not known if this reverses.

Over

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

Reverse mathematics

The induction, bounding and least number principles are commonly used in reverse mathematics and second-order arithmetic. For example,

I \Sigma _{1} is part of the definition of the subsystem RCA _{0} of second-order arithmetic. Hence, I '\Sigma _{1} , L \Sigma _{1} and B \Sigma _{1} are all theorems of RCA _{0} . The subsystem ACA _{0} proves all the principles I \varphi , I '\varphi , L \varphi , B \psi for arithmetical \varphi , \psi . The infinite pigeonhole principle is known to be equivalent to B \Pi _{1} and B \Sigma _{2} over RCA _{0} .^[3]

Notes and References

1. Book: Hájek. Petr. Metamathematics of First-Order Arithmetic. Pudlák. Pavel. Association for Symbolic Logic c/- Cambridge University Press. 2016. 978-1-107-16841-1. 1062334376.
2. Slaman. Theodore A.. 2004-08-01. \Sigma _{n} -bounding and \Delta _{n} -induction. Proceedings of the American Mathematical Society. 132. 8. 2449. 10.1090/s0002-9939-04-07294-6. 0002-9939. free.
3. Hirst. Jeffry. August 1987. Combinatorics in Subsystems of Second Order Arithmetic. PhD. Pennsylvania State University.