“School of Mathematics”

Back to Papers Home
Back to Papers of School of Mathematics

Paper   IPM / M / 2336
School of Mathematics
  Title:   Comparing constructive arithmetical theories based on NP-PIND and coNP-PIND
  Author(s):  Mor. Moniri
  Status:   Published
  Journal: J. Logic Comput.
  No.:  6
  Vol.:  13
  Year:  2003
  Pages:   881-888
  Supported by:  IPM
  Abstract:
In this note we show that the intuitionistic theory of polynomial induction on Π1b+-formulas does not imply the intuitionistic theory IS21 of polynomial induction on Σ1b+-formulas. We also show the converse assuming the Polynomial Hierarchy does not collapse. Similar results hold also for length induction in place of polynomial induction. We also investigate the relation between various other intuitionistic first-order theories of bounded arithmetic. Our method is mostly semantical, we use Kripke models of the theories.

Download TeX format
back to top
Clients Logo
Clients Logo
Clients Logo
Clients Logo
Clients Logo
Clients Logo
Clients Logo
Clients Logo
scroll left or right