6
$\begingroup$

Given a regular logic $\mathcal{L}$ and a structure $\mathfrak{A}$ (in a finite relational language $\Sigma$ for simplicity), let $\overline{Th_\mathcal{L}(\mathfrak{A})}$ be the structure defined as follows:

  • The underlying set of $\overline{Th_\mathcal{L}(\mathfrak{A})}$ is the disjoint union of the underlying set $A$ of $\mathfrak{A}$ and the set of all $\mathcal{L}[\Sigma]$-formulas with parameters from $\mathfrak{A}$ and at most the variable $x$ free.

  • These two "pieces" are named by unary relation symbols $X,F$ respectively.

  • On the "$X$-piece" we have the structure of $\mathfrak{A}$.

  • Connecting the "$X$-piece" and "$F$-piece" we have the substitution relation $$\mathsf{subs}=\{(\varphi,a,\psi): \psi=\varphi[a/x]\}.$$

  • On the "$F$-piece" alone we have a unary relation symbol $T$ naming the true-in-$\mathfrak{A}$ $\mathcal{L}$-sentences.

The usual argument of Tarski's undefinability theorem shows in fact that $\overline{Th_\mathcal{L}(\mathfrak{A})}$ is not $\mathcal{L}$-bi-interpretable with $\mathfrak{A}$, for any choice of $\mathfrak{A}$ and $\mathcal{L}$. However, this falls short of showing that $\overline{Th_\mathcal{L}(\mathfrak{A})}$ is not $\mathcal{L}$-interpretable in $\mathfrak{A}$ (recall that $\mathcal{L}$-bi-interpretability is stronger than mere $\mathcal{L}$-interpretability in both directions). I think I have an example of a structure $\mathfrak{S}$ such that $\overline{Th_{\mathsf{FOL}}(\mathfrak{S})}$ is interpretable in $\mathfrak{S}$, but it's very messy - so even if it's correct, it's not very good.

Question: is there a "reasonably simple" example of a structure $\mathfrak{A}$ and a logic $\mathcal{L}$ such that $\overline{Th_\mathcal{L}(\mathfrak{A})}$ is $\mathcal{L}$-interpretable in $\mathfrak{A}$?

One obvious requirement is that $\mathfrak{A}$ be very bad at defining isomorphisms between interpreted copies of itself.

$\endgroup$
1
  • $\begingroup$ Does Tarski's argument establish that $\mathfrak{A}$ and $\overline{Th_\mathcal{L}(\mathfrak{A})}$ are not bi-interpretable or does it establish that they're not bi-interpretable in a way that fixes $\mathfrak{A}$ (as in, using the obvious interpretation of $\mathfrak{A}$ in $\overline{Th_\mathcal{L}(\mathfrak{A})}$)? $\endgroup$ Commented Mar 21, 2022 at 23:35

0

You must log in to answer this question.

Browse other questions tagged .