Hostname: page-component-586b7cd67f-g8jcs Total loading time: 0 Render date: 2024-11-28T18:29:11.355Z Has data issue: false hasContentIssue false
  • English
  • Français

Finite variable logic, stability and finite models

Published online by Cambridge University Press:  12 March 2014

Marko Djordjević
Marko Djordjević*
Affiliation:
Department of Mathematics, Uppsala University, Box 480, S-75106 Uppsala, Sweden, E-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Extract

We will study complete Ln-theories and their models, where Ln is the set of first order formulas in which at most n distinct variables occur. Here, by a complete Ln-theory we mean a theory such that for every Ln-sentence, it or its negation is implied by the theory. Hence, a complete Ln-theory need not necessarily be complete in the usual sense. Our approach is to transfer concepts and methods from stability theory, such as the order property and counting types, to the context of Ln-theories. So, in one sense, we will develop some rudimentary stability theory for a particular class of (possibly) incomplete theories. To make the ‘stability theoretic’ arguments work, we need to assume that models of the complete Ln-theory T which we consider can be amalgamated in certain ways. If this condition is satisfied and T has infinite models then there will exist models of T which are sufficiently saturated with respect to Ln. This allows us to use some counting types arguments from stability theory. If, moreover, we impose some finiteness conditions on the number of Ln-types and the length of Ln-definable orders then a sufficiently saturated model of T will be ω-categorical and ω-stable. Using the theory of ω-categorical and ω-stable structures we derive that T has arbitrarily large finite models.

A different approach to combining stability theory with finite model theory is made by Hyttinen in [9] and [10].

Type
Research Article
Information
The Journal of Symbolic Logic , Volume 66 , Issue 2 , June 2001 , pp. 837 - 858
Copyright
Copyright © Association for Symbolic Logic 2001

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

REFERENCES

[1]Berthier, D., Stability of non-model-complete theories; products, groups, The Journal of the London Mathematical Society, vol. 11 (1975), pp. 453–464.Google Scholar
[2]Brouwer, A. E., Cohen, A. M., and Neumaier, A., Distance regular graphs, Springer-Verlag, 1989.CrossRefGoogle Scholar
[3]Chang, C. C. and Kiesler, H. J., Model theory, North-Holland, Amsterdam, 1992.Google Scholar
[4]Cherlin, G., Harrington, L., and Lachlan, A. H., ℵ0-categorical, ℵ0-stable structures, Annals of Pure and Applied Logic, vol. 28 (1985), pp. 103–135.CrossRefGoogle Scholar
[5]Dawar, A., Lindell, S., and Weinstein, S., Infinitary logic and inductive definability over finite structures, Information and Computation, vol. 119 (1995), pp. 160–175.CrossRefGoogle Scholar
[6]Eklof, P. and Fisher, E., The elementary theory of abelian groups, Annals of Mathematical Logic. vol. 4 (1972), pp. 115–171.CrossRefGoogle Scholar
[7]Hodges, W., Model theory, Cambridge University Press, 1993.CrossRefGoogle Scholar
[8]Hoffman, A. J. and Singleton, R. R., On Moore graphs with diameters 2 and 3, IBM Journal of Research and Development, vol. 4 (1960), pp. 497–504.CrossRefGoogle Scholar
[9]Hyttinen, T., On stability in finite models, to appear in Archive for Mathematical Logic.CrossRefGoogle Scholar
[10]Hyttinen, T., Forking in finite models, Manuscript.Google Scholar
[11]Immerman, N., Upper and lower bounds for first-order expressibility, Journal of Computer and Systems Sciences, vol. 25 (1982), pp. 76–98.CrossRefGoogle Scholar
[12]Poizat, B., Deux ou trois choses que jesaisde Ln, The Journal of Symbolic of Logic, vol. 47 (1982), pp. 641–658.CrossRefGoogle Scholar
[13]Shelah, S., Stability, the f.c.p. and superstability; model theoretic properties offormulas in first-order theories, Annals of Mathematical Logic, vol. 3 (1971), pp. 271–362.CrossRefGoogle Scholar
[14]Shelah, S., The lazy model-theoretician's guide to stability, Logique et Analyse, vol. 18 (1975), pp. 235–308.Google Scholar
[15]Shelah, S., Classification theory, North-Holland, Amsterdam, 1990.Google Scholar