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.
Similar content being viewed by others
References
Clote, P.: Partition relations in arithmetic. Proc. 6th Latin American Symposium on Mathematical Logic. Springer LNM, Vol. 1130, p. 32–68 (1983).
Clote, P.: Applications of the low basis theorem in arithmetic (preprint).
Jockusch, C., Soare R.:Π 01 -classes and degrees of theories. TAMS 173 (1972), p. 33–56.
Kanamori, A., McAloon, K.: On Gödel incompleteness and finite combinatorics (preprint).
Ketonen, J., Solovay, R.: Rapidly growing Ramsey functions. Annals of Mathematics 113 (1981), p. 267–314.
Kirby, L., Paris, J.: Initial segments of models of Peano's axioms. Springer LNM, Vol. 619, p. 211–226 (1976).
Paris, J.: A hierarchy of cuts in models of arithmetic. Springer LNM, Vol. 834, p. 312–337 (1979).
Paris, J.: Some conservation results for fragments of arithmetic. Springer LNM, Vol. 890, p. 251–262 (1980).
Paris, J., Dimitracopoulos, C.: Truth definitions for Δ0 formulas. Logic et Algorithmic. Genève (1982), p. 317–329.
Paris, J., Harrington, L.: An incompleteness in Peano arithmetic. Handbook for Mathematical Logic, ed. J. Barwise: North Holland (1976), p. 1133–1142.
Paris, J., Kirby, L.:Σ n collection schemas in arithmetic. Logic Colloquium '77. North Holland (1978), p. 199–210.
Pudlák, P.: Another combinatorial principle independent of Peano's axioms (unpublished).
Simpson, S., Smith, R.: Factorization of polynomials andΣ 01 -induction (preprint).
Smoryński, C.: An asymptotic formula for a logico-combinatorial problem (unpublished).
Author information
Authors and Affiliations
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
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
Received:
Issue Date:
DOI: https://doi.org/10.1007/BF02017489