# Is Robinson Arithmetic biinterpretable with some theory in LST?

Let ZFC$^{\text{fin}}$ be ZFC minus the axiom of infinity plus the negation of the axiom of infinity. It is well-known that ZFC$^{\text{fin}}$ is biinterpretable with Peano Arithmetic. In this sense one could argue that ZFC$^{\text{fin}}$ is PA couched in the language of set theory (ie one nonlogical binary relation, $\in$) rather than the language of arithmetic ($+$, $\cdot$, $0$, $S$). This gives us some confidence that "there exists an infinite set" -- and the hierarchy of large cardinal axioms beyond -- is an at least somewhat-natural extension of arithmetic.

In precise terms, every theory in this hierarchy proves the consistency of all those before it. In vague terms, each theory in this hierarchy adds "more infiniteness" than those before it.

Does the hierarchy start at PA, or is there a step below it? Robinson Arithmetic is a theory in the language of arithmetic; among its properties are:

1. Robinson Arithmetic is essentially undecidable (as PA and all stronger theories are)

2. PA proves the consistency of Robinson Arithmetic

3. Robinson Arithmetic is finitely axiomatizable

The first point might be considered an argument for why Robinson Arithmetic is part of the same hierarchy as PA/ZFC$^{\text{fin}}$ -- it has enough coding power to express primitive recursion. The second point shows why Robinson Arithmetic is strictly below PA/ZFC$^{\text{fin}}$ on this hierarchy. The third point explains -- in vague terms -- what sort of "infiniteness" PA/ZFC$^{\text{fin}}$ add to Robinson Arithmetic: it adds infinite collections of axioms.

From PA on up, all theories on the hierarchy are biinterpretable with some theory in the language of set theory.

Question: is Robinson Arithmetic biinterpretable with some theory in the language of set theory?

-
Don't know about Q, but Elementary Arithmetic is also finitely axiomatisable, essentially undecidable, and has a finitary consistency proof. Avigad's Number theory and elementary arithmetic (citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.105.6509) discusses EA and the set theory of Extensionality, Delta-0 Induction, Pair, Union, Power, and Delta-0 Separation. –  Daniel Mehkeri Jan 11 '11 at 5:03

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.

-
Hi Ali, many thanks for the references! –  Andres Caicedo May 28 '11 at 19:28
@Ali, thank you! If I could accept both @Andres' answer and yours I would accept both (since, as you mention, your answer builds on his). For the sake of posterity I'll put the green checkmark on this answer so people who come across this page know that they need to read both answers to get the whole story. Thank you! –  Adam Jun 15 '11 at 21:32
I take it that Adjunction essentially means that the union of any set with a singleton set exists (and singleton sets exist by the empty set axiom). You're right, that is surprisingly weak... Especially since it does not include extensionality! –  Adam Jun 15 '11 at 21:35
@Adam: I am glad to hear that you found the answer useful; your paraphrase of Adjunction is on "on the dot", by the way. –  Ali Enayat Jun 15 '11 at 21:59

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.

-
How embarrassing. Yes, $Q^\star$ is in my 225b notes exactly as you describe it. However I've got something completely different for $Q^+$ (all of the $T^+$ theories were in LST plus countably many constants, one for each set of HF, and countably many axioms basically amounting to extensionality for those constants). I really like how he teaches recursion theory using HF instead of $\mathbb N$, although the downside is that there's no textbook to go with it. –  Adam Jan 11 '11 at 3:53
Oh, sure. What I am calling $Q^+$ here is what Steel called $Q$ with a super-index $**$. But the LaTeX wasn't compiling for that, so I changed its name. –  Andres Caicedo Jan 11 '11 at 4:01
Okay, I see how adding (5) makes $Q^\star$ essentially undecidable, and that certainly will have to happen in order for the theory to interpret Robinson Arithmetic. But I'm still a bit uncertain about how you'd take advantage of that when defining an interpretation. Also, do you get the same theory for any pair of r.e. recursively inseparable sets $A$ and $B$, or might different r.e. sets give you different theories? –  Adam Jan 11 '11 at 4:14
Why is $Q^+$ strongly undecidable? –  Amit Kumar Gupta Jan 12 '11 at 2:08
Hi Adam. Theories with different pairs $A,B$ are bi-interpretable, but I am not convinced they are actually equal. I am not sure whether $Q^+$ solves your problem. In a sense, the issue is that we have very limited resources to work with, it is an interesting question. –  Andres Caicedo Jan 12 '11 at 2:35