Computabilidad de Soare Turing[2016] ejercicio 6.3.5

Question

Algunas definiciones: Un conjunto es $immune$ si es infinito pero no contiene ningún subconjunto infinito r.e. Dado un conjunto finito $A = \{x_1 < x_2 < · · · < x_k\}$ el número $y = 2^{x_1} + 2^{x_2} + · · · + 2^{x_k}$ se llama índice canónico de A. Sea $D_y$ denotan conjunto finito con índice canónico y, y $D_0$ denotan $\emptyset$ . Una secuencia $\{F_n\}_{n\in \omega}$ de conjuntos finitos es un fuerte matriz si hay una función recursiva $f$ tal que $F_n = D_{f(n)}$ . Un conjunto $B$ es hiperinmune si no hay una matriz fuerte disjunta $\{F_n\}_{n\in \omega}$ tal que $F_n\cap B\neq \emptyset$ .

Supongamos que $A$ es 1-generico.

(a) demostrar $A$ es inmune e hiperinmune.

(b) demostrar que no existe un conjunto no recursivo r.e. $V\leq_T A$ .

(c) Que $A_0 = \{n : 2n \in A\}$ y $A_1 = \{n : 2n + 1 \in A\}$ . Mostrar que $A_0$ y $A_1$ son incomparables de Turing.

Puedo demostrar (a),(b). Para (c) estoy atascado:

Si $A_0\le_T A_1$ entonces $A_0=\phi_e^{A_1}$ para algunos $e$ . Entonces, para todos los $x$ hay un segmento inicial $\sigma$ de $A$ que $\sigma_0(x) = \phi_e^{\sigma_1}(x)$ , donde $\sigma_0, \sigma_1$ se definen para $\sigma$ de forma análoga a como $A_0, A_1$ se definen para $A$ . Considere $W_e=\{\sigma: \exists x(\phi_e^{\sigma_1}(x)\downarrow \neq \sigma_0(x))\}$ que es r.e. Por la 1-genericidad de $A$ hay $\sigma\subset A$ tal que $\sigma \in W_e $ o $\sigma'\notin W_e$ para cualquier extensión $\sigma'$ de $\sigma$ .

Ahora bien, si $\sigma \in W_e$ hemos terminado, porque entonces $\phi_e^{A_1}\neq A_0$ en algún momento $x$ dada por la condición en $W_e$ . No sé qué hacer cuando se da el otro caso. Equivalentemente se traduce en $\forall x(\phi_e^{\sigma'_1}(x)\uparrow \vee \phi_e^{\sigma'_1}(x)\downarrow=\sigma'_0(x))$ . Parece implicar que $\phi_e^{A_1}$ es de hecho $A_0$ Lo cual es extraño...

Answer 1

Sólo para ser absolutamente claro, ya que ambos $\Phi_e^{\sigma_1}$ y $\sigma_0$ son funciones parciales, por $\Phi_e^{\sigma_1}(x)\downarrow \; \neq \sigma_0(x)$ Es decir: $$ (\Phi_e^{\sigma_1}(x)\downarrow \; \wedge \; \sigma_0(x)\downarrow) \wedge \Phi_e^{\sigma_1}(x) \neq \sigma_0(x) $$ En cuanto a su pregunta, esta interpretación funciona perfectamente.

Estás cerca, todo lo que necesitas mostrar es que debemos tener $\sigma \in W_e$ . Es decir:

Reclamación. Si $\sigma \preceq \chi_A$ y $\sigma$ testigos que $A \Vdash W_e$ entonces $\sigma \in W_e$ .

Prueba. Supongamos que no, entonces debemos tener: $$ (\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))] $$ Hay dos casos posibles:

1. Si: $$ (\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)] $$ Si $\Phi_e^{\rho_1}(x) \neq \sigma_0(x)$ Entonces obtenemos inmediatamente una contradicción. En caso contrario, tenemos $x \notin \operatorname{dom}(\sigma_0)$ por lo que podemos elegir $\rho \succeq \sigma$ tal que $\rho_0 \succeq \sigma_0$ y $\Phi_e^{\rho_1}(x) \neq \rho_0(x)$ m, también una contradicción.

2. Por lo demás, tenemos: $$ (\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)] $$ entonces $\bigcup_{\rho_1 \succeq \sigma_1} \operatorname{dom}(\Phi_e^{\rho_1}) \subseteq \operatorname{dom}(\sigma_0)$ es finito, por lo que se puede tomar $x \notin \bigcup_{\rho_1 \succeq \sigma_1} \operatorname{dom}(\Phi_e^{\rho_1})$ y ampliar $\rho \succeq \sigma$ tal que $x \in \operatorname{dom}(\rho_0)$ También es una contradicción. $\square$

Permítanme explicar la intuición detrás de la prueba. El primer caso afirma que podemos encontrar un $x$ en $\operatorname{dom}(\Phi_e^{\rho_1})$ que entra en conflicto con $\sigma_0$ . Si no está de acuerdo desde el principio ( $\Phi_e^{\rho_1}(x) \neq \sigma_0(x)$ ), entonces tenemos la contradicción. En caso contrario, es que $\sigma_0$ no se define en $x$ ( $x \notin \operatorname{dom}(\sigma_0)$ ), por lo que podemos ampliar $\sigma$ tal que $\sigma_0(x) \neq \Phi_e^{\rho_1}(x)$ .

El segundo caso dice que, no importa cómo se extienda $\sigma_1$ con $\rho_1$ , $\Phi_e^{\rho_1}$ tiene un dominio delimitado por el dominio de $\sigma_0$ . Pero $\sigma_0$ es sólo una cadena finita, por lo que podemos extender $\sigma$ a $\rho$ que $\rho_0$ tiene un dominio estrictamente mayor que todos los posibles dominios de $\Phi_e^{\rho_1}$ , dando lugar a la contradicción deseada.