Is Robinson Arithmetic biinterpretable with some theory in LST?

This is a refinement of the answer provided by Andres Caicedo.

For weak arithmetics, such as Robinson's $Q$, it is not bi-interpretability, but rather the weaker notion of mutual interpretability that turns out to be the "right" notion to study [See here for a thorough exposition by Harvey Friedman of various notions of interpretability].

It is known that $Q$ is mutually interpretable with a surprisingly weak set theory known as Adjunctive Set Theory, denoted $AS$, whose only axioms are the following two:

1. Empty Set: $\exists x\forall y\lnot (y\in x)$ 2. Adjunction: $\forall x\forall y\exists z\forall t(t\in z\leftrightarrow (t\in x\vee t=y)) $

The mutual interpretability of $Q$ and $AS$ is a refinement of a joint result of Szmielew and Tarski, who proved that $Q$ is interpretable in $AS$ plus Extensionality. This result was reproted without proof in the classic 1953 monograph Undecidable Theories of Tarski, Mostowski, and Robinson. A proof was published by Collins and Halpern in 1970. Later work in this area was made by Montagna and Mancini in 1994, and most recently by Albert Visser in 2009, whose paper below I recommend for references and a short history:.

A. Visser, Cardinal arithmetic in the style of Baron von Münchhausen, Rev. Symb. Log. 2 (2009), no. 3, 570–589

You can find a preprint of the paper here.

Note that since $Q$ is known to be essentially undecidable [i.e., every consistent extension of $Q$ is undecidable], the interpretability of $Q$ in $AS$ implies that AS is essentially undecidable.

I do not know about biinterpretability, but this is too long for a comment, and may be useful towards an answer:

I believe an appropriate set-theoretic version of $Q$ is the theory $Q^+$. First, let $Q^*$ be the theory whose axioms are:

1. Extensionality.
2. There is an empty set.
3. Pairing.
4. Union: $\forall x,y\exists z\forall w(w\in z\leftrightarrow w\in x\lor w\in y)$.

This is a true fragment of the theory of $V_\omega$, and proves all true-in-$V_\omega$ $\Sigma_1$ sentences.

An r.e. set is a $\Sigma_1$ subset of $V_\omega$. If $A$ and its complement (in $V_\omega$) are r.e., $A$ is recursive. There are recursively inseparable r.e. sets, say $A$ and $B$, with $A$ defined by the $\Sigma_1$ formula $\phi$ and $B$ by $\psi$. That they are recursively inseparable means that they are disjoint, but there is no recursive $C$ containing $A$ and disjoint from $B$.

We can define $Q^+$ by adding to $Q^*$ the axiom

5. $\forall x(\lnot\phi(x)\lor\lnot\psi(x))$.

This is a strongly undecidable, essentially undecidable (true) theory.

Any axiomatizable consistent extension $T$ of $Q^*$ is $\Pi_1$-incomplete, i.e., there is a true-in-$V_\omega$ $\Pi_1$ statement that $T$ does not prove. This is the first incompleteness theorem. (Second incompleteness requires a bit more.)

I do not know who these formulations are due to, I learned them from John Steel.

Since the other (excelent) answers didn’t touch the biinterpretability aspect of the question, let me comment on that.

First, a caveat: arbitrary structures (say, in a finite language) can be encoded by directed graphs. Thus, it might very well be the case that $Q$ is biinterpretable with a theory in a language with one binary predicate (i.e., in the language of set theory) which looks nothing like a “set theory” at all, and is not included in or consistent with any recognizable theory of sets like ZFC.

So, a more natural question is if $Q$ is biinterpretable with any theory that contains at least a modicum of set theory. While I didn’t exactly specified what this means, I propose that the answer is negative because of the following result of Albert Visser: $Q$ is not biinterpretable with any theory which includes the axiom of pairing $\forall x,y\,\exists z\,\forall t\,(t\in z\leftrightarrow t=x\lor t=y)$. See On $Q$.