4 votos

Títulos Turing en $\Sigma_3^0$ y $\Pi_1^0$ conjuntos.

Quiero demostrar que para cualquier $\Sigma_3^0$ conjunto de reales (por real entiendo un elemento del espacio de Baire $\omega^{\omega}$ ) $B$ hay un $\Pi_1^0$ conjunto de reales $A$ tal que para todos los grados de Turing $d$ , $B$ contiene un elemento de grado $d$ sólo si $A$ contiene un elemento de grado $d$ . La prueba propuesta es la siguiente: sea $R$ sea un conjunto recursivo de reales tal que para todo $\alpha\in\omega^\omega$ tenemos $$\alpha\in B\iff\exists i\forall j\exists k R(i, j, \bar{\alpha}(k)),$$ y que $$A=\{\langle i, \alpha, \beta\rangle:\forall j (\beta(j) = \mu k R(i, j, \bar{\alpha}(k)))\}.$$

Para ello, procedo del siguiente modo: para la dirección de avance, supongamos $\alpha\in B$ con grado de Turing $d$ . Entonces podemos tomar $i_0$ sea tal que $\forall j\exists k R(i_0, j, \bar{\alpha}(k))$ . Entonces podemos definir $\beta\in\omega^\omega$ como $\beta(j) = \mu k R(i_0, j, \bar{\alpha}(k))$ (conocemos las más pequeñas $k$ siempre existe, ya que $\alpha\in B$ ). Entonces, claramente $\langle i_0, \alpha, \beta\rangle\in A$ . Además, es el único elemento (que se me ocurre) que podemos construir en $A$ dado $\alpha\in B$ .

Demostrando que $[\alpha]\equiv_T [\langle i_0, \alpha, \beta\rangle]$ nos daría el resultado deseado. El sitio $\le_T$ dirección es obvia, pero la $\ge_T$ dirección no parece seguir. Construyendo $\langle i_0,\alpha, \beta\rangle$ de forma recursiva a partir de $\alpha$ no parece posible, ya que encontrar $i_0$ requiere una búsqueda ilimitada, al igual que encontrar $\beta$ . Se agradece cualquier ayuda.

1voto

Guest Puntos 11

Mostrar $(i_0, \alpha, \beta) \leq_T \alpha$ basta con demostrar que $\beta \leq_T \alpha$ ( $i_0$ es sólo un número entero).

Dado $j$ calcular $\beta(j)$ como sigue: Para cada $n < \omega$ Compruebe si $R(i_0, j, \alpha(n))$ retenciones. Estos cálculos pueden realizarse porque tenemos acceso a $\alpha$ . Sabemos que para algunos $n$ , $R(i_0, j, \alpha(n))$ se mantiene. Detener el cómputo en el menor $n$ y mostrarlo como $\beta(j)$ .

0 votos

Comprobación de $R(i_0, j, \alpha(n))$ puede hacerse con acceso a $\alpha$ sino encontrar $n$ estás haciendo una búsqueda ilimitada sobre $n<\omega$ (por $\omega$ Supongo que te refieres al primer ordinal infinito) -- por lo que no se trata de una recursividad en $\alpha$ procedimiento para encontrar $\beta$ . Si hay una manera de dar un límite $n < N$ donde $N$ depende de $\alpha$ entonces estaríamos bien, pero no estoy seguro de cómo hacer esto. Además, ¿por qué dices que es suficiente para mostrar $\beta\le_T\alpha$ ya que $i_0$ ¿es "sólo un número entero"? ¿Cómo se encuentra $i_0$ ? Esto también requeriría una búsqueda ilimitada para encontrar un $i$ satisfaciendo a R.

0 votos

La búsqueda del menor $n$ tal que $R(i_0, j, \alpha(n))$ no es ilimitada. Termina en un número finito de pasos. Compárese, por ejemplo, con un programa que a la entrada $j$ encontrar el menor primo por encima de $j$ buscando el menor $n$ sobre $j$ tal que $n$ es primo.

0 votos

Ok, ahora me doy cuenta de que mi pregunta es bastante tonta -- por alguna razón estaba pensando en las limitaciones de las funciones recursivas primitivas, pero el operador de minimización está totalmente bien en el dominio de las funciones recursivas.

i-Ciencias.com

I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.

Powered by:

X