There is no recursive link between the \(k\)-size of a model and its cardinality (Q1861532): Difference between revisions

Denote by \(\text{FO}^k\) the fragment of first-order logic in which only the variables \(x_1,\dots,x_k\) occur. For a finite structure \({\mathcal A}\), let \(k\)-size\(({\mathcal A})\) be the number of distinct \(\text{FO}^k\)-types satisfied in \({\mathcal A}\). In 1995, Anuj Dawar asked if the following upper Löwenheim-Skolem property holds: Is there, for every \(k\), a recursive function \(g_k\) such that if \({\mathcal B}\) is a finite structure of cardinality \(\geq g_k(n)\) with \(k\)-size\(({\mathcal B})\leq n\), then there are arbitrarily large finite structures \(\text{FO}^k\)-equivalent to \({\mathcal B}\)? The author shows that this question has a negative answer.