Computability and categoricity of weakly ultrahomogeneous structures

DOI10.3233/COM-170070zbMATH Open1420.03069arXiv1608.01254MaRDI QIDQ4601031FDOQ4601031

Authors: Francis Adams, Douglas Cenzer 

Publication date: 18 January 2018

Published in: Computability (Search for Journal in Brave)

Abstract: This paper investigates the effective categoricity of ultrahomogeneous structures. It is shown that any computable ultrahomogeneous structure is $Delt{a}_2^0$ categorical. A structure A is said to be weakly ultrahomogeneous if there is a finite (exceptional) set of elements $a_1,dots,a_n$ such that A becomes ultrahomogeneous when constants representing these elements are added to the language. Characterizations are obtained for weakly ultrahomogeneous linear orderings, equivalence structures, injection structures and trees, and these are compared with characterizations of the computably categorical and $Delt{a}_2^0$ categorical structures. Index sets are used to determine the complexity of the notions of ultrahomegenous and weakly ultrahomogeneous for various families of structures.

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

Recommendations

• Computability and categoricity of ultrahomogeneous structures
• Computability-theoretic categoricity and Scott families
• Categoricity spectra of computable structures
• The complexity of computable categoricity
• Effective categoricity of equivalence structures

zbMATH Keywords

computabilitycomputable model theoryinjectionsultrahomogeneous structureseffective categoricity

Mathematics Subject Classification ID

Models with special properties (saturated, rigid, etc.) (03C50) Categoricity and completeness of theories (03C35) Computable structure theory, computable model theory (03C57) Theory of numerations, effectively presented structures (03D45)

Cited In (6)

• A Note on the Computable Categoricity of $$\ell ^p$$ ℓ p Spaces
• Computability and categoricity of ultrahomogeneous structures
• Effective algebraicity
• Categoricity spectra of computable structures
• Omega-categorical structures and their algebraic invariants
• Computability-theoretic properties of injection structures

This page was built for publication: Computability and categoricity of weakly ultrahomogeneous structures

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