Construction of models of bounded arithmetic by restricted reduced powers

DOI10.1007/s00153-016-0484-9zbMath1380.03070OpenAlexW2341717488MaRDI QIDQ506954

Michal Garlík

Publication date: 2 February 2017

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

Full work available at URL: https://doi.org/10.1007/s00153-016-0484-9

zbMATH Keywords

ultraproductbounded arithmeticsharply bounded collection

Mathematics Subject Classification ID

First-order arithmetic and fragments (03F30) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Nonstandard models of arithmetic (03H15) Ultraproducts and related constructions (03C20)

Related Items

On the finite axiomatizability of ⋮ A remark on pseudo proof systems and hard instances of the satisfiability problem ⋮ Polynomial time ultrapowers and the consistency of circuit lower bounds

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Non-standard models of Peano arithmetic
• Arithmetizing uniform \(NC\)
• Bounded arithmetic for NC, ALogTIME, L and NL
• A new proof of Ajtai's completeness theorem for nonstandard finite structures
• Nondeterministic polynomial-time computations and models of arithmetic
• The strength of replacement in weak arithmetic
• Generalizations of the Compactness Theorem and Gödel’s Completeness Theorem for Nonstandard Finite Structures