There is no recursive link between the k-size of a model and its cardinality Original Research Article

Anuj Dawar poses two questions which give finitary analogies to the Löwenheim–Skolem theorems. Grohe (Proc. of the 12th IEEE Symp. on Logic in Computer Science, 1997), has shown that the first of these, which corresponds to the downward Löwenheim–Skolem theorem, has a negative answer. In this paper we combine Groheʹs technique with that of Robinsonʹs famous paper (Trans. Amer. Math. Soc. (1952)) to show that the second question, which corresponds to the upward Löwenheim–Skolem theorem, also has a negative answer.