×

Computability of Fraïssé limits. (English) Zbl 1215.03053

The authors contribute to general computable model theory by giving an effective analysis of computable structures via their “age”, being the collection of finitely generated substructures. Some basic theory is given and some general results proven for various kinds of things like amalgamation properties. For example, for structures (of a certain kind) a general syntactic condition is given for degree spectra to be upward closed. The usual suspects, Boolean algebras, linear orderings, various kinds of \({\mathbb Z}\)-modules and \(p\)-groups, together with graphs of various kinds are given as applications. This seems to be a nice unifying paper.

MSC:

03C57 Computable structure theory, computable model theory
03D45 Theory of numerations, effectively presented structures
PDF BibTeX XML Cite
Full Text: DOI

References:

[1] DOI: 10.1090/S0002-9939-98-04307-X · Zbl 0894.03017
[2] Aspects of effective algebra pp 26– (1981)
[3] DOI: 10.1002/malq.19860322514 · Zbl 0586.03030
[4] DOI: 10.1016/0168-0072(91)90049-R · Zbl 0744.03035
[5] DOI: 10.1016/j.apal.2005.02.001 · Zbl 1081.03033
[6] Theory of relations (1986)
[7] Proceedings of the American Mathematical Society 114 pp 545– (1992)
[8] DOI: 10.1090/S0002-9939-1994-1203984-4
[9] DOI: 10.1023/A:1023350306979
[10] The complexity of intrinsically r.e. subsets of existentially decidable models 55 pp 1213– (1990) · Zbl 0722.03031
[11] DOI: 10.1090/S0002-9939-98-04314-7 · Zbl 0906.03044
[12] Moderne Algebra (1930)
[13] Recursively enumerable sets and degrees (1987)
[14] Computable structures and the hyperarithmetical hierarchy (2000) · Zbl 0960.03001
[15] The {\(\Delta\)}2 0-spectrum of a linear order 66 pp 470– (2001)
[16] Degrees coded in jumps of orderings 51 pp 1034– (1986) · Zbl 0633.03038
[17] Models and computability: Invited papers from Logic Colloquium ’97 259 pp 193– (1999)
[18] DOI: 10.1016/S0168-0072(97)00059-6 · Zbl 0927.03072
[19] DOI: 10.1016/0168-0072(91)90038-N · Zbl 0734.03026
[20] A shorter model theory (1997) · Zbl 0873.03036
[21] DOI: 10.1016/S0168-0072(01)00087-2 · Zbl 1016.03034
[22] Spectra of structures and relations 72 pp 324– (2007)
[23] Contemporary mathematics pp 65– (2000)
[24] Handbook of recursive mathematics 1 pp 3– (1998)
[25] Degrees of structures 46 pp 723– (1981)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.