Logic in Computer Science (LICS 1997)

Paper: Large finite structures with few L^k-types (at LICS 1997)

Authors: Martin Grohe

Abstract

For each k\ge 3, we show that there is no recursive bound for the size of the smallest finite model of an L^k-theory in terms of its k-size. Here L^k denotes the k-variable fragment of first-order logic. An L^k-theory is a maximal consistent set of L^k-sentences, and the k-size of an L^k-theory is the number of L^k-types realized in its models. Our result answers a question of Dawar. As a corollary, we obtain that for k\ge 3 the so-called L^k-invariants, which characterize structures up to equivalence in L^k, cannot be recursively inverted.

BibTeX

  @InProceedings{Grohe-Largefinitestructur,
    author = 	 {Martin Grohe},
    title = 	 {Large finite structures with few L^k-types},
    booktitle =  {Proceedings of the Twelfth Annual IEEE Symp. on Logic in Computer Science, {LICS} 1997},
    year =	 1997,
    editor =	 {Glynn Winskel},
    month =	 {June}, 
    pages =      {216--227},
    location =   {Warsaw, Poland}, 
    publisher =	 {IEEE Computer Society Press}
  }