✦ LIBER ✦

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

✍ Scribed by R. Barker

Publisher: Elsevier Science
Year: 2002
Tongue: English
Weight: 141 KB
Volume: 118
Category: Article
ISSN: 0168-0072
DOI: 10.1016/s0168-0072(02)00039-8

No coin nor oath required. For personal study only.

✦ Synopsis

Anuj Dawar poses two questions which give ÿnitary analogies to the L owenheim-Skolem theorems. Grohe (Proc. of the 12th IEEE Symp. on Logic in Computer Science, 1997), has shown that the ÿrst of these, which corresponds to the downward L owenheim-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 owenheim-Skolem theorem, also has a negative answer.