An interpretation of S₂^1 in _1b-NIA

MaRDI QIDQ2642795zbMATH OpenFDO

Authors Gilda Ferreira, Isabel Oitavem

Publication date 5 September 2007

Published in Portugaliae Mathematica. Nova Série (Search for Journal in Brave)

Full work available at URL https://eudml.org/doc/53547

Mathematics Subject Classification ID

Relative consistency and interpretations (03F25) First-order arithmetic and fragments (03F30)

Review text

It is shown in the paper that Buss's theory \(S^{1}_{2}\) is interpretable in the Ferreira's theory \(\Sigma^{b}_{1}\)-NIA (originally denoted by \(\Sigma^{b}_{1}\)-PIND). The proof of this fact is for the first time carried out formally.

Recommendations

• scientific article; zbMATH DE number 3972855
• The formalization of interpretability
• scientific article; zbMATH DE number 4087659
• The arithmetics of a theory
• Bounded arithmetic and truth definition

Cited in

(1)

• Bounded theories for polyspace computability

This page was built for publication: An interpretation of \(S_2^1\) in \(\Sigma_1^b\)-NIA

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2642795)