View in EDS PDF Full Text

On the Hierarchy of Intuitionistic Bounded Arithmetic.

Saved in:
Bibliographic Details
Title: On the Hierarchy of Intuitionistic Bounded Arithmetic.
Authors: MONIRI, MORTEZA1 ezmoniri@gmail.com
Source: Journal of Logic & Computation. Aug2008, Vol. 18 Issue 4, p625-630. 6p.
Subjects: Mathematical logic, Combinatory logic, Nonclassical mathematical logic, Computer logic, Constructive mathematics, Polynomials, Algebra
Abstract: In this article, we study the two hierarchies of intuitionistic bounded arithmetic introduced by Buss and Harnik. Harnik's hierarchy contains the theory IS12 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 ISi2, collapses. We show that if ISi2 ├ ISi+12, then Si2(PV) ├ Σbi = Πbi and so the polynomial hierarchy collapses to Σpi=Πpi. 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 ISi2 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. [ABSTRACT FROM AUTHOR]
Copyright of Journal of Logic & Computation is the property of Oxford University Press / USA and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)
Database: Engineering Source
FullText Links:
  – Type: pdflink
Text:
  Availability: 0
Header DbId: egs
DbLabel: Engineering Source
An: 34034896
AccessLevel: 6
PubType: Academic Journal
PubTypeId: academicJournal
PreciseRelevancyScore: 0
IllustrationInfo
Items – Name: Title
  Label: Title
  Group: Ti
  Data: On the Hierarchy of Intuitionistic Bounded Arithmetic.
– Name: Author
  Label: Authors
  Group: Au
  Data: <searchLink fieldCode="AR" term="%22MONIRI%2C+MORTEZA%22">MONIRI, MORTEZA</searchLink><relatesTo>1</relatesTo><i> ezmoniri@gmail.com</i>
– Name: TitleSource
  Label: Source
  Group: Src
  Data: <searchLink fieldCode="JN" term="%22Journal+of+Logic+%26+Computation%22">Journal of Logic & Computation</searchLink>. Aug2008, Vol. 18 Issue 4, p625-630. 6p.
– Name: Subject
  Label: Subjects
  Group: Su
  Data: <searchLink fieldCode="DE" term="%22Mathematical+logic%22">Mathematical logic</searchLink><br /><searchLink fieldCode="DE" term="%22Combinatory+logic%22">Combinatory logic</searchLink><br /><searchLink fieldCode="DE" term="%22Nonclassical+mathematical+logic%22">Nonclassical mathematical logic</searchLink><br /><searchLink fieldCode="DE" term="%22Computer+logic%22">Computer logic</searchLink><br /><searchLink fieldCode="DE" term="%22Constructive+mathematics%22">Constructive mathematics</searchLink><br /><searchLink fieldCode="DE" term="%22Polynomials%22">Polynomials</searchLink><br /><searchLink fieldCode="DE" term="%22Algebra%22">Algebra</searchLink>
– Name: Abstract
  Label: Abstract
  Group: Ab
  Data: In this article, we study the two hierarchies of intuitionistic bounded arithmetic introduced by Buss and Harnik. Harnik's hierarchy contains the theory IS12 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 ISi2, collapses. We show that if ISi2 ├ ISi+12, then Si2(PV) ├ Σbi = Πbi and so the polynomial hierarchy collapses to Σpi=Πpi. 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 ISi2 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. [ABSTRACT FROM AUTHOR]
– Name: AbstractSuppliedCopyright
  Label:
  Group: Ab
  Data: <i>Copyright of Journal of Logic & Computation is the property of Oxford University Press / USA and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract.</i> (Copyright applies to all Abstracts.)
PLink https://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=egs&AN=34034896
RecordInfo BibRecord:
  BibEntity:
    Languages:
      – Code: eng
        Text: English
    PhysicalDescription:
      Pagination:
        PageCount: 6
        StartPage: 625
    Subjects:
      – SubjectFull: Mathematical logic
        Type: general
      – SubjectFull: Combinatory logic
        Type: general
      – SubjectFull: Nonclassical mathematical logic
        Type: general
      – SubjectFull: Computer logic
        Type: general
      – SubjectFull: Constructive mathematics
        Type: general
      – SubjectFull: Polynomials
        Type: general
      – SubjectFull: Algebra
        Type: general
    Titles:
      – TitleFull: On the Hierarchy of Intuitionistic Bounded Arithmetic.
        Type: main
  BibRelationships:
    HasContributorRelationships:
      – PersonEntity:
          Name:
            NameFull: MONIRI, MORTEZA
    IsPartOfRelationships:
      – BibEntity:
          Dates:
            – D: 01
              M: 08
              Text: Aug2008
              Type: published
              Y: 2008
          Identifiers:
            – Type: issn-print
              Value: 0955792X
          Numbering:
            – Type: volume
              Value: 18
            – Type: issue
              Value: 4
          Titles:
            – TitleFull: Journal of Logic & Computation
              Type: main
ResultId 1