×

zbMATH — the first resource for mathematics

\(\Pi^1_1\) relations and paths through \(\mathcal O\). (English) Zbl 1107.03051
First, the authors give a syntactical characterization of intrinsically \(\Pi_1^1\)-relations on structures. Then they study such relations on structures of maximal Scott rank. For the most natural examples like superatomic parts of Boolean algebras, elements of \(p\)-groups possessing height, and well-ordered segments of Harrison orderings, they find out that the set of possible Turing degrees of such subsets is the same as the set \(\mathcal P\) of Turing degrees of full paths through Kleene’s system \(\mathcal O\). By this, the structure of \(\mathcal P\) is especially interesting to study. In particular, it is shown that there is a path in \(\mathcal O\) in which no noncomputable hyperarithmetical part is computable, that \(\mathcal P\) contains a minimal pair, and that every countable distributive lattice could be embedded in \(\mathcal P\) and \(\mathcal P(\leq {\mathbf c})\), for each \({\mathbf 0}'\leq {\mathbf c}\in{\mathcal P}\).

MSC:
03D45 Theory of numerations, effectively presented structures
03D28 Other Turing degree structures
03F15 Recursive ordinals and ordinal notations
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] DOI: 10.1016/S0168-0072(97)00059-6 · Zbl 0927.03072
[2] Infinitistic methods pp 103– (1959)
[3] DOI: 10.2140/pjm.1969.30.67 · Zbl 0181.30602
[4] Computability, enumerability, unsolvability 224 pp 93– (1996)
[5] Effective model theory vs. recursive model theory 55 pp 1168– (1990)
[6] Infinitary logic and admissible sets 34 pp 226– (1969)
[7] DOI: 10.1016/0168-0072(88)90014-0 · Zbl 0651.03034
[8] DOI: 10.1016/0003-4843(78)90026-8 · Zbl 0404.03020
[9] Aspects of effective algebra pp 26– (1981)
[10] Recursive well-orderings 20 pp 151– (1955)
[11] DOI: 10.1016/0168-0072(89)90015-8 · Zbl 0678.03012
[12] DOI: 10.1002/malq.19960420110 · Zbl 0845.03021
[13] Computable structures and the hyperarithmetical hierarchy (2000) · Zbl 0960.03001
[14] DOI: 10.1002/malq.19960420139 · Zbl 0859.03016
[15] DOI: 10.1016/S0168-0072(96)00026-7 · Zbl 0877.03022
[16] The theory of models pp 329– (1965)
[17] DOI: 10.1016/0168-0072(94)00043-3 · Zbl 0837.03036
[18] Higher recursion theory (1990) · Zbl 0716.03043
[19] Southeast Asian Conference on Logic (Singapore, 1981) pp 185– (1983)
[20] Fundamenta Mathematical 87 pp 161– (1975)
[21] DOI: 10.1016/S0168-0072(01)00087-2 · Zbl 1016.03034
[22] DOI: 10.1090/S0002-9947-1968-0244049-7
[23] DOI: 10.1016/0168-0072(91)90097-6 · Zbl 0756.03022
[24] DOI: 10.1023/A:1021758312697
[25] DOI: 10.1007/BF01669456 · Zbl 0407.03040
[26] Proceedings of the American Mathematical Society 54 pp 311– (1976)
[27] One hundred and two problems in mathematical logic 40 pp 113– (1975)
[28] Theory of recursive functions and effective computability (1967) · Zbl 0183.01401
[29] DOI: 10.1016/0003-4843(77)90009-2 · Zbl 0376.02032
[30] Proceedings of the American Mathematical Society 39 pp 178– (1973)
[31] Degrees of unsolvability (1983) · Zbl 0542.03023
[32] DOI: 10.4153/CJM-1971-024-7 · Zbl 0272.02064
[33] Infinite abelian groups (1954)
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.