The theory of hereditarily bounded sets

04/14/2021

∙

by   Emil Jeřábek, et al.

∙

0

∙

share

We show that for any k∈ω, the structure (H_k,∈) 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_ω=⋃_k H_k of hereditarily finite sets, which is well known to be bi-interpretable with the standard model of arithmetic (ℕ,+,·).