Upper bounds for the arithmetical degrees (Q1086229): Difference between revisions

We show that there is an upper bound \(\underset \tilde{} d\) for the arithmetical degrees such that \(\underset \tilde{} d'\geq \underset \tilde{} 0^{(\omega)}\) but \(\underset \tilde{} d\) is not the degree of a subuniform upper bound for the arithmetical sets. It then follows that this degree is not the degree of a model of the elementary theory of the semiring of natural numbers. We next turn to comparisons of the upper bounds for the arithmetical degrees below \(\underset \tilde{} 0^{(\omega)}\) and the degrees below \(\underset \tilde{} 0^{(2)}\). We show that all uniform upper bounds for the arithmetical functions bound minimal upper bounds for the arithmetical degrees. We then introduce a counterpart of the generalized high/low hierarchy which is useful for studying upper bounds for the arithmetical degrees. We first locate minimal upper bounds for the arithmetical degrees within this hierarchy. We then give a direct proof of a result hidden in a paper of \textit{J. Knight}, \textit{A. H. Lachlan}, and \textit{R. I. Soare} [J. Symb. Logic 49, 425-436 (1984; Zbl 0576.03044)] which relates jumps of upper bounds for the arithmetical degrees to uniform upper bounds for the arithmetical functions. Finally, we determine which classes of this hierarchy are non-empty. The conclusion discusses open questions.