Generalizations of the Compactness Theorem and Goedel's Completeness Theorem for Nonstandard Finite Structures

摘要

The compactness theorem and Goedel's completeness theorem are perhaps the most important tools of mathematical logic for creating extensions of an existing model of a given theory. Unfortunately none of these theorems hold if we restrict our attention to finite models. In this paper we give generalizations of these theorems which can be used to construct extensions of nonstandard versions of finite structures. Therefore, although the structures are infinite, some finiteness properties will be true both for the original and the extended structures. These types of model extensions are closely related to questions in complexity theory.