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

**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 Symposium on Logic in Computer Science (LICS 1997)}, year = {1997}, month = {June}, pages = {216--227}, location = {Warsaw, Poland}, publisher = {IEEE Computer Society Press} }