Is there a difference between computable model theory and computable structure theory?

Question

I have the seen the books/notes with both titles and there seems to be quite some overlap, but I'm not sure if people in the field view them as having slightly different focuses.

Answer 1

These are indeed different, although related, subjects.

---

"Computable model theory" should be thought of as analogous to "computable algebra" or "computable topology" or similar; we start with classical model theory, in particular the study of complete first-order theories, and see how things change when we introduce computability-theoretic restrictions. Note that there are many choices to make here; for example, do we want to look at computable or decidable structures, and do we care about computable isomorphism or merely classical isomorphism? Millar's article Foundations of recursive model theory is old, but still a good starting point for this in my opinion. Alternatively, see volume 1 of the Handbook of Recursive Mathematics.

---

By contrast, the "paradigmatic starting question" in computable structure theory is quite different:

Suppose we have a countable structure $\mathfrak{A}$ and a relation $R$ on $\mathfrak{A}$. How is the logical complexity of $R$ in $\mathfrak{A}$ related to the "worst-case-computability-theoretic" complexity of $R$ across copies of $\mathfrak{A}$?

This is one of those questions which is tricky to even understand before knowing the answer. I'll just jump straight to (one of) the punchline(s):

The following are equivalent:

• For every copy $\mathcal{A}$ of $\mathfrak{A}$, the relation $R^\mathcal{A}$ is c.e. relative to $\mathcal{A}$.

• $R$ is computably infinitarily existentially (= "$\Sigma_1^c$") definable in $\mathfrak{A}$.

Let me explain what this means. A "copy" of a (countable) structure is an isomorphic structure with domain $\mathbb{N}$. Each copy $\mathcal{A}$ of $\mathfrak{A}$ comes with its own notion of "computable relative to me" (note that unless $\mathfrak{A}$ is really really boring, it will have continuum-many copies, so most copies of $\mathfrak{A}$ will be noncomputable objects even if $\mathfrak{A}$ is very nice). Meanwhile, $\Sigma_1^c$ is a particular fragment of infinitary logic $\mathcal{L}_{\infty,\omega}$. The point of this theorem - a special case of the Ash/Knight/Manasse/Slaman/Chisholm theorem - is that we've given a connection between computability-theoretic properties and syntax (in some appropriate logic); compare this with \L{}os/Tarski-style preservation theorems, which similarly link algebraic properties and syntactic structure.

The important point here is that the logic $\mathcal{L}_{\infty,\omega}$ wasn't necessarily of interest at the outset; it emerged as important because it turned out to give a characterization of the computability-theoretic properties ("complexity across all copies") which we started looking at. Other logics could in principle play similar roles, although none so far has (that's not quite right, technically, but Grilliot's theorem along similar lines - see Dissecting abstract recursion - never had the same impact). Contrast this with computable model theory, where first-order logic was in some sense the "true" object of study, we were just using computability theory as an additional lens through which to view it.

The standard sources on computable structure theory are Ash/Knight's Computable structures and the hyperarithmetic hierarchy and more recently Montalb'an's two-volume treatise (available at his website).

---

Of course the lines between subjects are really just social convention, and there's lots of points where computable model and structure theory blend together. The simplest test question I can think of is about focus: does (classical) first-order logic play a central role? If the answer is yes, you're probably looking at computable model theory; if the answer is no, it's probably computable structure theory.