Hostname: page-component-cd9895bd7-dzt6s Total loading time: 0 Render date: 2024-12-26T23:05:36.181Z Has data issue: false hasContentIssue false
  • English
  • Français

END-EXTENSIONS OF MODELS OF WEAK ARITHMETIC FROM COMPLEXITY-THEORETIC CONTAINMENTS

Published online by Cambridge University Press:  19 July 2016

LESZEK ALEKSANDER KOŁODZIEJCZYK
LESZEK ALEKSANDER KOŁODZIEJCZYK*
Affiliation:
INSTITUTE OF MATHEMATICS UNIVERSITY OF WARSAW BANACHA 2, 02-097 WARSZAWA POLANDE-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

We prove that if the linear-time and polynomial-time hierarchies coincide, then every model of Π1(ℕ) + ¬Ω1 has a proper end-extension to a model of Π1(ℕ), and so Π1(ℕ) + ¬Ω ⊢ BΣ1. Under an even stronger complexity-theoretic assumption which nevertheless seems hard to disprove using present-day methods, Π1(ℕ) + ¬Exp ⊢ BΣ1. Both assumptions can be modified to versions which make it possible to replace Π1(ℕ) by IΔ0 as the base theory.

We also show that any proof that IΔ0 + ¬Exp does not prove a given finite fragment of BΣ1 has to be “nonrelativizing”, in the sense that it will not work in the presence of an arbitrary oracle.

Keywords

collection schemeend-extensionsweak arithmetictime hierarchieslinear time hierarchyfractional-exponential growth
Type
Articles
Information
The Journal of Symbolic Logic , Volume 81 , Issue 3 , September 2016 , pp. 901 - 916
Copyright
Copyright © The Association for Symbolic Logic 2016 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

REFERENCES

Adamowicz, Z., A recursion-theoretic characterization of instances of BΣ n provable in Π n+1(N). Fundamenta Mathematicae, vol. 129 (1988), pp. 231–236.Google Scholar
Adamowicz, Z., Kołodziejczyk, L. A., and Paris, J., Truth definitions without exponentiation and the Σ1 collection scheme , this Journal, vol. 77 (2012), pp. 649–655.Google Scholar
Balcázar, J. L., Díaz, J., and Gabarró, J., Structural Complexity II, Springer-Verlag, Berlin, 1990.Google Scholar
Balcázar, J. L., Díaz, J., and Gabarró, J., Structural Complexity I. Second, Revised Edition, Springer-Verlag, 1995.Google Scholar
Beklemishev, L. D., A proof-theoretic analysis of collection . Archive for Mathematical Logic, vol. 37 (1998), pp. 275–296.CrossRefGoogle Scholar
Boughattas, S. and Kołodziejczyk, L. A., The strength of sharply bounded induction requires MSP . Annals of Pure and Applied Logic, vol. 161 (2010), pp. 504–510.Google Scholar
Cordón-Franco, A., Fernández-Margarit, A., and Lara-Martín, F. F., On axiom schemes for T-provably Δ1 formulas . Archive for Mathematical Logic, vol. 53 (2014), pp. 327–349.CrossRefGoogle Scholar
Dekhtyar, M. I., On the relativization of deterministic and nondeterministic complexity classes . Mathematical Foundations of Computer Science 1976, vol. 45, Lecture Notes in Computer Science, Springer, Berlin, 1976, pp. 255–259.Google Scholar
Ferreira, F., Binary models generated by their tally part . Archive for Mathematical Logic, vol. 33 (1994), pp. 283–289.Google Scholar
Ferreira, F., On end-extensions of models of ¬ exp. Mathematical Logic Quarterly, vol. 42 (1996), pp. 1–18.CrossRefGoogle Scholar
Håstad, J., Computational Limitations for Small Depth Circuits , PhD thesis, MIT, 1986.Google Scholar
Heller, H., On relativized polynomial and exponential computations . SIAM Journal on Computing, vol. 13 (1984), pp. 717–725.Google Scholar
Hájek, P. and Pudlák, P., Metamathematics of First-Order Arithmetic, Springer-Verlag, Berlin, 1993.Google Scholar
Jeřábek, E., The strength of sharply bounded induction . Mathematical Logic Quarterly, vol. 52 (2006), pp. 613–624.Google Scholar
Kneser, H., Reelle analytische Lösungen der Gleichung φ(φ(x)) = e x und verwandter Funktionalgleichungen . Journal für die reine und angewandte Mathematik, vol. 187 (1950), pp. 56–67.Google Scholar
Krajíček, J., Bounded Arithmetic, Propositional Logic, and Complexity Theory, Cambridge University Press, Cambridge, 1995.Google Scholar
Krajíček, J., Pudlák, P., and Takeuti, G., Bounded arithmetic and the polynomial hierarchy. Annals of Pure and Applied Logic, vol. 52 (1991), pp. 143–154.Google Scholar
Miltersen, P. B., Vinodchandran, N. V., and Watanabe, Osamu, Super-polynomial versus half-exponential circuit size in the exponential hierarchy . Computing and Combinatorics 5th Annual International Conference, COCOON’99 (Asano, T. et al., editor), Springer, Berlin, 1999, pp. 210–220.Google Scholar
Parsons, C., On a number-theoretic choice schema and its relation to induction . Intuitionism and Proof Theory. Proceedings of the Summer Conference at Buffalo, N.Y., 1968, vol. 57, Studies in logic and the foundations of mathematics, North-Holland, Amsterdam, 1970, pp. 459–473.CrossRefGoogle Scholar
Paris, J. B. and Kirby, L. A. S., Σ n collection schemas in arithmetic . Logic Colloquium ’77, vol. 96, Studies in Logic and the Foundations of Mathematics, North Holland, Amsterdam, 1978, pp. 199–209.Google Scholar
Szekeres, G., Fractional iteration of exponentially growing functions . Journal of the Australian Mathematical Society, vol. 2 (1961/62), pp. 301–320.Google Scholar
Thapen, N., Notes on switching lemmas, unpublished, available at users.math.cas.cz/thapen, 2009.Google Scholar
Wilkie, A. and Paris, J., On the existence of end-extensions of models of bounded induction . Logic, Methodology, and Philosophy of Science VIII (Moscow 1987) (Fenstad, J.E., Frolov, I.T., and Hilpinen, R., editors), pp. 143–161, North-Holland, Amsterdam, 1989.Google Scholar
Wrathall, C., Rudimentary predicates and relative computation . SIAM Journal on Computing, vol. 7 (1978), pp. 194–209.Google Scholar
Zambella, D., End extensions of models of linearly bounded arithmetic . Annals of Pure and Applied Logic, vol. 88 (1997), pp. 263–277.Google Scholar