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 essential undecidability essentially undecidable [i.e., every consistent extension of $Q$ is undecidable], the interpretability of $Q$ in $AS$ implies that AS is essentially undecidable.
