The interplay between certain aspects of interpretability, model theory and category theory

Question

I have some questions about the interplay of interpretability, model theory and category theory. Since I had difficulties in finding literature or other helpful information about this topic, it would be great if somebody of you can help me.

For a first-order theory $T$, let $Mod(T)$ denote the category of all models of $T$ where the arrows are the homomorphisms (or - if you want so - take the elementary embeddings). Let $I_T$ denote the spectrum of $T$. That is, $I_T$ is a function which takes some cardinal $\kappa$ as argument and which outputs the number of non-isomorphic models of $T$ having cardinality $\kappa$. I will also refer to the syntactical notion of interpretability (i.e. "theory $T_1$ interprets theory $T_2$") and mutual interpretability ("$T_1$ interprets $T_2$ and vice versa"). For what follows, assume that $T_1$ and $T_2$ are arbitrary first-order theories. Here are the three questions for which I would like to know whether there are any answers:

1. Are $Mod(T_1)$ and $Mod(T_2)$ equivalent (in the category theoretical sense) whenever $T_1$ and $T_2$ are mutually interpretable? Does the converse holds?

2. Are $Mod(T_1)$ and $Mod(T_2)$ equivalent (in the category theoretical sense) whenever $I_{T_1}=I_{T_2}$? Does the converse holds?

3. Does $I_{T_1}=I_{T_2}$ holds whenever $T_1$ and $T_2$ are mutually interpretable? Does the converse holds?

I will be grateful for any comments, answers and also for references to literature (papers, books,...) in which these questions or similar ones are discussed. Thank you!

Note that I do not expect that these questions are "profound conjectures" or something like that. Maybe that among the experts, their answers are already known and even "trivial". I was just thinking about some model theoretical topics and in this context, the three questions from above started to occupy me. Since I am not able to find any literature concerned with similar questions, I just would like to know whether there are some people in this forum who know more than I do and could share their knowledge with me.

Edit: Following some remarks of some of the commentators of this post, the above questions may also be interesting if we replace "mutual interpretable" with "bi-interpretable".

Answer 1

Here is a negative answer to question 2 and the converse of question 3.

Let $T_1$ be the theory of the integers under successor $\langle\mathbb{Z},S\rangle$. This theory asserts that $S$ is bijective and has no cycles of any finite length. That theory is complete, since all models of size $\aleph_1$ are isomorphic, consisting of $\aleph_1$ many $\mathbb{Z}$-chains, and more generally there is only one model of uncountable size $\kappa$ for any uncountable $\kappa$. But there are countably infinite many countable models up to isomorphism, since every model consists of some countable number of $\mathbb{Z}$-chains. So $I_{T_1}$ is the function that says there are $\aleph_0$ many countably infinite models, but only one model each in any uncountable cardinality.

Let $T_2$ be the theory of infinitely many distinct constants $c_n$. There are countably infinitely many countable models of this theory, depending on the number of objects in the model that are not the interpretation of any $c_n$, but there is only one model up to isomorphism in any uncountable cardinality, since any model of size $\kappa$ has the distinct $c_n$'s and then $\kappa$ many additional points.

Thus, both of these theories have the same number of models in any cardinality: no finite models, $\aleph_0$ many countable models, one model in each uncountable cardinality. So $I_{T_1}=I_{T_2}$.

But $T_1$ is not interpretable in $T_2$, since if it were, the interpretation would involve only finitely many constants, but one can define only finitely many points in a model of the reduct of $T_2$ to those finitely many constants plus one parameter, whereas in any model of $T_1$, we can define infinitely many points relative to any parameter. So this is a counterexample to the converse of question 3.

Note also that $T_1$ has no rigid models, since every $\mathbb{Z}$-chain admits translations, but $T_2$ has two rigid models, namely, the model with only the constants, and the model with the constants plus one more point. (Also, $T_2$ has models with only finitely many automorphisms.) These features show that $\text{Mod}(T_1)$ and $\text{Mod}(T_2)$ are not equivalent as categories, so this provides a negative instance to question 2.

Answer 2

Here is a counterexample to question 3 and an alternative one to its converse. I will also state an observation concerning question 1. (Hopefully, it is all correct.)

Converse of question 3: Assume $ZFC$ is consistent. Then $PA$ is. If I remember correctly, there is a result which states that under these circumstances, $PA$ and $ZFC$ have the same spectrum (namely $I_{ZFC}(\kappa)=I_{PA}(\kappa)=2^{\kappa}$ for all infinite $\kappa$ and $0$ otherwise). If the converse of question 3 would be true, $ZFC$ and $PA$ are mutually interpretable but then, $ZFC$ would prove its own consistency which is in conflict with the 2nd incompleteness theorem.

Question 3: Assume $T_1$ is the theory in the empty language consisting of all valid formulas. So, the only primitive symbol in the formulas of $T_1$ is the equality sign. Assume further that $T_2$ is the theory of single binary relation which is transitive. The language of $T_2$ consists thus of a single binary relation symbol. $T_1$ and $T_2$ are mutually interpretable. The theorems of $T_1$ are send to theorems of $T_2$ via the identity function and the other direction works by interpreting the binary relation as equality. However, $T_1$ is categorical in every power while $T_2$ must have at least two non-isomorphic models in every power (e.g. a model in which the binary relation is empty and another one in which the binary relation coincides with the equality). So, $I_{T_1}\neq I_{T_2}$.

Remarks concerning question 1: Consider again the mutually interpretable theories $T_1$ and $T_2$ of the counterexample to question 3. The corresponding reduct-construction viewed as functors do not establish an equivalence of $Mod(T_1)$ and $Mod(T_2)$ because the one from $Mod(T_2)$ to $Mod(T_1)$ is forgetful and thus maps two non-isomorphic models of $T_2$ which have the same cardinality to two isomorphic models of $T_1$. Note that this does not provide a negative answer to question 1. It only shows that if $Mod(T_1)$ and $Mod(T_2)$ were equivalent, this equivalence cannot be established by the reduct-constructions induced by the interpretations.

Edit: Here is a possible counterexample to question 1 which is based on similar considerations as Joel Hamkins' counterexample to question 2: Let us take the mutually interpretable theories $T_1$ and $T_2$ from my counterexample to question 3 (see above). Note that the only rigid models$^{(\star)}$ of $T_1$ are the models consisting of a single element. In contrast to this, for $T_2$, we can find rigid models in every cardinality, namely models in which the binary relation symbol of $T_2$ is interpreted as being a well-ordering over the corresponding universe$^{(\star\star)}$. For finite cardinalities, it is clear that suchlike models exist and for the infinite case, this holds because of the axiom of choice which we assume here. Thus, there cannot exist a full functor from $Mod(T_2)$ to $Mod(T_1)$ and this rules out the possibility of establishing an equivalence between these categories.

$^{(\star)}$ a rigid model is one for which the identity mapping is the only automorphism.

$^{(\star\star)}$ according to what I have heard here and there, well-ordered structures are always rigid

Answer 3

Regarding the first question:

(a) Theories with equivalent categories of models are not necessarily bi-interpretable. One can come up with simple examples in propositional logic (first-order logic with only zero-place relation symbols). For example, let $T_1$ be the empty theory in the language $\{ p_0,p_1,\dots \}$, and let $T_2$ be the theory with axioms $\{ p_0 \vdash p_i \}$ for all $i$. Both $Mod(T_1)$ and $Mod(T_2)$ are discrete categories with $2^{\aleph _0}$ elements, hence they are equivalent.

(b) Bi-interpetable theories do have equivalent categories of models. This result follows from the fact that an interpretation $F:T_1\to T_2$ gives rise to a functor $F^*:Mod(T_2)\to Mod(T_1)$; and if $T_1$ and $T_2$ are bi-interpretable, then $F$ has a "pseudo-inverse" $G$ which gives rise to a inverse $G^*$ to $F^*$.

The previous paragraph was a bit sketchy. A more elegant argument can be given using categorical logic: the theory $T_i$ gives rise to a syntactic category $C_{T_i}$. If $T_1$ and $T_2$ are bi-interpretable, then the pretopos completion of $C_{T_1}$ is equivalent to the pretopos completion of $C_{T_2}$. It then follows that the category $LF(C_{T_1},Sets)$ of logical functors from $C_{T_1}$ into the category of sets is equivalent to the category $LF(C_{T_2},Sets)$ of logical functors from $C_{T_2}$ into the category of sets. But $LF(C_{T_i},Sets)$ is equivalent to $Mod(T_i)$. [These ideas are all contained in the latter half of Makkai and Reyes, First order categorical logic.]

Note: I am taking "bi-interpretable" as synonymous with "definitional equivalence." Note that mutual interpretability does not imply bi-interpretability. See Andreka et al., "Mutual definability does not imply definitional equivalence, a simple example." http://www.math-inst.hu/pub/algebraic-logic/amn-definote.pdf