The theory of hereditarily bounded sets

0556685 - MÚ 2023 RIV DE eng J - Článek v odborném periodiku
Jeřábek, Emil
The theory of hereditarily bounded sets.
Mathematical Logic Quarterly. Roč. 68, č. 2 (2022), s. 243-256. ISSN 0942-5616. E-ISSN 1521-3870
Grant CEP: GA ČR(CZ) GA19-05497S
Institucionální podpora: RVO:67985840
Klíčová slova: hereditarily finite sets * pairing function * decidability
Obor OECD: Pure mathematics
Impakt faktor: 0.3, rok: 2022
Způsob publikování: Omezený přístup
https://doi.org/10.1002/malq.202100020

We show that for any finite k, 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.
Trvalý link: http://hdl.handle.net/11104/0330805