4

Some definitions: A set is $immune$ if it is infinite but contains no infinite r.e. subset. Given a finite set $A = \{x_1 < x_2 < · · · < x_k\}$, the number $y = 2^{x_1} + 2^{x_2} + · · · + 2^{x_k}$ is called the canonical index of A. Let $D_y$ denote finite set with canonical index y, and $D_0$ denote $\emptyset$. A sequence $\{F_n\}_{n\in \omega}$ of finite sets is a strong array if there is a recursive function $f$ such that $F_n = D_{f(n)}$. A set $B$ is hyperimmune if there is no disjoint strong array $\{F_n\}_{n\in \omega}$ such that $F_n\cap B\neq \emptyset$.

Assume $A$ is 1-generic.

(a) prove $A$ is immune and hyperimmune.

(b) prove there is no non-recursive r.e. set $V\leq_T A$.

(c) Let $A_0 = \{n : 2n \in A\}$ and $A_1 = \{n : 2n + 1 \in A\}$. Show that $A_0$ and $A_1$ are Turing incomparable.

I can prove (a),(b). For (c) I am stuck:

If $A_0\le_T A_1$, then $A_0=\phi_e^{A_1}$ for some $e$. Then for all $x$ there is an initial segment $\sigma$ of $A$ that $\sigma_0(x) = \phi_e^{\sigma_1}(x)$, where $\sigma_0, \sigma_1$ are defined for $\sigma$ analogous to how $A_0, A_1$ are defined for $A$. Consider $W_e=\{\sigma: \exists x(\phi_e^{\sigma_1}(x)\downarrow \neq \sigma_0(x))\}$ which is r.e. By 1-genericity of $A$ there is $\sigma\subset A$ such that $\sigma \in W_e $ or $\sigma'\notin W_e$ for any extension $\sigma'$ of $\sigma$.

Now if $\sigma \in W_e$ we are done, because then $\phi_e^{A_1}\neq A_0$ at some point $x$ given by the condition in $W_e$. I am not sure what to do when the other case occurs. Equivalently it translates to $\forall x(\phi_e^{\sigma'_1}(x)\uparrow \vee \phi_e^{\sigma'_1}(x)\downarrow=\sigma'_0(x))$. It seems to imply that $\phi_e^{A_1}$ is indeed $A_0$, which is strange...

Jun Xu
  • 449

1 Answers1

1

Just to be absolutely clear, since both $\Phi_e^{\sigma_1}$ and $\sigma_0$ are partial functions, by $\Phi_e^{\sigma_1}(x)\downarrow \; \neq \sigma_0(x)$ I mean: $$ (\Phi_e^{\sigma_1}(x)\downarrow \; \wedge \; \sigma_0(x)\downarrow) \wedge \Phi_e^{\sigma_1}(x) \neq \sigma_0(x) $$ As far as your question is concerned, this interpretation works perfectly fine.

You are close, all that you need to show is that we must have $\sigma \in W_e$. That is:

Claim. If $\sigma \preceq \chi_A$ and $\sigma$ witnesses that $A \Vdash W_e$, then $\sigma \in W_e$.

Proof. Suppose not, then we must have: $$ (\forall \rho \succeq \sigma)(\forall x)[\Phi_e^{\rho_1}(x)\uparrow \; \vee \; \rho_0(x)\uparrow \; \vee \; (\Phi_e^{\rho_1}(x)\downarrow \; \wedge \; \Phi_e^{\rho_1}(x) = \rho_0(x))] $$ There are two possible cases:

  1. If: $$ (\exists \rho_1 \succeq \sigma_1)(\exists x)[x \in \operatorname{dom}(\Phi_e^{\rho_1}) \wedge (x \notin \operatorname{dom}(\sigma_0) \vee \Phi_e^{\rho_1}(x) \neq \sigma_0(x)] $$ If $\Phi_e^{\rho_1}(x) \neq \sigma_0(x)$, then we immediately get a contradiction. Otherwise, we have $x \notin \operatorname{dom}(\sigma_0)$, so we may choose $\rho \succeq \sigma$ such that $\rho_0 \succeq \sigma_0$ and $\Phi_e^{\rho_1}(x) \neq \rho_0(x)$m, also a contradiction.

  2. Otherwise, we have: $$ (\forall \rho_1 \succeq \sigma_1)(\forall x)[x \in \operatorname{dom}(\Phi_e^{\rho_1}) \to (x \in \operatorname{dom}(\sigma_0) \wedge \Phi_e^{\rho_1}(x) = \sigma_0(x)] $$ then $\bigcup_{\rho_1 \succeq \sigma_1} \operatorname{dom}(\Phi_e^{\rho_1}) \subseteq \operatorname{dom}(\sigma_0)$ is finite, so one may take $x \notin \bigcup_{\rho_1 \succeq \sigma_1} \operatorname{dom}(\Phi_e^{\rho_1})$ and extend $\rho \succeq \sigma$ such that $x \in \operatorname{dom}(\rho_0)$, also a contradiction. $\square$

Let me explain the intuition behind the proof. The first case asserts that we can find an $x$ in $\operatorname{dom}(\Phi_e^{\rho_1})$ that conflicts with $\sigma_0$. If it disagrees from the start ($\Phi_e^{\rho_1}(x) \neq \sigma_0(x)$), then we have the contradiction. Otherwise, it is that $\sigma_0$ is not defined at $x$ ($x \notin \operatorname{dom}(\sigma_0)$), so we can extend $\sigma$ such that $\sigma_0(x) \neq \Phi_e^{\rho_1}(x)$.

The second case says that, no matter how you extend $\sigma_1$ with $\rho_1$, $\Phi_e^{\rho_1}$ has domain bounded by the domain of $\sigma_0$. But $\sigma_0$ is just a finite string, so we can extend $\sigma$ to $\rho$ which $\rho_0$ has domain strictly larger than all possible domains of $\Phi_e^{\rho_1}$, yielding the desired contradiction.

Clement Yung
  • 8,347