Jump to content

Induction, bounding and least number principles

From Wikipedia, the free encyclopedia

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.