The theory of hereditarily bounded sets

DOI10.1002/MALQ.202100020MaRDI QIDQ6094150zbMATH OpenOpenAlexFDO

Authors Emil Jeřábek

Publication date 12 September 2023

Published in Mathematical Logic Quarterly (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2104.06932

Mathematics Subject Classification ID

Models with special properties (saturated, rigid, etc.) (03C50) Decidability of theories and sets of sentences (03B25) Complexity of computation (including implicit computational complexity) (03D15) Quantifier elimination, model completeness, and related topics (03C10)

Abstract: We show that for any $kinomega$, 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 $$ of hereditarily finite sets, which is well known to be bi-interpretable with the standard model of arithmetic $(mathbbN,+,cdot)$.

Recommendations

• Decidability of ^*-sentences in HF
• Hereditary undecidability of some theories of finite structures
• Undecidable fragments of elementary theories
• Hereditarily-finite sets, data bases and polynomial-time computability
• scientific article; zbMATH DE number 1533641

Cites work

• scientific article; zbMATH DE number 3194530 (Why is no real title available?)
• Axiomatizability by a schema
• Decidability of the theory of the natural integers with the Cantor pairing function and the successor
• Des belles paires aux beaux uples
• LOGICAL THEORIES OF ONE-PLACE FUNCTIONS ON THE SET OF NATURAL NUMBERS
• La théorie élémentaire de la fonction de couplage de Cantor des entiers naturels est décidable
• On arithmetical first-order theories allowing encoding and decoding of lists
• Pairs, sets and sequences in first-order theories
• The computational complexity of logical theories
• Undecidable theories

Cited in

(7)

• scientific article; zbMATH DE number 599450 (Why is no real title available?)
• Hereditarily finite Finsler sets
• On the complexity of decision using destinies in \(H\)-bounded structures
• Hereditarily-finite sets, data bases and polynomial-time computability
• The fair division of hereditary set systems
• Enumeration of the adjunctive hierarchy of hereditarily finite sets
• Decidability of ^*-sentences in HF

This page was built for publication: The theory of hereditarily bounded sets

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6094150)