Separating weak \(\alpha\)-change and \(\alpha\)-change genericity (Q2140582)

In [\textit{M. McInerney} and \textit{K. M. Ng}, Isr. J. Math. 250, No. 1, 1--51 (2022; Zbl 07606042)], the authors introduced a transfinite hierarchy of genericity notions that are strictly between 1-genericity and 2-genericity. In [\textit{M. McInerney} and \textit{K. M. Ng}, Ann. Pure Appl. Logic 173, No. 7, Article ID 103134, 31 p. (2022; Zbl 07530350)], the paper under review, they show that, for every ordinal \(\alpha\) that is a power of \(\omega\) and it is either below or equal to \(\epsilon_0\), there is a \(\Delta^{0}_{2}\) Turing degree \(\mathbf{a}\) that is weakly \(\alpha\)-change generic but not \(\alpha\)-change generic. I provide some context to understand the result. In computability theory and, more specifically, in the study of degrees of unsolvability, one sees reals as infinite repositories of information rather than elements of an algebraic structure. Given access to the information encoded in a specific real, one may solve a given problem. On this basis, one defines different notions of reducibility of a problem to another. The most important of such notions is Turing reducibility, which is a pre-order and induces an equivalence relation among sets of reals. The equivalence classes are called Turing degrees. In many areas of mathematics, one defines several notions of typicality (genericity or randomness), i.e., informally, of what counts as a typical example of a class. In computability theory, Barmpalias and Lewis-Pye describe the study of typical reals as follows: one provides ``(a) a formalisation of the notion of `large' [set, e.g. being co-meager or being of measure 1]; (b) a restriction of the sets of reals that we consider to a countable class [e.g. countable collections definable in first-order arithmetic]; (c) the definition `typical real' as a real which occurs in every large set in this restricted class'' [\textit{G. Barmpalias} and \textit{A. Lewis-Pye}, in: Turing's revolution. The impact of his ideas about computability. Cham: Birkhäuser/Springer. 207--224 (2015; Zbl 1403.03067)]. In particular, for \(n\in\omega\), one defines the notion of \(n\)-\textit{generic} real as follows. Given \(W\subseteq \omega\), one says that a real \(A\) \textit{forces} \(W\) if and only if, for some initial segment \(\sigma\) of \(A\), either \(\sigma\in W\) or no extension of \(\sigma\) is in \(W\). Then, one says that a real is \(n\)-generic if and only if it forces every \(W\) that is computably enumerable relative to the Turing degree \(\emptyset^{(n-1)}\). Moreover, one says that a real is \textit{weakly} \(n\)-generic if and only if it forces every \(W\) such that (i) \(W\) is computably enumerable relative to \(\emptyset^{(n-1)}\) and, (ii) for each finite string, \(W\) contains an extension of that string. To justify the introduction of their new hierarchy of genericity notions between 1-genericity and 2-genericity, the authors write: ``Most of the interest in genericity occurs at the levels \(n=1\) and \(n=2\) \(\dots\) [T]here is a large difference in the behaviour of 1-generic and 2-generic [reals] \(\dots\) Given this, it [is] interesting to develop notions of genericity which are stronger than 1-genericity, but weaker than 2-genericity''. To introduce the new hierarchy, they generalize the so-called \textit{finite extension method}. The finite extension method allows one to construct in stages a real \(A\) that satisfies a countable sequence \((\psi_i)_{i<\omega}\) of conditions: at stage \(s\), having already constructed a finite binary string \(\sigma_{s-1}\), one constructs an extension \(\sigma_s\) of \(\sigma_{s-1}\) that satisfies \(\psi_s\) and such that every extension of \(\sigma_s\) also satisfies \(\psi_s\). Then, one let \(A= \bigcup_{s<\omega} \sigma_s\). The authors generalize this approach by considering finite extension arguments where one may use more than one attempt to satisfy a condition. The ordinal \(\alpha\) keeps track of how many times one acts to satisfy the given condition. Using the notions of uniform \(\alpha\)-change genericity, weak \(\alpha\)-change genericity, and \(\alpha\)-change genericity, the resulting hierarchy looks as follows: \begin{center} weakly \(2\)-generic \\ \(\Downarrow\) \\ \(\vdots\) \\ \(\Downarrow\) \\ \(\omega^2\)-change generic \\ \(\Downarrow\) \\ weakly \(\omega^2\)-change generic \\ \(\Downarrow\) \\ uniformly \(\omega^2\)-change generic \\ \(\Downarrow\) \\ \(\omega\)-change generic \\ \(\Downarrow\) \\ weakly \(\omega\)-change generic \\ \(\Downarrow\) \\ uniformly \(\omega\)-change generic (\(\equiv\) pb-generic) \\ \(\Downarrow\) \\ 1-change generic (\(\equiv\) 1-generic) \\ \(\Downarrow\) \\ weakly 1-change generic. \end{center} The authors refer to this hierarchy as the \textit{hierarchy of multiple genericity notions}. They show that, for every ordinal \(\beta\) such that \(\omega^\beta \leq \epsilon_0\), there is a \(\Delta^{0}_{2}\) Turing degree that is not \(\omega^\beta\)-computably approximable dominated and that does not compute an \(\omega^\beta\)-change generic degree. Then they show what they present as the main result of the paper: for every \(\beta\) as above, there is a \(\Delta^{0}_{2}\) Turing degree that is weakly \(\omega^\beta\)-change generic but not \(\omega^\beta\)-change generic. In [\textit{M. McInerney} and \textit{K. M. Ng}, Isr. J. Math. 250, No. 1, 1--51 (2022; Zbl 07606042)], the authors have shown that, for every \(\beta\) as before, there is a \(\Delta^{0}_{2}\) degree that is \(\omega^\beta\)-generic but not uniformly \(\omega^{\beta+1}\)-change generic. From these results, they conclude that there is a \(\Delta^{0}_{2}\) Turing degree separation of each level in the hierarchy of multiple genericity notions.