Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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".

share|improve this question
1  
For non-experts like me, can you explain what it means for $T_1$ to interpet $T_2$? –  Steven Landsburg Oct 30 '13 at 0:28
    
You may check the article on interpretability in Wikipedia to get a first impression. –  user42061 Oct 30 '13 at 0:50
2  
@StevenLandsburg See here as well. –  Andres Caicedo Oct 30 '13 at 2:53
add comment

3 Answers

up vote 9 down vote accepted

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.

share|improve this answer
    
Thank you for this convincing answer! Concerning questions 2 and 3, I have now a much clearer understanding than before. (Especially concerning your answer to question 2: the problems you demonstrated are in this special case caused by the countably infinite models of $T_2$ which are in some cases rigid. This rules out the possibility of finding a full functor from $Mod(T_2)$ to $Mod(T_1)$ since $T_1$ has no rigid models and thus "too many" homomorphisms in its model class. Is this what you have in mind?) –  user42061 Oct 30 '13 at 12:28
    
Yes, that is exactly what I meant. The existence of rigid models should be revealed in the category of models and will be preserved by equivalence of categories. –  Joel David Hamkins Oct 30 '13 at 13:23
    
I suppose that one could make another counterexample to question 2, by considering $T_1$ and $T_2$ with the maximal number of models in any cardinality, so $I_{T_1}=I_{T_2}$, but where $T_1$ has a prime model and $T_2$ is not complete (hence has no prime model). (There are many examples of this.) The existence of a prime model is a feature of the category, when one uses elementary embeddings as morphisms. –  Joel David Hamkins Oct 30 '13 at 15:05
    
Since you demonstrated that my beginner's questions are not so hard as I have at first believed, I became motivated to think a bit more about them. I think I found a simple counterexample to question 3 and another alternative one to its converse (one which uses the 2nd incompleteness theorem). Moreover, I have some ideas concerning question 1 (namely that there are mutually interpretable theories where the corresponding reducts, viewed as functors, do not on their own establish an equivalence). If you or anyone else is interested in discussing these examples, just answer to this comment. –  user42061 Oct 30 '13 at 22:18
    
@tobi, the recommended practice in this case is simply for you to post another answer to the question, even though it is your own question---it is completely fine to do this. –  Joel David Hamkins Oct 30 '13 at 23:07
add comment

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

share|improve this answer
    
In your example $T_1$ and $T_2$, why are they mutually interpretable? The theory $T_2$ includes the case of all partial orders, a complicated undecidable theory, and this prevents mutual interpretability. –  Joel David Hamkins Oct 31 '13 at 14:38
    
@Joel, maybe that my exposition was misleading. I mean the theory $T_2=\{\forall xyz(Rxy \wedge Ryz \to Rxz)\}$. So, $T_2$ consists just of this single axiom. –  user42061 Oct 31 '13 at 14:40
    
Yes, but this theory $T_2$ has models that are complicated partial orders, and that structure is not definable in any model of $T_1$. So how can we have an interpretation of $T_2$ in $T_1$? –  Joel David Hamkins Oct 31 '13 at 14:44
1  
True. Not every model from $T_2$ can be defined in a model of $T_1$. However, every model of $T_1$ defines some model of $T_2$, namely by defining the relation $R$ as being the identity. And this is what happens here if I am right. For an interpretation, this should suffice. –  user42061 Oct 31 '13 at 14:49
    
I don't think that is right. You need to define a translation from the language of $T_2$ into the language of $T_1$, such that every theorem of $T_2$ is provable about the translations of those theorems in $T_1$, and nothing more. –  Joel David Hamkins Oct 31 '13 at 14:59
show 11 more comments

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.