2000
Quantifier Variations in Solovay Reducibility

Solovay reducibility, a key concept in algorithmic randomness, allows us to compare the randomness of real numbers by looking at how quickly they can be approximated. It has become an essential tool for understanding how real numbers are structured in computability theory. In this talk, we explore variations in characterizations of this concept, focusing on how different quantifier choices affect its application to various types of real numbers.
Originally introduced by Solovay (1975), the concept involves a relation between two reals, $\alpha$ and $\beta$, using a function from $\mathbb{Q}$ to $\mathbb{Q}$ that computably transforms an approximation of $\beta$ to that of $\alpha$. Later, Downey et al. (2004) characterized Solovay reducibility for left-c.e. reals using increasing computable approximations $(a_n)_n$ and $(b_n)_n$ of $\alpha$ and $\beta$ respectively. For left-c.e. reals, using universal ($\forall$) or existential ($\exists$) quantifiers for $(a_n)_n$ and $(b_n)_n$ often leads to equivalent concepts, thus a robust notion.
Zheng and Rettinger (2004) introduced a new Solovay reducibility for computably approximable (c.a.) reals, which coincides with the original concept for left-c.e. reals and behaves better for c.a. reals. Their definition uses $\exists$ for both $(a_n)_n$ and $(b_n)_n$. Some researchers may believe the robustness also applies to c.a. reals. However, this is not true. We demonstrate that altering an existential quantifier ($\exists$) to a universal quantifier ($\forall$) in the definition of Solovay reducibility for c.a. reals leads to a different notion.
We demonstrate the non-equivalence that arises when altering quantifiers, supported by specific counterexamples, which are constructed by finite injury method.