• TUCS Publication Series
• How to Publish in TUCS Series
• Publication Search
• Publication Graph
• Publication Input
• Publication Input Guide
• JuFo Browser

Decidable Formulas of Intuitionistic Primitive Recursive Arithmetic

Saeed Salehi, Decidable Formulas of Intuitionistic Primitive Recursive Arithmetic. Reports on Mathematical Logic 36, 55–61, 2002.

Abstract:

By formalizing some classical facts about provably total functions of intuitionistic primitive recursive arithmetic ($iPRA$), we prove that the set of decidable formulas of $iPRA$ and of $i\Sigma_1^+$ (intuitionistic $\Sigma_1$-induction in the language of $PRA$) coincides with the set of its provably $\Delta_1$-formulas and coincides with the set of its provably atomic formulas. By the same methods, we shall give another proof of a theorem of Markovi\'{c} and \mbox{ De Jongh}: the decidable formulas of $HA$ are its provably $\Delta_1$-formulas.

BibTeX entry:

@ARTICLE{jSalehi02a,
  title = {Decidable Formulas of Intuitionistic Primitive Recursive Arithmetic},
  author = {Salehi, Saeed},
  journal = {Reports on Mathematical Logic},
  volume = {36},
  pages = {55–61},
  year = {2002},
}

Belongs to TUCS Research Unit(s): FUNDIM, Fundamentals of Computing and Discrete Mathematics

Publication Forum rating of this publication: level 1

Edit publication