Abstract We generalize the analysis of Andrews, Schweber and Sorbi of the first-order theory of the partial order of degrees of c.e. equivalence relations to higher computability theory, specifically to the setting of a regular cardinal.

Abstract A computably enumerable equivalence relation (ceer) $X$ is called self-full if whenever $f$ is a reduction of $X$ to $X$, then the range of $f$ intersects all $X$-equivalence classes. It is known that the infinite self-full ceers properly contain the dark ceers, i.e. the infinite ceers which do not admit an infinite computably enumerable transversal. Unlike the collection of dark ceers, which are closed under the operation of uniform join, we answer a question from [ 4] by showing that there are self-full ceers $X$ and $Y$ so that their uniform join $X\oplus Y$ is non-self-full. We then define and examine the hereditarily self-full ceers, which are the self-full ceers $X$ so that for any self-full $Y$, $X\oplus Y$ is also self-full: we show that they are closed under uniform join and that every non-universal degree in ${\operatorname{\textbf{Ceers}}}_{\operatorname{{\mathcal{I}}}}$ have infinitely many incomparable hereditarily self-full strong minimal covers. In particular, every non-universal ceer is bounded by a hereditarily self-full ceer. Thus, the hereditarily self-full ceers form a properly intermediate class in between the dark ceers and the infinite self-full ceers, which is closed under $\oplus $.

Abstract In [8], the third author defined a reducibility $\le _w^{\rm{*}}$ that lets us compare the computing power of structures of any cardinality. In [6], the first two authors showed that the ordered field of reals ${\cal R}$ lies strictly above certain related structures. In the present paper, we show that $\left( {{\cal R},exp} \right) \equiv _w^{\rm{*}}{\cal R}$ . More generally, for the weak-looking structure ${\cal R}$ ℚconsisting of the real numbers with just the ordering and constants naming the rationals, allo-minimal expansions of ${\cal R}$ ℚare equivalent to ${\cal R}$ . Using this, we show that for any analytic functionf, $\left( {{\cal R},f} \right) \equiv _w^{\rm{*}}{\cal R}$ . (This is so even if $\left( {{\cal R},f} \right)$ is noto-minimal.)

Abstract In this paper, we investigate connections between structures present in every generic extension of the universe V and computability theory. We introduce the notion of generic Muchnik reducibility that can be used to compare the complexity of uncountable structures; we establish basic properties of this reducibility, and study it in the context of generic presentability, the existence of a copy of the structure in every extension by a given forcing. We show that every forcing notion making ω2 countable generically presents some countable structure with no copy in the ground model; and that every structure generically presentable by a forcing notion that does not make ω2 countable has a copy in the ground model. We also show that any countable structure ${\cal A}$ that is generically presentable by a forcing notion not collapsing ω1 has a countable copy in V, as does any structure ${\cal B}$ generically Muchnik reducible to a structure ${\cal A}$ of cardinality ℵ1. The former positive result yields a new proof of Harrington’s result that counterexamples to Vaught’s conjecture have models of power ℵ1 with Scott rank arbitrarily high below ω2. Finally, we show that a rigid structure with copies in all generic extensions by a given forcing has a copy already in the ground model.

Abstract In this paper we investigate the reverse mathematics of higher-order analogues of the theory $$ATR_0$$ within the framework of higher order reverse mathematics developed by Kohlenbach [11]. We define a theory $$RCA_0^3$$ , a close higher-type analogue of the classical base theory $$RCA_0$$ which is essentially a conservative subtheory of Kohlenbach’s base theory $$RCA_{\rm{0}}^\omega$$ . Working over $$RCA_0^3$$ , we study higher-type analogues of statements classically equivalent to $$ATR_0$$ , including open and clopen determinacy, and examine the extent to which $$ATR_0$$ remains robust at higher types. Our main result is the separation of open and clopen determinacy for reals, using a variant of Steel’s tagged tree forcing; in the presentation of this result, we develop a new, more flexible framework for Steel-type forcing.