Hostname: page-component-7b7567c8c-7pwfn Total loading time: 0 Render date: 2026-11-17T02:50:08.261Z Has data issue: false hasContentIssue false

Minimal upper bounds for arithmetical degrees

Published online by Cambridge University Press:  12 March 2014

Masahiro Kumabe*
Affiliation:
The University of the Air, 2-11, Wakaba, Mihama-Ku, Chiba 261, Japan

Extract

This paper was inspired by Lerman [14] in which he proved various properties of upper bounds for the arithmetical degrees. The degrees which are upper bounds for the arithmetical degrees were first studied by Hodes [5] and Enderton and Putnam [5]. Enderton and Putnam [5] showed that if a is an upper bound for the arithmetical degrees, then a (2) ≥ 0(ω). This area was further studied by Hodes [5], Knight, Lachlan and Soare [12], Jockusch and Simpson [12], and Sacks [17].

Enderton and Putnam [5] and Sacks [17] have combined to show that 0(ω) is the least degree in {a (2): a is an upper bound for the arithmetical degrees}. So there seem to be some analogies between the degrees of upper bounds for the arithmetical degrees and the degrees below 0(2). But Sacks [17] showed an important difference between these two structures; namely, the Turing jumps of upper bounds for the arithmetical degrees have no least element. In Lerman [14], a systematic investigation of properties of the jumps of upper bounds for the arithmetical degrees was suggested, which could lead to a definition of the jump operator over the elementary theory of the partial ordering of the degrees. Although Cooper [5] found a degree-theoretic definition of the jump operator, Lerman's plan is still interesting.

We say a degree a is generic if there is a representative A of a such that A is Cohen generic for the arithmetical sentences. By Jockusch [5], the statement that A is Cohen generic for the arithmetical sentences is equivalent to saying that for any arithmetical set S of binary strings, there is a σ extended by A such that σ is in S or no extension of σ is in S. First, we investigate the relation between generic degrees and upper bounds for the arithmetical degrees. In the case D(≤ 0′), the set of degrees below 0′, it is well known that any nonrecursive r.e. degree bounds a 1-generic degree (Cohen generic for Σ1 sentences). Jockusch and Ponser [12] showed that any degree a with a″ >T (a ∪ 0′)′ bounds a 1-generic degree.

Information

Type
Research Article
Copyright
Copyright © Association for Symbolic Logic 1994

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.)

Article purchase

Temporarily unavailable