Skip to main content
SpringerLink
Log in

Combinatorial principles concerning approximations of functions

  • Published:
Archiv für mathematische Logik und Grundlagenforschung Aims and scope Submit manuscript

Abstract

Two infinite combinatorial principlesP(Σ n ) andT(Σ n ) concerning the existence of approximations of functions are studied.T(Σ n ) is shown to be equivalent toIΣ n andP(Σ n ) is shown to be incomparable withBΣ n+1 . Finally Pudláks principle, which is a finite miniaturization of bothT andP, is studied and its instances are related to instances of other known combinatorial statements.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Clote, P.: Partition relations in arithmetic. Proc. 6th Latin American Symposium on Mathematical Logic. Springer LNM, Vol. 1130, p. 32–68 (1983).

    Google Scholar 

  2. Clote, P.: Applications of the low basis theorem in arithmetic (preprint).

  3. Jockusch, C., Soare R.:Π 01 -classes and degrees of theories. TAMS 173 (1972), p. 33–56.

    Google Scholar 

  4. Kanamori, A., McAloon, K.: On Gödel incompleteness and finite combinatorics (preprint).

  5. Ketonen, J., Solovay, R.: Rapidly growing Ramsey functions. Annals of Mathematics 113 (1981), p. 267–314.

    Google Scholar 

  6. Kirby, L., Paris, J.: Initial segments of models of Peano's axioms. Springer LNM, Vol. 619, p. 211–226 (1976).

    Google Scholar 

  7. Paris, J.: A hierarchy of cuts in models of arithmetic. Springer LNM, Vol. 834, p. 312–337 (1979).

    Google Scholar 

  8. Paris, J.: Some conservation results for fragments of arithmetic. Springer LNM, Vol. 890, p. 251–262 (1980).

    Google Scholar 

  9. Paris, J., Dimitracopoulos, C.: Truth definitions for Δ0 formulas. Logic et Algorithmic. Genève (1982), p. 317–329.

  10. Paris, J., Harrington, L.: An incompleteness in Peano arithmetic. Handbook for Mathematical Logic, ed. J. Barwise: North Holland (1976), p. 1133–1142.

  11. Paris, J., Kirby, L.:Σ n collection schemas in arithmetic. Logic Colloquium '77. North Holland (1978), p. 199–210.

  12. Pudlák, P.: Another combinatorial principle independent of Peano's axioms (unpublished).

  13. Simpson, S., Smith, R.: Factorization of polynomials andΣ 01 -induction (preprint).

  14. Smoryński, C.: An asymptotic formula for a logico-combinatorial problem (unpublished).

Download references

Author information

Authors and Affiliations

  1. Prague

    Petr Hájek

  2. Manchester

    Jeff Paris

Authors
  1. Petr Hájek
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Jeff Paris
    View author publications

    You can also search for this author in PubMed Google Scholar

Additional information

This paper was completed in September 1985 when the second author was a guest of the Mathematical Institute of the Czechoslovak Academy of Science in Prague.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Hájek, P., Paris, J. Combinatorial principles concerning approximations of functions. Arch math Logik 26, 13–28 (1987). https://doi.org/10.1007/BF02017489

Download citation

  • Received:

  • Issue Date:

  • DOI: https://doi.org/10.1007/BF02017489

Keywords

Search

Navigation