Ajtai's Completeness Theorem for Nonstandard Finite Structures
Michal Garl · 2012
Ajtai's generalization of Godel's completeness theorem is a tool that can be used to construct an extension of a given pseudo-nite structure into a model of a given theory. The existence of such model extensions is closely related to questions in complexity theory. In this paper we give a new proof of Ajtai's theorem using basic techniques of model theory.