Generalization of Shapiro's theorem to higher arities and noninjective notations

DOI10.1007/s00153-022-00836-4OpenAlexW4295655564WikidataQ114231461 ScholiaQ114231461MaRDI QIDQ2700823

Michał Wrocławski, Dariusz Kalociński

Publication date: 27 April 2023

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

Full work available at URL: https://doi.org/10.1007/s00153-022-00836-4

zbMATH Keywords

equivalence relationsdefinabilityintrinsic computabilitylearnabilitynotations for natural numbers

Mathematics Subject Classification ID

Computable structure theory, computable model theory (03C57)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Generic copies of countable structures
• Acceptable notation
• Model theory
• Computable structures and the hyperarithmetical hierarchy
• A taxonomy of deviant encodings
• Primitively recursive categoricity for unars and equivalence structures
• Representations of natural numbers and computability of various functions
• A note on decidable categoricity and index sets
• Scott sentences for equivalence structures
• Degrees of bi-embeddable categoricity of equivalence structures
• On \(\Delta_2^0\)-categoricity of equivalence relations
• Effective categoricity of equivalence structures
• On degrees of unsolvability
• Degrees coded in jumps of orderings
• Recantation or Any old ω-sequence would do after all
• A Friedberg enumeration of equivalence structures
• Computable Structure Theory
• Trial and error predicates and the solution to a problem of Mostowski
• Limiting recursion