The Sacks Density Theorem [7] states that the Turing degrees of the recursively enumerable sets are dense. We show that the Density Theorem holds in every model of P - + BΣ 2 . The proof has two components: a lemma that in any model of P - + BΣ 2 , if B is recursively enumerable and incomplete then IΣ 1 holds relative to B and an adaptation of Shore's [9] blocking technique in α-recursion theory to models of arithmetic.

We show, however, that this is not always the case.

We show that that every countable model of PA has a conservative extension M with a subset Y such that a certain Σ1(Y)-formula defines in M a subset which is not r. e. relative to Y.

We study the Lindenbaum algebra ${\fancyscript{A}}$ (WKL o, RCA o) of sentences in the language of second-order arithmetic that imply RCA o and are provable from WKL o. We explore the relationship between ${\Sigma^1_1}$ sentences in ${\fancyscript{A}}$ (WKL o, RCA o) and ${\Pi^0_1}$ classes of subsets of ω. By applying a result of Binns and Simpson (Arch. Math. Logic 43(3), 399–414, 2004) about ${\Pi^0_1}$ classes, we give a specific embedding of the free distributive lattice with countably many generators into ${\fancyscript{A}}$ (...) (WKL o, RCA o). (shrink)

Sacks [23] asks if the metarecursively enumerable degrees are elementarily equivalent to the r.e. degrees. In unpublished work, Slaman and Shore proved that they are not. This paper provides a simpler proof of that result and characterizes the degree of the theory as [Formula: see text] or, equivalently, that of the truth set of [Formula: see text].

The foundation scheme in set theory asserts that every nonempty class has an ∈\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\in $$\end{document}-minimal element. In this paper, we investigate the logical strength of the foundation principle in basic set theory and α\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\alpha $$\end{document}-recursion theory. We take KP set theory without foundation as the base theory. We show that KP-\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$^-$$\end{document} + Π1\documentclass[12pt]{minimal} \usepackage{amsmath} (...) \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\Pi _1$$\end{document}-Foundation + V=L\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$V=L$$\end{document} is enough to carry out finite injury arguments in α\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\alpha $$\end{document}-recursion theory, proving both the Friedberg-Muchnik theorem and the Sacks splitting theorem in this theory. In addition, we compare the strengths of some fragments of KP. (shrink)

We explore the complexity of Sacks’ Splitting Theorem in terms of the mind change functions associated with the members of the splits. We prove that, for any c.e. set A, there are low computably enumerable sets $A_0\sqcup A_1=A$ splitting A with $A_0$ and $A_1$ both totally $\omega ^2$ -c.a. in terms of the Downey–Greenberg hierarchy, and this result cannot be improved to totally $\omega $ -c.a. as shown in [9]. We also show that if cone avoidance is added then there (...) is no level below $\varepsilon _0$ which can be used to characterize the complexity of $A_1$ and $A_2$. (shrink)