A Sketch of the Proof that There is no Recursive Link Between the k-size of a Model and its Cardinality

Russell Barker

In this talk I shall introduce the notion of L^{k} , the fragment of first order logic which contains variables x_{1}, …, x_{k}, k-size and k-equivalence. Then I shall go on to use these tools to present two ideas conjectured by Anuj Dawar [1] which give finitary analogies to the Löwenheim-Skolem theorems. After this I will introduce the notions of diophantine and unary-exponential diophantine equations and give some results about these. Later a sketch refutation of Dawar’s first conjecture, which is due to Martin Grohe [2], will be presented. This refutation involves building a translation from systems of diophantine equations into specific kinds of L^{k} theories called scales and then using a theorem of Matijasevic [3] to show that the desired result is impossible. Finally, I shall extend Grohe’s proof, using the notions of unary exponential diophantine equations and exponentiation scales, and then use another of Matijasevic’s theorems [4] to show that Dawar’s second conjecture is also false.

[1] A. Dawar, Type and indiscernables in finite models, Logic Colloquium ’95, 1998.

[2] M. Grohe, Large finite models with small lk-types, in Proceedings of the 12th IEEE symposium on Logic in Computer Sciences, 1997.

[3] J.V. Matiyasevic, Enumerable set are diophantic, Soviet Mathematics Doklady, 1970.

[4] J.V. Matiyasevic, The existance of non-effectizable estimates in the theory of exponential diophantine equations, Journal of Soviet Mathematics, 1974.

Address: Mathematical Institute, University of Oxford, 24-29 St Giles, Oxford, OX1 3LB,UK