$f \in \Sigma_n^1 \iff f \in \Pi_n^1$ en una jerarquía analítica

Question

La proposición 1.7 en Higher Recursion Theory de Sacks dice $f \in \Sigma_n^1 \iff f \in \Pi_n^1$ con la prueba:

Desde $f$ es una función, entonces,

$f(x)=y \iff \forall z. [y \neq z \implies f(x) \neq z]$ .

Si el lado izquierdo de la afirmación anterior es $\Sigma^1_n$ ( $\Pi^1_n$ respectivamente), entonces el lado derecho es $\Pi^1_n$ ( $\Sigma^1_n$ respectivamente). QED.

Lo que no entiendo es que si $f(x)=y$ es $\Sigma^1_n$ Entonces, ¿por qué el lado derecho debería ser $\Pi^1_n$ ? Creo que tiene que ser al menos $\Pi^1_{n+1}$ ya que existe un cuantificador universal en $z$ y $[y \neq z \implies f(x) \neq z]$ es al menos $\Sigma^1_n$ como $f(x)=y$ es $\Sigma^1_n$ .

Answer 1

Hay dos cosas que te faltan. En primer lugar, el $\forall z$ es un cuantificador de primer orden, no de segundo orden, por lo que queda subsumido por cualquier cuantificador de orden superior que haya por ahí. En segundo lugar, como $f(x) = y$ es $\Sigma_n^1$ su negación es $\Pi_n^1$ . Básicamente, usted tiene $$ \forall z(\text{arithmetic statement} \rightarrow \neg \Sigma_n^1) $$ Que es lo mismo que $$ \forall z(\text{arithmetic statement} \rightarrow \Pi_n^1) $$ Que es $\Pi_n^1$ .