Interpretations

(This started as an answer on Math.Stackexchange. This version has been lightly edited and expanded. Also posted at fff.)

Throughout this post, theory means first-order theory. In fact, we are concerned with theories that are recursively presented, though the abstract framework applies more generally. Thanks to Fredrik Engström Ellborg for suggesting in Google+ the reference Kaye-Wong, and to Ali Enayat for additional references and many useful conversations on this topic.

Informally, to say that a theory $T$ interprets a theory $S$ means that there is a procedure for associating structures $\mathcal N$ in the language of $S$ to structures $\mathcal M$ in the language of $T$ in such a way that if $\mathcal M$ is a model of $T$ , then $\mathcal N$ is a model of $S$ .

Let us be a bit more precise, and do this syntactically to reduce the requirements of the metatheory. The original notion is due to Tarski, see

Alfred Tarski. Undecidable theories. In collaboration with Andrzej Mostowski and Raphael M. Robinson. Studies in Logic and the Foundations of Mathematics. North-Holland Publishing Company, Amsterdam, 1953. MR0058532 (15,384h).

I follow here the modern reference on interpretations,

Albert Visser, Categories of theories and interpretations, in Logic in Tehran, Lecture Notes in Logic, vol. 26, Association for Symbolic Logic, La Jolla, CA, 2006, pp. 284–341. MR2262326 (2007j:03083).

One can take “the theory $T$ interprets the theory $S$ ” to mean that there are

A map $i$ that assigns formulas in the language of $T$ to the symbols of the language $\mathcal L$ of $S$ , and
A formula $\mathrm{Dom}(x)$ in the language of $T$ ,

with the following properties: We can extend $i$ to all $\mathcal L$ -formulas recursively: $i(\phi\land\psi)=i(\phi)\land i(\psi)$ , etc, and $i(\forall x\phi)=\forall x(\mathrm{Dom}(x)\to i(\phi))$ . It then holds that $T$ proves

$\exists x\,\mathrm{Dom}(x)$ , and
$i(\phi)$ for each axiom $\phi$ of $S$ (including the axioms of first-order logic).

Here, $T,S$ are taken to be recursive, and so is $i$ .

If the above happens, then we can see $i$ as a strong witness to the fact that the consistency of $T$ implies the consistency of $S$ .

Two theories are mutually interpretable iff each one interprets the other. By the above, this is a strong version of the statement that they are equiconsistent.

Two theories are bi-interpretable iff they are mutually interpretable, and in fact, the interpretations $i$ from $T$ is $S$ and $j$ from $S$ in $T$ can be taken to be “inverses” of each other, in the sense that $T$ proves that $\phi$ and $j(i(\phi))$ are equivalent for each $\phi$ in the language of $T$ , and similarly for $S$ , $\psi$ and $i(j(\psi))$ . In a sense, two theories that are bi-interpretable are very much “the same”, only differing in their presentation.

A good example illustrating this notion occurs when formalizing the idea of finitary mathematics. We can show that the two standard formalizations, $\mathsf{PA}$ and $\mathsf{ZFfin}$ , are bi-interpretable, where $\mathsf{ZFfin}$ is the variant of $\mathsf{ZF}$ resulting from replacing the axiom of infinity with its negation, and where foundation is stated as the axiom scheme of $\epsilon$ -induction.

If we do not take the precaution of stating foundation this way, then the resulting theory $\mathsf{ZFfin}'$ is mutually interpretable with $\mathsf{PA}$ , but it is not immediately clear whether they are bi-interpretable, see section 3 for this. (Similar issues, curiously, occur with NFU and appropriate fragments of set theory.) The problem is related to the existence of transitive closures, see section 4 for more details.

The standard interpretation of $\mathsf{ZFfin}$ inside $\mathsf{PA}$ goes by defining $n\mathrel E m$ iff, writing $m$ in base $2$ , the $n$ th number from the right is $1$ . That is, $m=(2k+1)2^n+s$ for some $k$ and some $s<2^n$ . From Gödel’s work on the incompleteness theorems, we know that this is definable inside $\mathsf{PA}$ , see here for some details and references. This interpretation goes back to Ackermann:

Wilhelm Ackermann. Die Widerspruchsfreiheit der allgemeinen Mengenlehre, Math. Ann. 114 (1937), 305–315.

In the other direction, the interpretation goes by realizing that in $\mathsf{ZFfin}$ we can still define $\omega$ and ordinal arithmetic, and the result is a model of $\mathsf{PA}$ . But this is not the inverse. To obtain the inverse, we work in $\mathsf{ZFfin}$ , and compose this with a definable bijection $p:V\to\mathsf{ORD}$ , namely

$p(x)=\sum \{2^{p(y)}\mid y\in x\}.$

(Of course, $V$ stands here for “ $V_\omega$ ”, the universe, and $\mathsf{ORD}$ stands for “ $\omega$ ”.) The paper Kaye-Wong explains all this and provides additional references. This inverse interpretation is due to Mycielski, who published it in Russian:

Jan Mycielski. The definition of arithmetic operations in the Ackermann model. Algebra i Logika Sem. 3 (5-6), (1964), 64–65. MR0177876 (31 #2134).

Mycielski’s result remained “hidden” until attention was drawn to it in the survey

Richard Kaye and Tin Lok Wong. On interpretations of arithmetic and set theory. Notre Dame Journal of Formal Logic 48 (4), (2007), 497–510. MR2357524 (2008i:03075).

(The pdf linked to above has some additional information than the version published at the Journal.)

For a different example, see this question on MathOverflow. In particular, Ali Enayat’s answer links to an excellent survey by Harvey Friedman on Interpretations, according to Tarski.

On the difference between mutual interpretability and bi-interpretability, see this nice post by Ali Enayat to the FOM list. Ali shows there that $\mathsf{ZF}$ and $\mathsf{ZFC}$ , which are obviously mutually interpretable, are not bi-interpretable. The proof goes by noticing that if $T$ and $S$ are bi-interpretable, then the class of groups arising as $\mathrm{Aut}(\mathcal M)$ for $\mathcal M\models T$ coincides with the class of groups of the form $\mathrm{Aut}(\mathcal N)$ for $\mathcal N\models S$ .

However, $\mathsf{ZF}$ admits a model with an automorphism of order $2$ , and this is not possible for $\mathsf{ZFC}$ . (Additional details are given at the link.)

This naturally leads to the question of whether $\mathsf{ZFfin}'$ and $\mathsf{PA}$ (or, equivalently, $\mathsf{ZFfin}$ ) are bi-interpretable, that is, whether a more clever interpretation than Ackermann’s may get rid of the issues that forced us to adopt $\epsilon$ -induction.

That this is not the case, meaning, the theories are mutually interpretable, but not bi-interpretable, was shown recently in

Ali Enayat, James H. Schmerl, and Albert Visser. $\omega$ -models of finite set theory. In Set theory, arithmetic, and foundations of mathematics: theorems, philosophies, Juliette Kennedy, and Roman Kossak, eds. Lect. Notes Log., vol. 36, Assoc. Symbol. Logic, La Jolla, CA, 2011, pp. 43–65. MR2882651 (2012m:03132).

In fact, in Theorem 5.1, they show that $\mathsf{ZFfin}'$ and $\mathsf{PA}$ are not even sententially equivalent. This is a weaker notion than bi-interpretability:

Recall that if we have an interpretation $i$ from $T$ in $S$ , then to each model $\mathcal M$ of $S$ we associate a model $i(\mathcal M)$ of $T$ . That $T$ and $S$ are bi-interpretable gives us interpretations $i$ from $T$ in $S$ , and $j$ from $S$ in $T$ such that for any model $\mathcal M$ of $S$ , the model $j(i(\mathcal M))$ is isomorphic to $\mathcal M$ , and for any model $\mathcal N$ of $T$ , the model $i(j(\mathcal N))$ is isomorphic to $\mathcal N$ .

We say that $T$ and $S$ are sententially equivalent when the interpretations $i$ and $j$ can be chosen to satisfy the weaker demand than $i(j(\mathcal N))$ and $\mathcal N$ are elementarily equivalent, and similarly for $j(i(\mathcal M))$ and $\mathcal M$ .

Their proof that this property fails for $\mathsf{PA}$ and $\mathsf{ZFfin}'$ ultimately traces back to the fact that no arithmetically definable model of $\mathsf{PA}$ that is non-standard can be elementarily equivalent to the standard model. This is a result of Dana Scott. On the other hand, there are many arithmetically definable $\omega$ -models of $\mathsf{ZFfin}'$ . In section 4 we illustrate a very general method for producing such examples; further details can be seen in the Enayat-Schmerl-Visser paper.

This section was originally an answer on Math.Stackexchange.

Let $\mathsf{ZF}^{\lnot\infty}$ be the theory resulting from replacing in $\mathsf{ZF}$ the axiom of infinity by its negation, but leaving foundation as the axiom stating that any non-empty set $x$ has an element disjoint from $x$ . This theory is not strong enough to prove the existence of transitive closures. This is the reason why $\mathsf{ZFfin}$ is usually formulated with foundation (regularity) replaced by its strengthening of $\epsilon$ -induction, namely the scheme that for every formula $\phi(x,\vec y)$ adds the axiom

$\forall \vec y\,(\forall x\,(\forall z\in x\,\phi(z,\vec y)\to\phi(x,\vec y)\to\forall x\,\phi(x,\vec y)).$

Over the base theory $\mathsf{BT}$ consisting of (the empty set exists), extensionality, pairing, union, comprehension, and replacement, one can prove that for any $x$ , there is a transitive set containing $x$ iff there is a smallest such set, that is, there is a transitive set containing $x$ iff its transitive closure exists.

Over $\mathsf{BT}$ plus foundation, the scheme of $\epsilon$ -induction is equivalent to the statement $\mathsf{TC}$ that every set is contained in a transitive set.

Unfortunately, as I claimed above, $\mathsf{ZF}^{\lnot\infty}$ cannot prove the existence of transitive closures. To see this, start with $(V_\omega,\in)$ , the standard model of $\mathsf{ZF}^{\lnot\infty}$ . Let

$\omega^\star=\{\{n+1\}\in V_\omega\mid n\in\omega\}.$

Define $F:V_\omega\to V_\omega$ by

$F(n)=\{n+1\},F(\{n+1\})=n$

for $n\in\omega$ , and $F(x)=x$ for $x\notin\omega\cup\omega^\star$ . Now define a new “membership” relation by

$x\in_F y\Longleftrightarrow x\in F(y)$

for $x,y\in V_\omega$ . It turns out that

$(V_\omega,\in_F)\models\mathsf{ZF}^{\lnot\infty}+\lnot\mathsf{TC}.$

In fact, $\emptyset$ is not contained in any transitive set in this structure. (Note that $\emptyset$ is not the empty set of this model.)

All this and much more is discussed in Kaye-Wong. The result that $\mathsf{ZF}^{\lnot\infty}$ is consistent with $\lnot\mathsf{TC}$ , and the proof just sketched, are due to Mancini. For additional details, Kaye-Wong refers to

Antonella Mancini and Domenico Zambella. A note on recursive models of set theories, Notre Dame Journal of Formal Logic, 42 (2), (2001), 109-115. MR1993394 (2005g:03061).

In fact, if $F:V_\omega\to V_\omega$ is any bijection, then defining $\in^F$ as above gives a model of $\mathsf{ZF}^{\lnot\infty}$ , except possibly for foundation. Many examples can be produced starting from this idea.

Let me close by mentioning a very recent paper by Ali Enayat,

Ali Enayat. Some interpretability results concerning $\mathsf{ZF}$ . Preprint.

Here, Ali extends the result mentioned above that $\mathsf{ZF}$ and $\mathsf{ZFC}$ are not bi-interpretable. In fact, he shows that no two distinct extensions of $\mathsf{ZF}$ are bi-interpretable. (And some more.)

This should be contrasted with the situation for mutually interpretability. The development of forcing and inner model theory in fact has provided us with a plethora of examples of mutually interpretable such extensions. (I would probably expand this short section into a post of its own, once I find appropriate time.)

This entry was posted on Sunday, August 18th, 2013 at 2:14 pm and is filed under 580: Topics in set theory, Interpretations, Peano Arithmetic. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.

2 Responses to Interpretations

andrescaicedo says:

August 18, 2013 at 2:40 pm

fff, http://ffbandf.wordpress.com/, is Forking, Forcing and back&Forthing, a “(collective) blog on all things considered regarding forking, forcing and the back and forth between Model Theory and Set Theory, and even the rest of math.” This is my first post there.

Reply
On anti-foundation and coding the hereditarily finite sets | A kind of library says:

August 27, 2016 at 9:29 am

[…] have written about this before. Briefly, one exhibits (definable) translations between the collection of hereditarily finite […]

Reply

	ปั่นสล็อต on 414/514 The theorems of Rieman…
	Richard Kimberly Hec… on Woodin’s proof of the se…
	Is there a Borel-mea… on 414/514 Examples of Baire clas…
	Simple bijectiveness… on 580 -Some choiceless results…
	Schur’s theore… on 580 -III. Partition calcu…
	Uncountable linearly… on 403/503 – Homework …
	What is a non-constr… on On strong measure zero se…
	function from Nmathb… on Hindsight
	Cauchy Schwarz Inequ… on 275 -Positive polynomials
	What is a Cantor-sty… on 580 -Some choiceless results…
	Question about Gener… on 580 -Some choiceless results…
	Set has Measure Zero… on On strong measure zero se…
	Non-measurable subse… on 580 -Cardinal arithmetic …
	hmeng1 on 414/514 The theorems of Rieman…
	580 -Cardinal arithm… on 580 -Cardinal arithmetic …

A kind of library