The theory of ceers computes true arithmetic

DOI10.1016/j.apal.2020.102811zbMath1442.03021arXiv1909.09401OpenAlexW3016201751MaRDI QIDQ2187270

Noah Schweber, Uri Andrews, Andrea Sorbi

Publication date: 2 June 2020

Published in: Annals of Pure and Applied Logic (Search for Journal in Brave)

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

zbMATH Keywords

computably enumerable equivalence relationcomputable reducibility on equivalence relations

Mathematics Subject Classification ID

First-order arithmetic and fragments (03F30) Recursively (computably) enumerable sets and degrees (03D25) Other degrees and reducibilities in computability and recursion theory (03D30)

Related Items

Primitive recursive equivalence relations and their primitive recursive complexity ⋮ Index sets for classes of positive preorders ⋮ INITIAL SEGMENTS OF THE DEGREES OF CEERS ⋮ ON THE STRUCTURE OF COMPUTABLE REDUCIBILITY ON EQUIVALENCE RELATIONS OF NATURAL NUMBERS ⋮ Classifying word problems of finitely generated algebras via computable reducibility ⋮ On universal positive graphs ⋮ The structure of computably enumerable preorder relations ⋮ Well-orders realized by C.E. equivalence relations ⋮ Computable embeddability for algebraic structures

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The effective theory of Borel equivalence relations
• Some undecidability results for lattices in recursion theory
• Definability in the Turing degrees
• Relatively precomplete numerations and arithmetic
• First-order theory of the degrees of recursive unsolvability
• Definability in the enumeration degrees
• Positive equivalences
• Jumps of computably enumerable equivalence relations
• The last question on recursively enumerable \(m\)-degrees
• Graphs realised by r.e. equivalence relations
• UNIVERSAL COMPUTABLY ENUMERABLE EQUIVALENCE RELATIONS
• LINEAR ORDERS REALIZED BY C.E. EQUIVALENCE RELATIONS
• Classifying positive equivalence relations
• Interpretability and Definability in the Recursively Enumerable Degrees
• The Theory of the Degrees below 0 ′
• Theorie der Numerierungen I
• Recursively Enumerable Equivalence Relations Modulo Finite Differences
• On Group-Theoretic Decision Problems and Their Classification. (AM-68)
• Interpreting true arithmetic in the local structure of the enumeration degrees
• ON ISOMORPHISM CLASSES OF COMPUTABLY ENUMERABLE EQUIVALENCE RELATIONS
• Joins and meets in the structure of ceers
• Definability via Kalimullin pairs in the structure of the enumeration degrees
• Isomorphism relations on computable structures
• Defining totality in the enumeration degrees
• Computably enumerable equivalence relations
• A list of arithmetical structures complete with respect to the first-order definability