Preservation theorems for bounded formulas

DOI10.1007/s00153-006-0016-0zbMath1112.03021OpenAlexW2064470584MaRDI QIDQ866887

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

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

Related Items

Models of Bounded Arithmetic Theories and Some Related Complexity Questions

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Functional interpretations of feasibly constructive arithmetic
• Bounded arithmetic and the polynomial hierarchy
• Constructivism in mathematics. An introduction. Volume II
• Saturated models of universal theories
• Interpreting classical theories in constructive ones
• Polynomial induction and length minimization in intuitionistic bounded arithmetic
• Provably total functions of intuitionistic bounded arithmetic
• Comparing Constructive Arithmetical Theories Based on NP-PIND and coNP-PIND