Hostname: page-component-586b7cd67f-r5fsc Total loading time: 0 Render date: 2024-11-23T21:58:45.209Z Has data issue: false hasContentIssue false
  • English
  • Français

Decidability of the “almost all” theory of degrees

Published online by Cambridge University Press:  12 March 2014

John Stillwell
John Stillwell*
Affiliation:
Monash University, Clayton Victoria 3168, Australia
Get access Rights & Permissions [Opens in a new window]

Extract

Ever since Spector's brilliant application of measure theory to recursion theory in 1958 [6] it has been realized that measure theory promotes sweeping simplifications in the theory of degrees. Results previously thought to be pathological were shown by Spector, and later Sacks [4], [5], to hold for almost all degrees (“almost all” in the sense of Lebesgue measure), often with much simpler proofs. Good examples of this phenomenon are Spector's demonstration that almost all pairs of sets are of incomparable degree (as an immediate consequence of Fubini's theorem) and Sacks' exquisitely simple deduction from this result that almost every degree is the join of two incomparable degrees (for if a random sequence is decomposed into its even and odd parts, the result is a random pair).

The present paper attempts to vindicate the feeling that almost all degrees behave in a simple manner by showing that if the quantifier in the theory of degrees with ′(jump), ∪ (join) and ∩ (meet) is taken to be (almost ∀a) instead of (∀a) then the theory is decidable. We are able to use ∩ because it will be shown that if t1, t2 are any terms built from degree variables a1, …, am with ′ and ∪ then t1 ∩ t2 exists for almost all a1, …, am. Thus the “almost all” theory presents a sharp contrast to the standard theory, where ∩ is not always defined (Kleene-Post [1]) and which is known to be undecidable (Lachlan [2]).

Type
Research Article
Information
The Journal of Symbolic Logic , Volume 37 , Issue 3 , September 1972 , pp. 501 - 506
Copyright
Copyright © Association for Symbolic Logic 1972

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

REFERENCES

[1]Kleene, S. C. and Post, E. L., The upper semi-lattice of degrees of recursive unsolvability, Annals of Mathematics, (2) vol. 59 (1954), p. 379–407.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), p. 457–472.CrossRefGoogle Scholar
[3]Rogers, H. Jr., The theory of recursive functions and effective computability, McGraw-Hill, New York, 1967.Google Scholar
[4]Sacks, G. E., Degrees of unsolvability, Annals of Mathematics Studies, No. 55, Princeton University Press, Princeton, N.J., 1963.Google Scholar
[5]Sacks, G. E., Measure-theoretic uniformity in recursion theory and set theory, Transactions of the American Mathematical Society, vol. 142 (1969), p. 381–420.CrossRefGoogle Scholar
[6]Spector, C., Measure-theoretic construction of incomparable hyperdegrees, this Journal, vol. 23 (1958), p. 280–288.Google Scholar