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.