Journal of Logic and Computation

Journal of Logic and Computation Advance Access published online on February 6, 2008
Journal of Logic and Computation, doi:10.1093/logcom/exn003

This Article Abstract Full Text (PDF) Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Add to My Personal Archive Download to citation manager Request Permissions Google Scholar Articles by Moniri, M. Social Bookmarking          What's this?

© The Author, 2008. Published by Oxford University Press. All rights reserved. For Permissions, please email: journals.permissions@oxfordjournals.org

Original papers

On the Hierarchy of Intuitionistic Bounded Arithmetic

Morteza Moniri

Department of Mathematics, Shahid Beheshti University, Evin, Tehran, Iran.

E-mail: m-moniri{at}cc.sbu.ac.ir, ezmoniri{at}gmail.com

Received 22 January 2007.

In this article, we study the two hierarchies of intuitionistic bounded arithmetic introduced by Buss and Harnik. Harnik's hierarchy contains the theory defined and studied by Cook and Urquhart as the first level. We prove level by level equivalence between the two hierarchies (for the first level, the fact was first proved by Cook and Urquhart using realizability and functional interpretation and later by Buss by an elementary method). Next we investigate the question of whether the hierarchy, denoted , collapses. We show that if , then and so the polynomial hierarchy collapses to . Our proof for this is independent from earlier works on relating the collapse of the hierarchy of classical bounded arithmetic and the collapse of the polynomial hierarchy. We give an elementary model theoretic proof using only the basic properties of the theories and we do not use results which belong to Cook and Urquhart and also Harnik that characterize the definable functions of these theories with long witnessing proofs.

Keywords: Bounded arithmetic; intuitionistic logic; polynomial hierarchy; kripke model

References

1. Buss SR. Bounded Arithmetic (1986) Naples: Bibliopolis.
2. Buss SR. The Polynomial Hierarchy and Intuitionistic Bounded Arithmetic (1986) Berlin: Springer. 77–103. Structure in complexity theory (Berkeley, CA, 1986), Lecture Notes in Computer Science, 223.
3. Buss SR. A Note on Bootstrapping Intuitionistic Bounded Arithmetic (1992) Cambridge: Cambridge University Press. 149–169. Proof theory (Leeds, 1990).
4. Buss SR. On model theory for intuitionistic bounded arithmetic with applications to independence results. In: Feasible Mathematics—Buss SR, Scott PJ, eds. (1990) Birkhauser. 27–47.
5. Buss SR. Relating the bounded arithmetic and polynomial time hierarchy. In: Annals of Pure and Applied Logic (1995) 75:67–77.[CrossRef][ISI]
6. Cook SA, Urquhart A. Functional interpretations of feasibly constructive arithmetic. In: Annals of Pure and Applied Logic (1993) 63:103–200.[CrossRef][ISI]
7. Harnik V. Provably total functions of intuitionistic bounded arithmetic. In: Journal of Symbolic Logic (1992) 57:466–477.[CrossRef][ISI]
8. Hodges W. A Shorter Model Theory (1997) Cambridge: Cambridge University Press.
9. Krajíek J. Bounded Arithmetic, Propositional Logic, and Complexity Theory (1995) Cambridge: Cambridge University Press.
10. Krajíek J, Pudlak P, Takeuti G. Bounded arithmetic and the polynomial hierarchy, International symposium on Mathematical logic and its applications (Nagoya, 1988). In: Annals of Pure and Applied Logic (1991) 52:143–153.[CrossRef][ISI]
11. Moniri M. Comparing constructive arithmetical theories based on NP-PIND and coNP-PIND. In: Journal of Logic and Computation (2003) 13:881–888.[Abstract/Free Full Text]
12. Moniri M. Preservation theorems for bounded formulas. In: Archive for Mathematical Logic (2007) 46:9–14.[CrossRef][ISI]
13. Wehmeier KF. Semantical Investigations in Intuitionistic First-Order Arithmetic. Phd Thesis (1996) Munster.
14. Zambella D. Notes on polynomially bounded arithmetic. In: Journal of Symbolic Logic (1996) 61:942–966.[CrossRef][ISI]

CiteULike    Connotea    Del.icio.us    What's this?

This Article Abstract Full Text (PDF) Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Add to My Personal Archive Download to citation manager Request Permissions Google Scholar Articles by Moniri, M. Social Bookmarking          What's this?