Notes on Interpretability between Weak First-order Theories: Theories of Sequences

We introduce a first-order theory $\mathsf{S}\mathsf{e}\mathsf{q}$ which is mutually interpretable with Robinson’s $\mathsf{Q}$. The universe of a standard model for $\mathsf{S}\mathsf{e}\mathsf{q}$ consists of sequences. We prove that $\mathsf{S}\mathsf{e}\mathsf{q}$ directly interprets the adjuctive set theory $\mathsf{A}\mathsf{S}\mathsf{T}$, and we prove that $\mathsf{S}\mathsf{e}\mathsf{q}$ interprets the tree theory $\mathsf{T}$ and the set theory $\mathsf{A}\mathsf{S}\mathsf{T}+\mathsf{E}\mathsf{X}\mathsf{T}$.