Premium
Forcing in Finite Structures
Author(s) -
Zambella Domenico
Publication year - 1997
Publication title -
mathematical logic quarterly
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.473
H-Index - 28
eISSN - 1521-3870
pISSN - 0942-5616
DOI - 10.1002/malq.19970430313
Subject(s) - pigeonhole principle , mathematics , forcing (mathematics) , simple (philosophy) , independence (probability theory) , discrete mathematics , combinatorics , mathematical analysis , statistics , epistemology , philosophy
We present a simple and completely model‐theoretical proof of a strengthening of a theorem of Ajtai: The independence of the pigeonhole principle from I Δ 0 ( R ). With regard to strength, the theorem proved here corresponds to the complexity/proof‐theoretical results of [10] and [14], but a different combinatorics is used. Techniques inspired by Razborov [11] replace those derived from Håstad [8]. This leads to a much shorter and very direct construction.