Advertisement
Published in:
2014 | OriginalPaper | Chapter
Computability and Categoricity of Ultrahomogeneous Structures
Authors : Francis Adams, Douglas Cenzer
Published in: Language, Life, Limits
Publisher: Springer International Publishing
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
This paper investigates the effective categoricity of ultrahomogeneous structures. It is shown that any computable ultrahomogeneous structure is
$\varDelta^0_2$
categorical. A structure
${\mathcal A}$
is said to be
weakly ultrahomogeneous
if there is a finite (
exceptional
) set of elements
a
1
,…,
a
n
such that
${\mathcal A}$
becomes ultrahomogeneous when constants representing these elements are added to the language. Characterizations are obtained for the weakly ultrahomogeneous linear orderings, equivalence structures, and injection structures, and compared with characterizations of the computably categorical and
$\varDelta^0_2$
categorical structures.