Hostname: page-component-cd9895bd7-hc48f Total loading time: 0 Render date: 2024-12-22T14:36:52.965Z Has data issue: false hasContentIssue false
  • English
  • Français

Some Aspects of Model Theory and Finite Structures

Published online by Cambridge University Press:  15 January 2014

Eric Rosen
Eric Rosen*
Affiliation:
Department of Mathematics, Statistics and Computer Science, University of Illinoisat Chicago, Chicago, IL 60607, USA, E-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Extract

Model theory is concerned mainly, although not exclusively, with infinite structures. In recent years, finite structures have risen to greater prominence, both within the context of mainstream model theory, e.g., in work of Lachlan, Cherlin, Hrushovski, and others, and with the advent of finite model theory, which incorporates elements of classical model theory, combinatorics, and complexity theory. The purpose of this survey is to provide an overview of what might be called the model theory of finite structures. Some topics in finite model theory have strong connections to theoretical computer science, especially descriptive complexity theory (see [26, 46]). In fact, it has been suggested that finite model theory really is, or should be, logic for computer science. These connections with computer science will, however, not be treated here.

It is well-known that many classical results of ‘infinite model theory’ fail over the class of finite structures, including the compactness and completeness theorems, as well as many preservation and interpolation theorems (see [35, 26]). The failure of compactness in the finite, in particular, means that the standard proofs of many theorems are no longer valid in this context. At present, there is no known example of a classical theorem that remains true over finite structures, yet must be proved by substantially different methods. It is generally concluded that first-order logic is ‘badly behaved’ over finite structures.

From the perspective of expressive power, first-order logic also behaves badly: it is both too weak and too strong. Too weak because many natural properties, such as the size of a structure being even or a graph being connected, cannot be defined by a single sentence. Too strong, because every class of finite structures with a finite signature can be defined by an infinite set of sentences. Even worse, every finite structure is defined up to isomorphism by a single sentence. In fact, it is perhaps because of this last point more than anything else that model theorists have not been very interested in finite structures. Modern model theory is concerned largely with complete first-order theories, which are completely trivial here.

Type
Research Article
Information
Bulletin of Symbolic Logic , Volume 8 , Issue 3 , September 2002 , pp. 380 - 403
Copyright
Copyright © Association for Symbolic Logic 2002

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] Ajtai, M. and Gurevich, Y., Monotone versus positive, Journal of the ACM, vol. 34 (1987), pp. 1004–1015.CrossRefGoogle Scholar
[2] Ajtai, M. and Gurevich, Y., Datalog vs first-order logic, Journal of Computer and System Sciences, vol. 49 (1994), pp. 562–58.Google Scholar
[3] Alechina, N. and Gurevich, Y., Syntax vs. semantics on finite structures, Structures in logic and computer science. A selection of essays in honor of A. Ehrenfeucht (Mycielski, J., Rozenberg, G., and Salomaa, A., editors), LNCS, vol. 1261, Springer-Verlag, 1997, pp. 14–33.Google Scholar
[4] Andréka, H., van Benthem, J., and Németi, I., Modal languages and bounded fragments of predicate logic, 1996, ILLC Research Report ML–96–03.Google Scholar
[5] Baldwin, J. T., Theories in finite model theory, 1999, preprint.Google Scholar
[6] Baldwin, J. T. and Lessmann, O., Amalgamation properties and finite models in Ln-theories, Archive for Mathematical Logic, vol. 41 (2002), pp. 155–167.Google Scholar
[7] Baldwin, J. T. and Shelah, S., Randomness and semigenericity, Transactions of the American Mathematical Society, vol. 349 (1997), pp. 1359–1376.CrossRefGoogle Scholar
[8] Baldwin, J. T. and Shi, N., Stable generic structures, Annals of Pure and Applied Logic, vol. 79 (1996), pp. 1–35.Google Scholar
[9] Barker, R., A proof that there is no recursive link between the k-size of a model and its cardinality, 2000, preprint.Google Scholar
[10] van Benthem, J., Modal logic and classical logic, Bibliopolis, 1983.Google Scholar
[11] Birkhoff, G., On the structure of abstract algebras, Proc. Camb. Phil. Soc., vol. 31 (1935), pp. 433–454.Google Scholar
[12] Börger, E., Grädel, E., and Gurevich, Y., The classical decision problem, Springer-Verlag, 1997.CrossRefGoogle Scholar
[13] Chang, C. C. and Keisler, H. J., Model theory, 3rd ed., North-Holland, 1990.Google Scholar
[14] Chatzidakis, Z., Model theory of finite fields and pseudo-finite fields, Annals of Pure and Applied Logic, vol. 88 (1997), pp. 95–108.Google Scholar
[15] Chatzidakis, Z., van den Dries, L., and Macintyre, A., Definable sets over finite fields, Journal für die Reine und Angewandte Mathematik, vol. 427 (1992), pp. 107–135.Google Scholar
[16] Cherlin, G., Theories categorical in power n + 2, Discrete Mathematics, to appear.Google Scholar
[17] Cherlin, G., Large finite structures with few types, Algebraic model theory (Hart, B. T., Lachlan, A. H., and Valeriote, M. A., editors), Kluwer Academic Publishers, 1997, pp. 53–105.Google Scholar
[18] Cherlin, G., Sporadic homogeneous structures, The Gelfand Mathematical Seminars, Birkhäuser, 2000, pp. 15–48.Google Scholar
[19] Cherlin, G. and Felgner, U., Homogeneous finite groups, Journal of the London Mathematical Society (2), vol. 62 (2000), pp. 784–794.Google Scholar
[20] Cherlin, G., Harrington, L., and Lachian, A. H., ℵ0-categorical, ℵ0-stable structures, Annals of Pure and Applied Logic, vol. 28 (1985), pp. 103–135.CrossRefGoogle Scholar
[21] Compton, K., Some useful preservation theorems, The Journal of Symbolic Logic, vol. 48 (1983), pp. 427–440.Google Scholar
[22] Dawar, A., Types and indiscernibles in fnite models, Logic Colloquium '95 (Makowsky, J. and Ravve, E., editors), Springer-Verlag, 1998, pp. 51–65.Google Scholar
[23] Dawar, A., Lindell, S., and Weinstein, S., Infnitary logic and inductive defnability over fnite structures, Information and Computation, vol. 119 (1994), pp. 160–175.Google Scholar
[24] Djordjević, M., Finite variable logic and homogeneous structures, 2000, preprint.Google Scholar
[25] Djordjević, M., Finite variable logic, stability and finite models, The Journal of Symbolic Logic, vol. 66 (2001), pp. 837–858.Google Scholar
[26] Ebbinghaus, H.-D. and Flum, J., Finite model theory, Springer-Verlag, 1995.Google Scholar
[27] Fagin, R., Probabilities on fnite models, The Journal of Symbolic Logic, vol. 41 (1976), pp. 50–58.Google Scholar
[28] Felgner, U., Pseudo-endliche Gruppen, Seminarber., Humboldt-Univ. Berlin, Sekt. Math., vol. 110 (1990), pp. 82–96.Google Scholar
[29] Gardiner, A., Homogeneous graphs, Journal of Combinatorial Theory. Series B., vol. 20 (1976), pp. 94–102.Google Scholar
[30] Glebskiĭ, Ju.V., Kogan, D. I., Liogonkiĭ, M. I., and Talanov, V. A., Volume and fraction of satisfiability of formulas of the lower predicate calculus, Kibernetika (Kiev), vol. 2 (1969), pp. 17–27, (Russian).Google Scholar
[31] Grädel, E. and McColm, G., Hierarchies in transitive closure logic, stratifed Datalog and infnitary logic, Annals of Pure and Applied Logic, vol. 77 (1996), pp. 166–199.CrossRefGoogle Scholar
[32] Grädel, E. and Rosen, E., On preservation theorems for two-variable logic, Mathematical Logic Quarterly, vol. 45 (1999), pp. 315–325.CrossRefGoogle Scholar
[33] Grohe, M., Existential least fxed-point logic and its relatives, Journal of Logic and Computation, vol. 7 (1997), pp. 205–228.Google Scholar
[34] Grohe, M., Finite variable logics in descriptive complexity theory, this Bulletin, vol. 4 (1998), pp. 345–398.Google Scholar
[35] Gurevich, Y., Toward logic tailored for computational complexity, Computation and proof theory (Richter, M. M. et al., editors), Lecture Notes in Mathematics, vol. 1104, Springer-Verlag, 1984, pp. 175–216.Google Scholar
[36] Herwig, B., Extending partial isomorphisms on fnite structures, Combinatorica, vol. 115 (1995), pp. 365–371.Google Scholar
[37] Herwig, B., Extending partial isomorphisms for the small index property of many co-categorical structures, Israel Journal of Mathematics, vol. 107 (1997), pp. 93–123.CrossRefGoogle Scholar
[38] Herwig, B. and Lascar, D., Extending partial isomorphisms and the profnite topology on free groups, Transactions of the American Mathematical Society, vol. 352 (2000), pp. 1985–2021.Google Scholar
[39] Hodges, W., Finite extensions and fnite groups, Models and sets (Aachen, 1983) (Müller, G. H. and Richter, M. M., editors), Lecture Notes in Mathematics, vol. 1103, Springer-Verlag, 1984, pp. 193–206.CrossRefGoogle Scholar
[40] Hodges, W., Model theory, Cambridge University Press, 1993.Google Scholar
[41] Hodges, W., Hodkinson, I., Lascar, D., and Shelah, S., The small index property for ω-categorical ω-stable structures andfor the random graph, Journal of the London Mathematical Society (2), vol. 48 (1993), pp. 204–218.Google Scholar
[42] Hrushovski, E., Extending partial isomorphisms of graphs, Combinatorica, vol. 12 (1992), pp. 411–416.Google Scholar
[43] Hrushovski, E., A stable ℵ0-categorical pseudoplane, 1998, preprint.Google Scholar
[44] Hyttinen, T., Forking in finite models, 1999, preprint.Google Scholar
[45] Hyttinen, T., On stability in finite models, Archive for Mathematical Logic, vol. 39 (2000), pp. 89–102.Google Scholar
[46] Immerman, N., Descriptive complexity, Springer-Verlag, 1998.Google Scholar
[47] Immerman, N. and Kozen, D., Definability with bounded number of bound variables, Information and Computation, vol. 83 (1989), pp. 121–139.CrossRefGoogle Scholar
[48] Keisler, H. J. and Walkoe, W. Jr., The diversity of quantifier prefixes, The Journal of Symbolic Logic, vol. 38 (1973), pp. 79–85.Google Scholar
[49] Kim, B. and Pillay, A., From stability to simplicity, this Bulletin, vol. 4 (1998), pp. 17–36.Google Scholar
[50] Kolaitis, Ph., Implicit definability on finite structures and unambiguous computations, Proceedings of 5th IEEE Symposium on Logic in Computer Science, 1990, pp. 168–180.Google Scholar
[51] Lachlan, A. H., Homogeneous structures, Proceedings of the ICM 1986 (Gleason, A., editor), American Mathematical Society, 1987, pp. 314–321.Google Scholar
[52] Lachlan, A. H., Stable finitely homogeneous structures a survey, Algebraic model theory (Hart, B. T., Lachlan, A. H., and Valeriote, M. A., editors), Kluwer Academic Publishers, 1997, pp. 145–159.Google Scholar
[53] Lachlan, A. H. and Tripp, A., Finite homogeneous 3-graphs, Mathematical Logic Quarterly, vol. 41 (1995), pp. 287–306.Google Scholar
[54] Lessmann, O., Simple theories in finite variable logic, 2000, preprint.Google Scholar
[55] Lyndon, R. C., An interpolation theorem in the predicate calculus, Pacific Journal of Mathematics, vol. 9 (1959), pp. 129–142.Google Scholar
[56] Lyndon, R. C., Properties preserved under homomorphism, Pacific Journal of Mathematics, vol. 9 (1959), pp. 143–154.Google Scholar
[57] Macpherson, D., Finite axiomatizability and theories with trivial algebraic closure, Notre Dame Journal of Formal Logic, vol. 32 (1991), pp. 188–192.Google Scholar
[58] Poizat, B., Deux ou trois choses que je sais de Ln , The Journal of Symbolic Logic, vol. 47 (1982), pp. 641–658.Google Scholar
[59] Robinson, A., Introduction to model theory and to the metamathematics of algebra, North-Holland, 1963.Google Scholar
[60] Rosen, E., Finite model theory and finite variable logic, Ph.D. thesis , University of Pennsylvania, 1995.Google Scholar
[61] Rosen, E., Modal logic over finite structures, Journal of Logic, Language and Information, vol. 6 (1997), pp. 427–439.Google Scholar
[62] Rosen, E., On the first-order prefix hierarchy, 1998, preprint.Google Scholar
[63] Rosen, E., Shelah, S., and Weinstein, S., k-universal graphs, Logic and random structures, American Mathematical Society, 1997, pp. 65–77.Google Scholar
[64] Rosen, E. and Weinstein, S., Preservation theorems in finite model theory, Logic and computational complexity (Leivant, D., editor), LNCS, vol. 960, Springer-Verlag, 1995, pp. 480–502.Google Scholar
[65] Saracino, D. and Wood, C., Homogeneous finite rings in characteristic 2n , Annals of Pure and Applied Logic, vol. 40 (1988), pp. 11–28.Google Scholar
[66] Shelah, S. and Spencer, J., Zero-one laws for sparse random graphs, Journal of the American Mathematical Society, vol. 1 (1988), pp. 97–115.Google Scholar
[67] Shoenfield, J., Mathematical logic, Addison-Wesley, 1967.Google Scholar
[68] Stolboushkin, A., Finite monotone properties, Proceedings of 10th IEEE Symposium on Logic in Computer Science, 1995, pp. 324–330.Google Scholar
[69] Tait, W. W., A counterexample to a conjecture of Scott and Suppes, The Journal of Symbolic Logic, vol. 24 (1959), pp. 15–16.Google Scholar
[70] Thomas, S., Theories with finitely many models, The Journal of Symbolic Logic, vol. 51 (1986), pp. 374–376.Google Scholar
[71] Walkoe, W. Jr., Finite partially-ordered quantification, The Journal of Symbolic Logic, vol. 35 (1970), pp. 535–555.Google Scholar
[72] Wilson, J. S., On simple pseudofinite groups, Journal of the London Mathematical Society (2), vol. 51 (1995), pp. 471–490.Google Scholar
[73] Zilber, B., Totally categorical theories; structural properties and non-finite axiomatizability, Proceedings: Model Theory of Algebra and Arithmetic (Pacholski, L. et al., editors), 1979, pp. 381–410.Google Scholar