Primera reflexión teorema de $\Pi_1^1$ $\Pi_1^1$ propiedades

Question

Deje $\Phi\subseteq\mathcal{P}(\mathcal{X})$ ser una colección de subconjuntos de a $\mathcal{X}$. Podemos decir $\Phi$ $\Pi_1^1$ $\Pi_1^1$ si para $A\subseteq\mathbb{N}\times\mathcal{X}$, $A\in \Pi_1^1$, el conjunto de secciones $\{n:A_n\in\Phi\}$$\Pi_1^1$. Del mismo modo definir lo que significa para $\Phi$$\Pi_1^1$$\Sigma_1^1$. Por lo $\Phi$ puede ser considerado como una "propiedad" de los conjuntos de

La primera reflexión teorema dice lo siguiente: Si $\Phi$$\Pi_1^1$$\Pi_1^1$$A$$\Pi_1^1$, luego $$\Phi(A)\implies\exists B\in\Delta_1^1 (B\subseteq A \wedge \Phi(B)).$$ An equivalent formulation is that if $\Phi$ is $\Pi_1^1$ on $\Sigma_1^1$, and $$ is $\Sigma_1^1$, then $$\Phi(A)\implies\exists B\in\Delta_1^1(B\supseteq A\wedge\Phi(B)).$$ This easily follows from the first formulation by taking $\Phi'(A)=\Phi(\neg a)$.

La prueba de este teorema se da de la siguiente manera:

Prueba: Supongamos que no. Tomar $W\subseteq\mathbb{N}$, $W\in\Pi_1^1\setminus\Delta_1^1$. Deje $U\subseteq\mathcal{N}$ $\Pi_1^1$- completo, y dejar que $\varphi:U\to\operatorname{Ordinals}$ $\Pi_1^1$- rango en $U$. Entonces, hay un total funciones recursivas $f$ $g$ tal que $x\in A\iff f(x)\in U$ $n\in W\iff g(n)\in U$ (esto es sólo la definición de integridad). Ahora, aquí es la parte que estoy teniendo problemas para envolver mi cabeza alrededor. La prueba va a decir que todo esto significa que

$$n\notin W\iff\Phi(\{x:f(x)<_{\varphi}^*g(n)\}),$$

lo que significa que $W$$\Delta_1^1$, una contradicción.

La declaración de $n\in W\iff g(n)\in U$ nos da un $\Pi_1^1$ definición de $W$, por lo que entiendo que estamos tratando de obtener un $\Sigma_1^1$ definición de $W$, para llegar a una contradicción. Lo que me confunde es cómo llegamos a la declaración, asumiendo el contrario de la afirmación del teorema, y por qué eso significa que el complemento de $W$$\Pi_1^1$. Yo también agradecería si alguien podría dar una explicación intuitiva de ser $\Pi_1^1$$\Pi_1^1$. También he sido capaz de encontrar ninguna referencia en ninguna de estas -- el más cercano es Moschovakis' Descriptivo de la Teoría de conjuntos de texto, pero incluso eso no parece contener este resultado. Cualquier ayuda es muy apreciada.

EDIT: El documento que aquí se da una prueba de la negrita resultado, pero parece ser estructurado de manera diferente(?)

Answer 1

Recordemos que $x<^\ast_\varphi y$ se define como $x\in U\land (y\notin U\lor\varphi(x)<\varphi(y))$ (véase, por ejemplo, Moschovakis' Descriptivo de la Teoría de conjuntos 4B).

Permítanme indicar con $Q_n:=\{x : f(x)<^\ast_\varphi g(n)\}$. Observe que la definición de $<^\ast_\varphi$ tenemos que $x\in Q_n$ implica $f(x)\in U$, lo que da como resultado que $x\in A$ y por lo tanto tenemos $Q_n\subseteq A$.

Si $n\notin W$ tenemos que $g(n)\notin U$ y, por tanto, por la definición de $<^\ast_\varphi$ tenemos que para cualquier $x$ tal que $f(x)\in U$ ( $x\in A$ ) es el caso de que $f(x)<^\ast_\varphi g(n)$. Por lo tanto se deduce que el $Q_n=A$ y, por lo tanto, la asunción, $\Phi(Q_n)$ es el caso.

Ahora vamos a $n\in W$. Observe que $Q_n$ $\Delta_1^1$ (esto es debido a que $Q_n$ es un subconjunto de a $A$ con rango delimitado, para una prueba de que he encontrado el Acotamiento Teorema de la 4A.4 en Moschovakis libro). Por lo tanto, por la suposición de que no existe $\Delta_1^1$ $B\subseteq A$ $\Phi(B)$ se sigue que no es el caso que $\Phi(Q_n)$.

Esto demuestra que el resaltado de la declaración.

Ahora a ver que $\mathbb{N}\setminus W$ $\Pi_1^1$ aviso que desde el $\{(n,x) : f(x)<^\ast_\varphi g(n)\}$ $\Pi_1^1$ $\Phi$ $\Pi^1_1$ tenemos que $\mathbb{N}\setminus W=\{n : \{x : f(x)<^\ast_\varphi g(n)\}\in\Phi\}$$\Pi^1_1$.

Lamentablemente yo no puedo proporcionar una gran cantidad de información y referencias de los resultados de los mismos, ya que ha sido un largo tiempo desde la última vez estudiado descriptivo de la teoría de conjuntos :(