Preservation theorems for bounded formulas

DOI10.1007/S00153-006-0016-0MaRDI QIDQ866887zbMATH OpenOpenAlexFDO

Authors Morteza Moniri

Publication date 14 February 2007

Published in Archive for Mathematical Logic (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00153-006-0016-0

zbMATH Keywords

Kripke modelNPBounded arithmeticQuantifier eliminationIntuitionistic logicModel completenessPolynomial hierarchyPolynomial inductionUniversal theory

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) First-order arithmetic and fragments (03F30) Models of arithmetic and set theory (03C62) Quantifier elimination, model completeness, and related topics (03C10)

Recommendations

• An Independence Result for Intuitionistic Bounded Arithmetic
• scientific article; zbMATH DE number 999649
• scientific article; zbMATH DE number 176198
• Two General Results on Intuitionistic Bounded Theories
• Polynomial induction and length minimization in intuitionistic bounded arithmetic

Cites work

• scientific article; zbMATH DE number 432703 (Why is no real title available?)
• scientific article; zbMATH DE number 4059391 (Why is no real title available?)
• scientific article; zbMATH DE number 176198 (Why is no real title available?)
• scientific article; zbMATH DE number 1215494 (Why is no real title available?)
• scientific article; zbMATH DE number 1007358 (Why is no real title available?)
• scientific article; zbMATH DE number 819737 (Why is no real title available?)
• scientific article; zbMATH DE number 227056 (Why is no real title available?)
• Bounded arithmetic and the polynomial hierarchy
• Comparing Constructive Arithmetical Theories Based on NP-PIND and coNP-PIND
• Constructivism in mathematics. An introduction. Volume II
• Functional interpretations of feasibly constructive arithmetic
• Interpreting classical theories in constructive ones
• Polynomial induction and length minimization in intuitionistic bounded arithmetic
• Provably total functions of intuitionistic bounded arithmetic
• Saturated models of universal theories

Cited in

(2)

• Preservation theorems in finite model theory
• Models of Bounded Arithmetic Theories and Some Related Complexity Questions

This page was built for publication: Preservation theorems for bounded formulas

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