Skip to main content
added 128 characters in body
Source Link
Dan Turetsky
  • 3.1k
  • 16
  • 27

I don't have an answer to the main question, but there is a noncomputable weakly antirandom real; in fact we can build a perfect c-csmz $\Pi^0_1$-class $Q$.

We have strategies for every partial computable sequence of epsilons $\psi$. A strategy begins by choosing a large $n$ and waiting until $\psi$ has converged on the first $2^{n+1}$ elements. Let $\epsilon_0$ be the least of these first $2^{n+1}$ epsilons, and $s$ the stage at which we see this convergence. For every $\sigma \in 2^{n+1}$ with $[\sigma] \cap Q_s$ not empty, our strategy chooses a $\tau$ extending $\sigma$ with $[\tau] \cap Q_s$ not empty and $\mu([\tau]) < \epsilon_0$ and declares that $[\sigma] \cap Q_{s+1} = [\tau] \cap Q_s$. Arrange these strategies in a finite injury construction.

Now we can define $\Phi$. Given a sequence of epsilons as an oracle, it waits until it sees some strategy act with $\epsilon_0$ and $n$ such that $\epsilon_0$ is no more than the least of the first $2^{n+1}$ elements of the sequence. When this occurs, we can define $I_0, \dots, I_{2^{n+1}-1}$ such that they cover all of $Q_{s+1}$ by covering the appropriate $\tau$. We will eventually see such a strategy as long as the oracle is a computable sequence of epsilons. We can define the remaining $I_k$ in any way consistent with the sequence.

Edit: In fact, any weakly 1-generic will be weakly antirandom. Just have $\Phi$ choose intervals in some dense fashion.

I don't have an answer to the main question, but there is a noncomputable weakly antirandom real; in fact we can build a perfect c-csmz $\Pi^0_1$-class $Q$.

We have strategies for every partial computable sequence of epsilons $\psi$. A strategy begins by choosing a large $n$ and waiting until $\psi$ has converged on the first $2^{n+1}$ elements. Let $\epsilon_0$ be the least of these first $2^{n+1}$ epsilons, and $s$ the stage at which we see this convergence. For every $\sigma \in 2^{n+1}$ with $[\sigma] \cap Q_s$ not empty, our strategy chooses a $\tau$ extending $\sigma$ with $[\tau] \cap Q_s$ not empty and $\mu([\tau]) < \epsilon_0$ and declares that $[\sigma] \cap Q_{s+1} = [\tau] \cap Q_s$. Arrange these strategies in a finite injury construction.

Now we can define $\Phi$. Given a sequence of epsilons as an oracle, it waits until it sees some strategy act with $\epsilon_0$ and $n$ such that $\epsilon_0$ is no more than the least of the first $2^{n+1}$ elements of the sequence. When this occurs, we can define $I_0, \dots, I_{2^{n+1}-1}$ such that they cover all of $Q_{s+1}$ by covering the appropriate $\tau$. We will eventually see such a strategy as long as the oracle is a computable sequence of epsilons. We can define the remaining $I_k$ in any way consistent with the sequence.

I don't have an answer to the main question, but there is a noncomputable weakly antirandom real; in fact we can build a perfect c-csmz $\Pi^0_1$-class $Q$.

We have strategies for every partial computable sequence of epsilons $\psi$. A strategy begins by choosing a large $n$ and waiting until $\psi$ has converged on the first $2^{n+1}$ elements. Let $\epsilon_0$ be the least of these first $2^{n+1}$ epsilons, and $s$ the stage at which we see this convergence. For every $\sigma \in 2^{n+1}$ with $[\sigma] \cap Q_s$ not empty, our strategy chooses a $\tau$ extending $\sigma$ with $[\tau] \cap Q_s$ not empty and $\mu([\tau]) < \epsilon_0$ and declares that $[\sigma] \cap Q_{s+1} = [\tau] \cap Q_s$. Arrange these strategies in a finite injury construction.

Now we can define $\Phi$. Given a sequence of epsilons as an oracle, it waits until it sees some strategy act with $\epsilon_0$ and $n$ such that $\epsilon_0$ is no more than the least of the first $2^{n+1}$ elements of the sequence. When this occurs, we can define $I_0, \dots, I_{2^{n+1}-1}$ such that they cover all of $Q_{s+1}$ by covering the appropriate $\tau$. We will eventually see such a strategy as long as the oracle is a computable sequence of epsilons. We can define the remaining $I_k$ in any way consistent with the sequence.

Edit: In fact, any weakly 1-generic will be weakly antirandom. Just have $\Phi$ choose intervals in some dense fashion.

Source Link
Dan Turetsky
  • 3.1k
  • 16
  • 27

I don't have an answer to the main question, but there is a noncomputable weakly antirandom real; in fact we can build a perfect c-csmz $\Pi^0_1$-class $Q$.

We have strategies for every partial computable sequence of epsilons $\psi$. A strategy begins by choosing a large $n$ and waiting until $\psi$ has converged on the first $2^{n+1}$ elements. Let $\epsilon_0$ be the least of these first $2^{n+1}$ epsilons, and $s$ the stage at which we see this convergence. For every $\sigma \in 2^{n+1}$ with $[\sigma] \cap Q_s$ not empty, our strategy chooses a $\tau$ extending $\sigma$ with $[\tau] \cap Q_s$ not empty and $\mu([\tau]) < \epsilon_0$ and declares that $[\sigma] \cap Q_{s+1} = [\tau] \cap Q_s$. Arrange these strategies in a finite injury construction.

Now we can define $\Phi$. Given a sequence of epsilons as an oracle, it waits until it sees some strategy act with $\epsilon_0$ and $n$ such that $\epsilon_0$ is no more than the least of the first $2^{n+1}$ elements of the sequence. When this occurs, we can define $I_0, \dots, I_{2^{n+1}-1}$ such that they cover all of $Q_{s+1}$ by covering the appropriate $\tau$. We will eventually see such a strategy as long as the oracle is a computable sequence of epsilons. We can define the remaining $I_k$ in any way consistent with the sequence.