Sage Journals: Discover world-class research

Abstract

This paper investigates the effective categoricity of ultrahomogeneous structures. It is shown that any computable ultrahomogeneous structure is $Δ_{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 $Δ_{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.

Keywords

Computability ultrahomogeneous injections effective categoricity computable model theory

Get full access to this article

View all access options for this article.

References

Adams and

Cenzer, Computability and categoricity of ultrahomogeneous structures, in: Language, Life, Limits: Proc. CiE 2014 (Computability in Europe),

Beckmann,

Csuhaj-Varju and

Meer, eds, Springer Lecture Notes in Computer Science, Vol. 8493, 2014, pp. 1–10.

Calvert,

Cenzer,

Harizanov and

Morozov, Effective categoricity of equivalence structures, Annals of Pure and Applied Logic 14(1) (2006), 61–78. doi:10.1016/j.apal.2005.10.002.

Calvert,

J.F.

Knight and

Millar, Computable trees of Scott rank

ω_{1}^{CK}

and computable approximation, J. Symbolic Logic 76 (2006), 283–298. doi:10.2178/jsl/1140641175.

Cenzer,

Harizanov and

J.B.

Remmel, Computability theoretic properties of injection structures, Algebra and Logic 53 (2014), 39–69. doi:10.1007/s10469-014-9270-0.

Csima,

Harizanov,

Miller and

Montalban, Computability of Fraisse limits, J. Symbolic Logic 76 (2011), 66–93. doi:10.2178/jsl/1294170990.

Fokina,

J.F.

Knight,

Melnikov,

S.M.

Quinn and

Safranski, Classes of Ulm type and coding rank-homogeneous trees in other structures, J. Symbolic Logic 76 (2011), 846–869. doi:10.2178/jsl/1309952523.

Fraisse, Theory of Relations, North-Holland, Amsterdam, 1986.

A.H.

Lachlan, Homogeneous structures, in: Proceedings of the International Congress of Mathematicians, Berkeley, CA, 1986, Vol. 1, Amer. Math. Soc., Providence, RI, 1987, pp. 314–321.

A.H.

Lachlan and

R.E.

Woodrow, Countable ultrahomogeneous undirected graphs, Trans. Amer. Math. Soc. 262 (1980), 51–94. doi:10.1090/S0002-9947-1980-0583847-2.

10.

Lempp,

McCoy,

Miller and

Solomon, Computable categoricity of trees of finite heights, J. Symbolic Logic 70 (2005), 151–215. doi:10.2178/jsl/1107298515.

11.

Marker, Model Theory: An Introduction, Springer, New York, 2002.

12.

Marshall, Computability-Theoretic Properties of Partial Injections, Trees, and Nested Equivalences, Ph.D. dissertation, George Washington University, 2015.

13.

Miller, The computable dimensions of trees of infinite height, J. Symbolic Logic 70 (2005), 111–141. doi:10.2178/jsl/1107298513.

14.

J.B.

Remmel, Recursively categorical linear orders, Proceedings of the AMS 83 (1981), 387–391. doi:10.1090/S0002-9939-1981-0624937-1.

15.

Soare, Recursive Enumerable Sets and Degrees, Springer-Verlag, 1987.

Computability and categoricity of weakly ultrahomogeneous structures

Abstract

Keywords

Get full access to this article

References