The random members of a ${\Pi }_1^0$ class

Abstract

We examine several notions of randomness for elements in a given ${\Pi }_1^0$ class $\mathcal{P}$. Such an effectively closed subset $\mathcal{P}$ of $2^{\omega }$ may be viewed as the set of infinite paths through the tree $T_{\mathcal{P}}$ of extendible nodes of $\mathcal{P}$, i.e., those finite strings that extend to a member of $\mathcal{P}$, so one approach to defining a random member of $\mathcal{P}$ is to randomly produce a path through $T_{\mathcal{P}}$ using a sufficiently random oracle for advice. In addition, this notion of randomness for elements of $\mathcal{P}$ may be induced by a map from $2^{\omega }$ onto $\mathcal{P}$ that is computable relative to $T_{\mathcal{P}}$, and the notion even has a characterization in term of Kolmogorov complexity. Another approach is to define a relative measure on $\mathcal{P}$ by conditionalizing the Lebesgue measure on $\mathcal{P}$, which becomes interesting if $\mathcal{P}$ has Lebesgue measure 0. Lastly, one can alternatively define a notion of incompressibility for members of $\mathcal{P}$ in terms of the amount of branching at levels of $T_{\mathcal{P}}$. We explore some notions of homogeneity for ${\Pi }_1^0$ classes, inspired by work of van Lambalgen. A key finding is that in a specific class of sufficiently homogeneous ${\Pi }_1^0$ classes $\mathcal{P}$, each of these approaches coincides. We conclude with a discussion of random members of ${\Pi }_1^0$ classes of positive measure.