Hostname: page-component-78c5997874-g7gxr Total loading time: 0 Render date: 2024-11-02T22:32:12.831Z Has data issue: false hasContentIssue false
  • English
  • Français

An application of Σ40 determinacy to the degrees of unsolvability

Published online by Cambridge University Press:  12 March 2014

Carl G. Jockusch Jr.
Carl G. Jockusch Jr.*
Affiliation:
University of Illinois, Urbana, Illinois 61801
Get access Rights & Permissions [Opens in a new window]

Extract

If a and b are degrees of unsolvability, a is called (as in [1]) a minimal cover of b if b < a and no degree c satisfies b < c < a. A degree a is called a minimal cover if it is a minimal cover of some degree b. We show in ZF set theory that there is a degree d such that every degree a ≥ d is a minimal cover. In [1] it was remarked that this result follows via a lemma of D. A. Martin [4] from the determinacy of a certain Σ50 Gale-Stewart game (which in turn follows [5] from the existence of a measurable cardinal). The argument here is parallel to that of [1], but the essential new ingredient is the result of Paris [6] that Σ50 determinacy can be proved in ZF. Also it is necessary to replace the Σ50 game of [1] by a related Σ40 game and to use the method, rather than just the statement, of Martin's lemma.

Theorem. There is a degreedsuch that every degreea ≥ dis a minimal cover.

Proof. In a (Gale–Stewart) game on 2ω, players I and II construct a set of integers A as follows: At the nth stage, player I determines whether n ϵ A if n is even and player II if n is odd. Thus player I controls A0 and player II controls A1 where Ai = {n: 2n + i ϵ A}. Let Aij denote (Ai)j and let M (A, B) mean that the degree of A is a minimal cover of that of B. Consider now the particular game in which player I wins iff M(A, A00) holds.

Type
Research Article
Information
The Journal of Symbolic Logic , Volume 38 , Issue 2 , June 1973 , pp. 293 - 294
Copyright
Copyright © Association for Symbolic Logic 1973

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

BIBLIOGRAPHY

[1]Jockusch, C. G. Jr. and Soare, R. I., Minimal covers and arithmetical sets, Proceedings of the American Mathematical Society, vol. 25 (1970), pp. 856–859.CrossRefGoogle Scholar
[2]Lachlan, A. H., Distributive initial segments of the degrees of unsolvability, Zeitschrift für mathematische Logik und Grundlagen der Mathematik, vol. 14 (1968), pp. 457–472.CrossRefGoogle Scholar
[3]Lerman, M., Initial segments of the degrees of unsolvability, Annals of Mathematics (2), vol. 93 (1971), pp. 365–389.CrossRefGoogle Scholar
[4]Martin, D. A., The axiom of determinateness and reduction principles in the analytical hierarchy, Bulletin of the American Mathematical Society, vol. 74 (1968), pp. 687–689.CrossRefGoogle Scholar
[5]Martin, D. A., Measurable cardinals and analytic games, Fundamenta Mathematicae, vol. 66 (1970), pp. 287–291.Google Scholar
[6]Paris, J. B., ZF ⊦ Σ40determinateness, this Journal (to appear).Google Scholar
[7]Shoenfield, J. R., Mathematical Logic, Addison-Wesley, Reading, Mass., 1967.Google Scholar
[8]Spector, C., On degrees of recursive unsolvability, Annals of Mathematics (2), vol. 64 (1956), pp. 581–592.CrossRefGoogle Scholar