Forcing in Finite Structures (revised version of ML-1996-02)
Domenico Zambella

Abstract:
We present a simple and completely model­theoretical proof of a strengthening 
of a theorem of Ajtai's: the independence of the pigeonhole principle from 
I-\Delta_0(R). Qua 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 Hastad [8]. This leads to a much shorter and very direct
construction.

Mathematics Subject Classification. 03C62, 03F35 and 03H15.
Keywords: Models of atithmetic, bounded arithmetic, finite model theory.