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:
-
Robinson Arithmetic is essentially undecidable (as PA and all stronger theories are)
-
PA proves the consistency of Robinson Arithmetic
-
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?
Best Answer
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.