Forcing in Finite Structures
Domenico Zambella · Mathematical logic quarterly · 1997
Abstract We present a simple and completely model‐theoretical proof of a strengthening of a theorem of Ajtai: The independence of the pigeonhole principle fromIΔ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.