The theory of hereditarily bounded sets

Abstract

We show that for any $k\in \omega$, the structure $(H_k,\in )$ of sets that are hereditarily of size at most $k$ is decidable. We provide a transparent complete axiomatization of its theory, a quantifier elimination result, and tight bounds on its computational complexity. This stands in stark contrast to the structure $V_{\omega }={\bigcup }_k{H}_k$ of hereditarily finite sets, which is well known to be bi-interpretable with the standard model of arithmetic $(\mathbb{N},+,\cdot )$.

20 pages

Cited by in corpus (1)

• Friedman-reflexivity: interpreters as consistoids