Forcing in Finite Structures

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.