Types and indiscernibles in finite models (Q4381409)

To analyze the expressive power of first-order logic from the point of view of finite model theory, we need equivalence relations that are coarser than the relation of elementary equivalence. A way is to restrict the number of variables used in formulas of first-order logic by \(k\), the obtained logic is called a finite variable logic and is denoted by \(L^{k}\). The study of classes of finite structures axiomatizable with finitely many variables has importance through connections with computational complexity. The relationship between the size of a finite structure and the number of distinct types it realizes (with respect to \(L^{k}\)) is considered. Some open questions, formulated as finitary Löwenheim-Skolem properties, are presented regarding this relationship. This is also discussed through finitary versions of sets of indiscernibles and of the Ehrenfeucht-Mostowski property. For the entire collection see [Zbl 0884.00035].