Forcing in Finite Structures

DOI10.1002/MALQ.19970430313zbMATH Open0880.03020OpenAlexW2115500515MaRDI QIDQ4351930FDOQ4351930

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

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

zbMATH Keywords

finite model theorybounded arithmeticmodels of arithmeticpigeonhole principle

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• The independence of the modulo \(p\) counting principles
• An exponential lower bound to the size of bounded depth frege proofs of the pigeonhole principle
• Title not available (Why is that?)

Cited In (7)

• Title not available (Why is that?)
• A new proof of Ajtai's completeness theorem for nonstandard finite structures
• Partially definable forcing and bounded arithmetic
• Forcing extensions of partial lattices
• Title not available (Why is that?)
• Title not available (Why is that?)
• Forcing formulas in Fraïssé structures and classes

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)