# The differences between Model Theory and Computation Theory

Model Theory seems more interested with Gödel's completeness theorem, Tarski' quantifier elimination and logic systems that Turing computability and Church recursivity.

However, both theories overlap significantly.

Are there differences between both theories or is one term the mathematical term while the other is the computer science term?

• Quantifier elimination is syntax; it is strange to see it listed as a topic of semantics. – user14972 Jun 6 '14 at 21:07
• Can you provide some examples of what you mean by "both theories overlap significantly"? – Alex Kruckman Jun 6 '14 at 23:33

In a slogan, we might say (without being too misleading) that computability theory is about the finite, model theory mostly about the infinite -- a rather big difference!

In a bit more detail, computability theory is about what can and can't be done by algorithms -- at least in the basic, original sense, these are finite sets of instructions for operating on finitely specifiable data (natural numbers, or stuff that can be coded up using natural numbers, like finite strings of symbols). So computability theory starts by showing the equivalence of various sharpenings of that intuitive idea (e.g. the Turing and the Gödel-Herbrand and the Kleene characterisations of computability come to the same). And proceeds to prove limitative results about what can't be computed. And then proceeds to fancier stuff about computational complexity, etc etc.

Model theory is about the relationship between theories (bunches of sentences) and their models in which they are true -- typically, in the interesting cases (at least at the outset), these are infinite structures. And we are interested in results like the Gödel completeness theorem (syntactically consistent sets of first-order sentences always have a model), the upward and downward Löwenheim-Skolem theorem (if you have an uncountably infinite model, you'll have bigger infinite models, and smaller countably infinite models). And so it goes. Very different issues.

• Do you mean recursion theory ? – Rene Schipperus Jun 6 '14 at 22:16

You are referring to the basic aspects of model theory, modern model theory is concerned with classifying the models of a (usually complete) theory and then of classifying theories themselves as to how their models behave, ultimately it has become closer to algebraic geometry, than to recursion theory.

Model theory is about the existence of objects that "witness" mathematical theories. Various facts about a theory can be drawn from the existence of a so-called model. Models can be analyzed as objects in their own right. Every sort of logic has its own sort of model.

"Computability theory" is the study of various sorts of logics that, intuitively, capture the notion of what finite computation means. Each of these logics will have its own kind of model. And the vocabulary used to describe these models might be the same as the vocabulary used in model theory. But that's about as far as the relationship goes.