Recursive Upper Bounds for a Class of L^{n}-Theories

Marko Djordjević

M. Grohe has shown (see [1]) that if n ≥ 3 and the vocabulary of L contains at least one (n − 1)-ary relation symbol then there is no recursive function f such that for all L^{n}-theories T with finite models, min{|M| : M ⊧ T } ≤ f(|S_{n}^{n}(T)|), where S_{n}^{n}(T) is the set of L^{n}-types in n free variables with respect to T. In [2], for every n ≥ 2, a well behaved class of L^{n}-theories (where the vocabulary of L may contain relation symbols of all arities ≤ n), call it T_{n}, is studied. There it is proved that every theory in T_{n} has finite models, and in this talk we show that there exists a recursive function f : ω^{2} → ω such that for every n ≥ 2 and every T ∈ T_{n}, min{|M| : M ⊧ T } ≤ f(n, |S_{n}^{n}(T)|). This result depends heavily on the theory of stable homogeneous structures, a survey of which can be found in [3].

[1] M. Grohe, Large finite structures with few L^{k}-types, Proceedings of the 23rd International Symposium on Mathematical Foundations of Computer Science, Lecture Notes in Computer Science 1450, Springer-Verlag, (1998).

[2] M. Djordjević, Finite variable logic, stability and finite models, to appear in J. Symb. Logic.

[3] A. H. Lachlan, Stable finitely homogeneous structures, a survey, in: B. T. Hart et al. (Eds.) Algebraic Model Theory, Kluwer Academic Publishers (1997), 145-159.

Address: Department of Mathematics, Uppsala University, Box 480, 751 06 Uppsala, Sweden.

E-mail: marko@math.uu.se