Computability and categoricity of weakly ultrahomogeneous structures

DOI10.3233/COM-170070MaRDI QIDQ4601031zbMATH OpenFDO

Authors Francis Adams, Douglas Cenzer

Publication date 18 January 2018

Published in Computability (Search for Journal in Brave)

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

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)

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.

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

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)