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$ Commented 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$ Commented 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$ Commented Dec 28, 2022 at 22:48

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .