The theory of hereditarily bounded sets

DOI10.1002/MALQ.202100020zbMATH Open1521.03077arXiv2104.06932OpenAlexW4225979384MaRDI QIDQ6094150FDOQ6094150

Authors: Emil Jeřábek 

Publication date: 12 September 2023

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

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)$.

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

Recommendations

• Decidability of \(\exists^*\forall\forall\)-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

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)

Cites Work

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

Cited In (7)

• Title not available (Why is that?)
• 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 \(\exists^*\forall\forall\)-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)