We show that for any, the structure 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 of hereditarily finite sets, which is well known to be bi‐interpretable with the standard model of arithmetic.

A structure M is pregeometric if the algebraic closure is a pregeometry in all structures elementarily equivalent to M. We define a generalisation: structures with an existential matroid. The main examples are superstable groups of Lascar U-rank a power of ω and d-minimal expansion of fields. Ultraproducts of pregeometric structures expanding an integral domain, while not pregeometric in general, do have a unique existential matroid. Generalising previous results by van den Dries, we define dense elementary pairs of structures expanding an (...) integral domain and with an existential matroid, and we show that the corresponding theories have natural completions, whose models also have a unique existential matroid. We also extend the above result to dense tuples of structures. (shrink)