Induction, bounding and least number principles

(Redirected from Least number principle)

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

edit

Informally, for a first-order formula of arithmetic   with one free variable, the induction principle for   expresses the validity of mathematical induction over  , while the least number principle for   asserts that if   has a witness, it has a least one. For a formula   in two free variables, the bounding principle for   states that, for a fixed bound  , if for every   there is   such that  , then we can find a bound on the  's.

Formally, the induction principle for   is the sentence:[1]

 

There is a similar strong induction principle for  :[1]

 

The least number principle for   is the sentence:[1]

 

Finally, the bounding principle for   is the sentence:[1]

 

More commonly, we consider these principles not just for a single formula, but for a class of formulae in the arithmetical hierarchy. For example,   is the axiom schema consisting of   for every   formula   in one free variable.

Nonstandard models

edit

It may seem that the principles  ,  ,  ,   are trivial, and indeed, they hold for all formulae  ,   in the standard model of arithmetic  . However, they become more relevant in nonstandard models. Recall that a nonstandard model of arithmetic has the form   for some linear order  . In other words, it consists of an initial copy of  , whose elements are called finite or standard, followed by many copies of   arranged in the shape of  , whose elements are called infinite or nonstandard.

Now, considering the principles  ,  ,  ,   in a nonstandard model  , we can see how they might fail. For example, the hypothesis of the induction principle   only ensures that   holds for all elements in the standard part of   - it may not hold for the nonstandard elements, who can't be reached by iterating the successor operation from zero. Similarly, the bounding principle   might fail if the bound   is nonstandard, as then the (infinite) collection of   could be cofinal in  .

Relations between the principles

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

The following relations hold between the principles (over the weak base theory  ):[1][2]

  •   for every formula  ;
  •  ;
  •  , and both implications are strict;
  •  ;
  •  , but it is not known if this reverses.

Over  , Slaman proved that  .[3]

Reverse mathematics

edit

The induction, bounding and least number principles are commonly used in reverse mathematics and second-order arithmetic. For example,   is part of the definition of the subsystem   of second-order arithmetic. Hence,  ,   and   are all theorems of  . The subsystem   proves all the principles  ,  ,  ,   for arithmetical  ,  . The infinite pigeonhole principle is known to be equivalent to   and   over  .[4]

References

edit
  1. ^ a b c d e 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). " -bounding and  -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.