×

zbMATH — the first resource for mathematics

Infima in the recursively enumerable weak truth table degrees. (English) Zbl 0909.03038
The following interesting results are given:
1. For any nonrecursive, \(W\)-incomplete r.e. \(W\)-degree \({\mathbf c}\), there is an r.e. \(W\)-degree \({\mathbf a} |_W {\mathbf c}\) such that the infimum \({\mathbf a} \cap {\mathbf c}\) exists. This shows that there are no strongly noncappable r.e. \(W\)-degrees, in contrast to the situation in the r.e. \(T\)-degrees.
2. For any nonrecursive, \(W\)-incomplete r.e. \(W\)-degree \({\mathbf c}\), there is an r.e. \(W\)-degree \({\mathbf a}\) such that the infimum \({\mathbf a} \cap {\mathbf c}\) fails to exist.
MSC:
03D25 Recursively (computably) enumerable sets and degrees
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Ambos-Spies, K., “Contiguous r.e. degrees,” pp. 1–37 in Computation and Proof Theory, Lecture Notes in Mathematics , 1104, edited by M. M. Richter et al., Springer-Verlag, New York, 1984. · Zbl 0562.03022
[2] Ambos-Spies, K., “On pairs of recursively enumerable degrees,” Transactions of the American Mathematical Society , vol. 283 (1984), pp. 507–31. · Zbl 0541.03023
[3] Ambos-Spies, K., “Cupping and noncapping in the r.e. weak truth table and Turing degrees,” Archiv für mathematische Logik und Grundlagenforschung , vol. 25 (1985), pp. 109–26. · Zbl 0619.03032
[4] Blaylock, R., Some Results on e-Genericity and Recursively Enumerable Weak Truth Table Degrees , Ph.D. Dissertation, University of Illinois at Urbana-Champaign, 1991.
[5] Cohen, P. F., Weak Truth-Table Reducibility and the Pointwise Ordering of 1-1 Recursive Functions , Ph.D. Dissertation, University of Illinois at Urbana-Champaign, 1975.
[6] Downey, R. G., “\(\Delta_2^0\) degrees and transfer theorems,” Illinois Journal of Mathematics, vol. 31 (1987), pp. 419–27. · Zbl 0629.03017
[7] Fischer, P., “Pairs without infimum in the recursively enumerable weak truth table degrees,” The Journal of Symbolic Logic , vol. 51 (1986), pp. 117–29. JSTOR: · Zbl 0587.03030
[8] Friedberg, R. M., and H. Rogers, Jr. “Reducibility and completeness for sets of integers,” Zeitschrift für mathematische Logik und Grundlagen der Mathematik , vol. 5 (1959), pp. 117–25. · Zbl 0108.00602
[9] Jockusch, Jr., C. G., “Three easy constructions of recursively enumerable sets,” pp. 83–91 in Logic Year 1979–80, Lecture Notes in Mathematics , 859, edited by M. Lerman, J. Schmerl, and R. Soare, Springer-Verlag, New York, 1981. · Zbl 0472.03031
[10] Lachlan, A. H., “Lower bounds for pairs of recursively enumerable degrees,” Proceedings of the London Mathematical Society , vol. 16 (1966), pp. 537–69. · Zbl 0156.00907
[11] Ladner, R. E., and L. P. Sasso, “The weak truth table degrees of recursively enumerable sets,” Annals of Mathematical Logic , vol. 8 (1975), pp. 429–48. · Zbl 0324.02028
[12] Soare, R. I., Recursively Enumerable Sets and Degrees , Springer-Verlag, New York, 1987. · Zbl 0623.03042
[13] Stob, M., “wtt-degrees and T-degrees of recursively enumerable sets,” The Journal of Symbolic Logic, vol. 48 (1983), pp. 921–30. JSTOR: · Zbl 0563.03028
[14] Yates, C. E. M., “A minimal pair of recursively enumerable degrees,” The Journal of Symbolic Logic, vol. 32 (1965), pp. 159–68. JSTOR: · Zbl 0143.25402
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.