Clasificación de los conjuntos en jerarquía aritmética

Question

Me dan los conjuntos $A$ tal que $|A|<\infty, A\neq\emptyset$ y $B$ tal que $|B|=\infty$ . Entonces se supone que debo encontrar dónde van los siguientes conjuntos en la jerarquía aritmética:

$S=\{e\colon \text{dom}(\Phi_e)=A\}$

$T=\{e\colon \text{dom}(\Phi_e)=B\}$

pero estoy un poco confundido sobre cómo decidir esto? Está claro que no están en $\Sigma_1,\Pi_1$ pero no sé a dónde ir a partir de ahí y por qué sus clasificaciones pueden ser diferentes, ya que por lo que puedo ver cualquier declaración lógica para un conjunto también funcionaría para el otro? Gracias.

Nota: $\Phi_e$ denota el $e$ -ésima función parcial computable.

Answer 1

Dejemos que $\psi$ sea una función recursiva primitiva tal que $\psi(e,n,t)=1$ si $\Phi_e(n)$ se detiene en $t$ pasos o menos en caso contrario $\psi(e,n,t)=0$ .

Entonces $S=\{n\;|\;\exists t\forall x \forall u(u\ge t \wedge x\in A\Leftrightarrow\psi(n,x,u)=1)\}$ Así que $S\in\Sigma_2$ .

Pero también $S=\{n\;|\;\forall x \forall u\exists t(u\ge t \wedge x\in A\Leftrightarrow\psi(n,x,u)=1)\}$ Así que $S\in\Pi_2$ .

Así que $S\in\Delta_2$ . Tenga en cuenta que $S\notin\Sigma_1\cup\Pi_1$

Tenga en cuenta que $x\in A$ es una relación primitiva recursiva como $A$ es finito.

Si $B$ no es recursivamente enumerable, entonces $T$ está vacío, por lo que $T\in\Delta_0$ .

Si $B$ es recursivamente enumerable, dejemos que $b$ tal que $B=dom(\Phi_b)$ .

Entonces $T=\{n\;|\;\forall x\forall u\exists t \quad u>t\Rightarrow (\psi(b,x,u)=1\Leftrightarrow\psi(n,x,u)=1)\}$ . Así que $T\in\Pi_2$ .

La principal diferencia es que como $A$ es finito, hay tiempo $t$ tal que si una función $f$ de dominio $A$ se calcula, ya sea $f$ se detiene antes de tiempo $t$ o nunca se detiene (se puede ver $t$ como el tiempo máximo necesario para converger). Pero $B$ es infinito, por lo que no puede haber un tiempo máximo sobre todas las entradas, por lo que $T\notin \Sigma_2$