zbMATH — the first resource for mathematics

Classifying model-theoretic properties. (English) Zbl 1160.03012
Summary: In [J. Symb. Log. 69, No. 4, 1117–1142 (2004; Zbl 1071.03021)], B. F. Csima, D. R. Hirschfeldt, J. F. Knight, and R. I. Soare showed that a set \(A\leq _{\text T} 0'\) is nonlow\(_{2}\) if and only if \(A\) is prime bounding, i.e., for every complete atomic decidable theory \(T\), there is a prime model \(\mathcal M\) computable in \(A\). The authors presented nine seemingly unrelated predicates of a set \(A\), and showed that they are equivalent for \(\Delta ^{0}_{2}\) sets. Some of these predicates, such as prime bounding, and others involving equivalence structures and abelian \(p\)-groups come from model theory, while others involving meeting dense sets in trees and escaping a given function come from pure computability theory.
As predicates of \(A\), the original nine properties are equivalent for \(\Delta ^{0}_{2}\) sets; however, they are not equivalent in general. This article examines the (degree-theoretic) relationship between the nine properties. We show that the nine properties fall into three classes, each of which consists of several equivalent properties. We also investigate the relationship between the three classes, by determining whether or not any of the predicates in one class implies a predicate in another class.

03C57 Computable structure theory, computable model theory
Zbl 1071.03021
Full Text: DOI
[1] Siberian Mathematical Journal 27 pp 572– (1986)
[2] Izvestiya Akademii Nauk Kazakhskoǐ SSR. Seriya Fiziko-Matematicheskaya pp 51– (1981)
[3] Bounding prime models 69 pp 1117– (2004)
[4] Recursive in a generic real 65 pp 164– (2000)
[5] Handbook of recursive mathematics 138 pp 1177– (1998)
[6] DOI: 10.1305/ndjfl/1022615611 · Zbl 1007.03036
[7] Degrees of unsolvability (1983) · Zbl 0542.03023
[8] DOI: 10.1305/ndjfl/1039724885 · Zbl 0891.03013
[9] Recursively enumerable sets and degrees: A study of computable functions and computably generated sets (1987) · Zbl 0667.03030
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.