Podemos encontrar una fórmula de la definición de un recursivamente enumerable?

Question

Por el Post del Teorema sabemos que un conjunto $A\subseteq\mathbf{N}$ es recursivamente enumerable iff es definible por una $\Sigma_1$-fórmula, es decir, existe una $\Sigma_1$-fórmula $\varphi(x)$ $x$ libre tal que para cada número $n$: \[ n\in a\longleftrightarrow \mathfrak{N}\vDash\varphi(\overline{n}) \] donde $\mathfrak{N}$ es el modelo estándar de la de primer orden lenguaje de la Aritmética de Peano.

Tengo la siguiente pregunta: dado un r.e. set $A$ podemos encontrar siempre un $\Sigma_1$-fórmula de la definición?

Answer 1

La definición de un recurrente conjunto enumerable, es que es el dominio de algunos parciales de la función recursiva.

No es recursiva primitiva de la función $\psi$, de tal manera que $\psi(n,t,x)=0$ si y sólo si $\phi_n(x)$ (la función recursiva $n$ en la entrada $x$) se detiene en menos de $t$ pasos, de lo contrario $\psi(n,t,x)=1$. Cualquier recursiva primitiva de la función puede ser definida por un $\Delta_0$-fórmula. Por lo tanto

$$\phi_n(x)\mbox{ halts } \Leftrightarrow \exists t\; \psi(n,t,x)=0$$

La existencia de $\psi$ es una consecuencia de Kleene T-predicado

Answer 2

Por el axioma de elección, existe una función que se asigna a cada r.e. establece en uno de sus definiciones. Podemos 'encontrar' la definición en ese sentido. Esta función no puede ser demasiado agradable, sin embargo, debido a que decidiría la extensional equivalencia de las dos definiciones.

Deje $f$ ser una función que asigna a cada conjunto a uno de sus definiciones. Para cada instrucción aritmética $p$ hay un conjunto $\{n|p\}$. La igualdad de las definiciones de $f(\{n|p\}) = f(\mathbb N)$ es la forma de decidir si $p$ es cierto. G\"odel los teoremas de incompletitud de decir que no puede hacer eso.