Forcing in Finite Structures

DOI10.1002/MALQ.19970430313MaRDI QIDQ4351930zbMATH OpenOpenAlexFDO

Authors Domenico Zambella

Publication date 11 January 1998

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

Full work available at URL https://doi.org/10.1002/malq.19970430313

zbMATH Keywords

bounded arithmeticfinite model theorymodels of arithmeticpigeonhole principle

Mathematics Subject Classification ID

Model theory of finite structures (03C13) Models of arithmetic and set theory (03C62) Second- and higher-order arithmetic and fragments (03F35) Nonstandard models of arithmetic (03H15)

Recommendations

• Typical forcings, NP search problems and an extension of a theorem of Riis
• A new proof of Ajtai's completeness theorem for nonstandard finite structures
• Provability of the pigeonhole principle and the existence of infinitely many primes
• Polynomial size proofs of the propositional pigeonhole principle

Cites work

• An exponential lower bound to the size of bounded depth frege proofs of the pigeonhole principle
• scientific article; zbMATH DE number 806753 (Why is no real title available?)
• scientific article; zbMATH DE number 819737 (Why is no real title available?)
• The independence of the modulo \(p\) counting principles

Cited in

(7)

• Forcing formulas in Fraïssé structures and classes
• Forcing extensions of partial lattices
• Partially definable forcing and bounded arithmetic
• A new proof of Ajtai's completeness theorem for nonstandard finite structures
• scientific article; zbMATH DE number 5130974 (Why is no real title available?)
• scientific article; zbMATH DE number 3926890 (Why is no real title available?)
• scientific article; zbMATH DE number 1107521 (Why is no real title available?)

This page was built for publication: Forcing in Finite Structures

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