3
$\begingroup$

A set $A$ is 1-generic if it forces its jump, namely for any $e\in\omega$, there exists $\sigma\preceq A$ such that: $\Phi^{\sigma}_{e}(e)\downarrow\vee(\forall\tau\succeq\sigma)(\Phi^{\tau}_{e}(e)\uparrow)$. Then in Cantor space $2^\omega$, what's the measure of $G=\{f\in2^{\omega}:f$ is 1-generic$\}$?

$\endgroup$
1
  • $\begingroup$ Probably best to clarify that you intend $A\subseteq\mathbb{N}$ here, and that $\preceq$ refers to the finite initial segment relation. Also, people often use a lower case $\varphi_e^\sigma$ where you have $\Phi_e^\sigma$, to refer to the function computed by program $e$ with $\sigma$ as oracle. $\endgroup$ Dec 28, 2022 at 20:37

1 Answer 1

5
$\begingroup$

It's measure 0. Almost every real is Martin-Löf random, and no random can be 1-generic.


Here's a direct argument, which can also be turned into an argument that no 1-generic is ML-random.

For any $n$, we can construct a computable set of strings $X$ which is dense and such that the measure of reals which meet $X$ is at most $2^{-n}$: let $(\sigma_i)_{i \in \omega}$ be a computable listing of strings. Let $\tau_i$ be the lexicographically least string of length at least $n+i+2$ and extending $\sigma_i$. Let $X = \{\tau_i : i \in \omega\}$. So the measure of reals extending some element of $X$ is at most $\sum_i 2^{-n-i-2} \le 2^{-n}$.

Now define $e$ such that $\Phi^A_e(e)\downarrow$ iff $A$ extends an element of $X$. Since $X$ is dense, the only way to force the jump at $e$ is to extend an element of $X$, so every 1-generic must do so. So the measure of 1-generics is at most $2^{-n}$. Since $n$ was arbitrary, the measure is 0.

$\endgroup$
2
  • $\begingroup$ It would be very kind of you, if you could you sketch the arguments for these... $\endgroup$ Dec 28, 2022 at 22:43
  • $\begingroup$ But also, I have a feeling there is a very direct argument. Something like: there must be infinitely many programs $e$ for which the reals handling $e$ in one way or the other have small measure. This would force the overall measure to zero. $\endgroup$ Dec 28, 2022 at 22:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.