Large finite structures with few L/sup κ/-types
Martin Grohe · 2002
Far each /spl kappa//spl ges/3, we show that there is no recursive bound for the size of the smallest finite model of an L/sup /spl kappa//-theory in terms of its /spl kappa/-size. Here L/sup /spl kappa// denotes the /spl kappa/-variable fragment of first-order logic. An L/sup /spl kappa//-theory is a maximal consistent set of L/sup /spl kappa//-sentences, and the /spl kappa/-size of an L/sup /spl kappa//-theory is the number of L/sup /spl kappa//-types realized in its models. Our result answers a question of Dawar (1993). As a corollary, we obtain that for /spl kappa//spl ges/3 the so-called L/sup /spl kappa//-invariants, which characterize structures up to equivalence in L/sup /spl kappa//, cannot be recursively inverted.