{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,29]],"date-time":"2026-03-29T15:26:29Z","timestamp":1774797989894,"version":"3.50.1"},"reference-count":6,"publisher":"Cambridge University Press (CUP)","issue":"3","license":[{"start":{"date-parts":[[2014,3,12]],"date-time":"2014-03-12T00:00:00Z","timestamp":1394582400000},"content-version":"unspecified","delay-in-days":15167,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J. symb. log."],"published-print":{"date-parts":[[1972,9]]},"abstract":"<jats:p>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 (\u201calmost all\u201d 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).<\/jats:p><jats:p>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 \u2032(jump), \u222a (join) and \u2229 (meet) is taken to be (almost \u2200<jats:bold>a<\/jats:bold>) instead of (\u2200<jats:bold>a<\/jats:bold>) then the theory is decidable. We are able to use \u2229 because it will be shown that if <jats:italic>t<\/jats:italic><jats:sub>1<\/jats:sub>, <jats:italic>t<\/jats:italic><jats:sub>2<\/jats:sub> are any terms built from degree variables <jats:bold>a<\/jats:bold><jats:sub>1<\/jats:sub>, \u2026, <jats:bold>a<\/jats:bold><jats:sub><jats:italic>m<\/jats:italic><\/jats:sub> with \u2032 and \u222a then <jats:italic>t<\/jats:italic><jats:sub>1<\/jats:sub> \u2229 <jats:italic>t<\/jats:italic><jats:sub>2<\/jats:sub> exists for almost all <jats:bold>a<\/jats:bold><jats:sub>1<\/jats:sub>, \u2026, <jats:bold>a<\/jats:bold><jats:sub><jats:italic>m<\/jats:italic><\/jats:sub>. Thus the \u201calmost all\u201d theory presents a sharp contrast to the standard theory, where \u2229 is not always defined (Kleene-Post [1]) and which is known to be undecidable (Lachlan [2]).<\/jats:p>","DOI":"10.2307\/2272735","type":"journal-article","created":{"date-parts":[[2006,5,6]],"date-time":"2006-05-06T21:17:55Z","timestamp":1146950275000},"page":"501-506","source":"Crossref","is-referenced-by-count":18,"title":["Decidability of the \u201calmost all\u201d theory of degrees"],"prefix":"10.1017","volume":"37","author":[{"given":"John","family":"Stillwell","sequence":"first","affiliation":[]}],"member":"56","published-online":{"date-parts":[[2014,3,12]]},"reference":[{"key":"S0022481200079044_ref006","first-page":"280","volume":"23","author":"Spector","year":"1958","journal-title":"Measure-theoretic construction of incomparable hyperdegrees"},{"key":"S0022481200079044_ref004","volume-title":"Annals of Mathematics Studies","author":"Sacks","year":"1963"},{"key":"S0022481200079044_ref002","doi-asserted-by":"publisher","DOI":"10.1002\/malq.19680143002"},{"key":"S0022481200079044_ref001","doi-asserted-by":"publisher","DOI":"10.2307\/1969708"},{"key":"S0022481200079044_ref005","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-1969-0253895-6"},{"key":"S0022481200079044_ref003","volume-title":"The theory of recursive functions and effective computability","author":"Rogers","year":"1967"}],"container-title":["Journal of Symbolic Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0022481200079044","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,30]],"date-time":"2019-05-30T20:57:42Z","timestamp":1559249862000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0022481200079044\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1972,9]]},"references-count":6,"journal-issue":{"issue":"3","published-print":{"date-parts":[[1972,9]]}},"alternative-id":["S0022481200079044"],"URL":"https:\/\/doi.org\/10.2307\/2272735","relation":{},"ISSN":["0022-4812","1943-5886"],"issn-type":[{"value":"0022-4812","type":"print"},{"value":"1943-5886","type":"electronic"}],"subject":[],"published":{"date-parts":[[1972,9]]}}}