A Weak First-Order Theory of Sequences

We introduce a first-order theory \(\textsf{Seq}\) which is mutually interpretable with Robinson’s \(\textsf{Q}\) . The universe of a standard model for \(\textsf{Seq}\) consists of sequences. We prove that \(\textsf{Seq}\) directly interprets the adjunctive set theory \(\textsf{AST}\) , and we prove that \(\textsf{Seq}\) interprets the tree theory \(\textsf{T}\) and the set theory \(\mathsf {AST + EXT}\) .