Abstract We show that a computable function $f:\mathbb R\rightarrow \mathbb R$ has Luzin’s property (N) if and only if it reflects $\Pi ^1_1$ -randomness, if and only if it reflects $\Delta ^1_1({\mathcal {O}})$ -randomness, and if and only if it reflects ${\mathcal {O}}$ -Kurtz randomness, but reflecting Martin–Löf randomness or weak-2-randomness does not suffice. Here a function f is said to reflect a randomness notion R if whenever $f(x)$ is R-random, then x is R-random as well. If additionally f is known to have bounded variation, then we show f has Luzin’s (N) if and only if it reflects weak-2-randomness, and if and only if it reflects $\emptyset '$ -Kurtz randomness. This links classical real analysis with algorithmic randomness.

We present what is known about the reverse mathematical strength of weak theorems involving Borel sets.

Abstract We define the notion of a completely determined Borel code in reverse mathematics, and consider the principle $CD - PB$ , which states that every completely determined Borel set has the property of Baire. We show that this principle is strictly weaker than $AT{R_0}$ . Any ω-model of $CD - PB$ must be closed under hyperarithmetic reduction, but $CD - PB$ is not a theory of hyperarithmetic analysis. We show that whenever $M \subseteq {2^\omega }$ is the second-order part of an ω-model of $CD - PB$ , then for every $Z \in M$ , there is a $G \in M$ such that G is ${\rm{\Delta }}_1^1$ -generic relative to Z.

Abstract Let ${\cal S}$ be a Scott set, or even an ω-model of WWKL. Then for each A ε S, either there is X ε S that is weakly 2-random relative to A, or there is X ε S that is 1-generic relative to A. It follows that if A1,…,An ε S are noncomputable, there is X ε S such that each Ai is Turing incomparable with X, answering a question of Kučera and Slaman. More generally, any ∀∃ sentence in the language of partial orders that holds in ${\cal D}$ also holds in ${{\cal D}^{\cal S}}$ , where ${{\cal D}^{\cal S}}$ is the partial order of Turing degrees of elements of ${\cal S}$ .

Abstract We examine the computable part of the differentiability hierarchy defined by Kechris and Woodin. In that hierarchy, the rank of a differentiable function is an ordinal less than ${\omega _1}$ which measures how complex it is to verify differentiability for that function. We show that for each recursive ordinal $\alpha > 0$ , the set of Turing indices of $C[0,1]$ functions that are differentiable with rank at most α is ${{\rm{\Pi }}_{2\alpha + 1}}$ -complete. This result is expressed in the notation of Ash and Knight.