¿Existe una función no recursiva (digamos, de naturales a naturales) tal que el inverso de cada conjunto de e.r. sea e.r.?
Si es así, ¿cómo se construye uno? Si no, ¿cómo probarlo? ¿Alguna referencia?
Respuestas
¿Demasiados anuncios?
Para cualquier secuencia $ \mathcal {B} = \langle B_i : i \in \mathbb {N} \rangle $ de subconjuntos de $ \mathbb {N}$ hay un $ \mathcal {B}$ -Juego de cohesivos $A$ un conjunto infinito tal que, para cualquier $B_i \in \mathcal {B}$ o bien hay sólo finamente muchos elementos de $A$ en $B_i$ o todos los elementos de $A$ están en $B_i$ . El conjunto $A$ se llama "cohesivo" porque, aunque es infinito, ninguno de los conjuntos $B_i$ es capaz de dividirlo en dos piezas infinitas.
Aplique ese hecho con $ \mathcal {B}$ que contiene todos los conjuntos de E.R. para obtener un conjunto cohesivo $A$ . Deje que $f$ ser la función que enumera $A$ en orden creciente. Primero, $A$ no es computable, ni siquiera r.e., porque si $A$ fue r.e. entonces podríamos usar esa enumeración para enumerar efectivamente "todos los demás elementos" de $A$ lo que nos daría un conjunto de R.E. que se divide $A$ en dos piezas infinitas, lo cual es imposible. Además, porque $A$ no es computable, $f$ no es computable - si pudiéramos computar $f$ entonces podríamos enumerar $A$ en orden creciente, lo que implicaría $A$ es computable.
Ahora deja que $B$ ser cualquier conjunto de R.E. Entonces, porque $A$ es cohesiva para los conjuntos de E.R., una de dos cosas debe suceder:
- Todos los elementos de $A$ están en $B$ . En este caso $f^{-1}(B)$ es cofinita, y por lo tanto es computable.
- Sólo finamente muchos elementos de $A$ están en $B$ . En este caso, $f^{-1}(B)$ es un conjunto finito, y por lo tanto es computable.
De cualquier manera $f^{-1}(B)$ no es sólo R.E., es computable.
Peter Gerdes
Puntos
99
Sólo para aclarar, asumí que la pregunta se refería a las funciones bijectivas (ya que son más interesantes), por lo que demostré que la respuesta también era afirmativa en ese caso.
Si quieres cualquier función antigua, puedes usar el forzado al estilo Galvin-Prikry. Definir un segmento inicial finito de la función y mantener un conjunto infinito $S$ de los posibles valores futuros de los elementos en el rango. En la etapa $i$ se resta $W_i$ de $S$ a menos que eso lo deje finito, en cuyo caso te encoges $S$ para ser un subconjunto de $W_i$ . En realidad es la misma técnica pero me gusta más.
En cuanto al caso bijectivo la respuesta sigue siendo sí.
Deje que $ \mathscr {E}$ denotan la estructura con dominio consistente en conjuntos c.e. (alias r.e.) bajo la relación $ \subseteq $ . Un automorfismo de $ \mathscr {E}$ es sólo una función bijectiva en los conjuntos c.e. que respetan $ \subseteq $ .
Es un resultado de (?) (Tal vez Soare como aparece en su libro de texto) que cualquier automorfismo de $ \mathscr {E}$ es inducido por una permutación de $ \omega $ (es decir, la bijección de $ \omega $ con sí mismo).
Hay varias formas diferentes de ver que no todos los automorfismos de $ \mathscr {E}$ son inducidos por una permutación computable. El argumento de Lachlan es mi favorito porque funciona incluso en $ \mathscr {E}$ modulo de diferencias finitas.
Dado que todas las permutaciones computables dan lugar a automorfismos, se puede fijar un conjunto cohesivo co-c.e. $C$ por ejemplo, el elogio de un conjunto máximo, y tenga en cuenta que cualquier permutación $p_C$ de $C$ unión de la identidad en $C$ El cumplido induce un mapa inyectable $p(W)= (W \cap \bar {C}) \cup p_C(W \cap C)$ . Desde $C$ es cohesivo, ya sea $W \cap C$ es finito, así que $p(W)$ es una unión de conjunto c.e. un conjunto finito y por lo tanto c.e. o $W$ casi cubre $C$ así que $C - W$ es finito. Por lo tanto, $p_C(W \cap C)$ sólo difiere finamente de $C$ y por lo tanto sólo difiere finamente de $W \cap C$ . Por lo tanto $p(W)$ difiere sólo finamente de $W$ así que $p(W)$ es c.e. Por lo tanto $p$ es un automorfismo de los conjuntos c.e. (ya que es claramente una función surjectiva en todos los conjuntos).
La prueba de Lachlan se basa en definir permutaciones computables en subconjuntos computables mayores y más grandes de $ \omega $ . Empezamos con $R_0= \emptyset $ y construir una secuencia $R_0 \subseteq R_1 \ldots $ de conjuntos computables tales que $ \omega - R_i$ nunca es finito pero $ \bigcup R_i = \omega $ . En cada uno $R_{i+1} - R_i$ definimos una permutación y dejamos que la permutación final sea la unión de estas permutaciones parciales. La idea clave es similar a la que hemos utilizado anteriormente: si $W \cap C$ es finito o $C - W$ es finito entonces sin embargo definimos nuestra permutación en $C$ no puede interferir con la cartografía $W$ a otro conjunto de C.E.
En el escenario $i+1$ elegir algunos computables $R_{i+1}$ no es casi igual a $ \omega $ que se extiende infinitamente $R_{i}$ que contiene $W_i$ o $ \bar {W_i}$ . Entonces seleccione el primer conjunto de c.e. $W$ aún no se ha tratado de tal manera que $W \cap (R_{i+1}-R_i)$ es infinito y $(R_{i+1}-R_i) - W$ es infinito. Dejemos que $C$ ser un infinito subconjunto computable de $W \cap (R_{i+1}-R_i)$ . Deje que $p_0$ ser la identidad en $(R_{i+1}-R_i)$ . Deje que $p_1$ ser la permutación en $(R_{i+1}-R_i)$ intercambiando $C$ y $ \bar {C} \cap (R_{i+1}-R_i)$ .
Claramente ambos $p_0$ y $p_1$ y computable y como $ \bar {C} \cap (R_{i+1}-R_i)$ contiene infinitamente muchos elementos fuera de $W$ se deduce que $p_1(W)$ no es casi igual a $W$ . Desde $R_{i+1}$ o bien contiene $W_i$ o $ \bar {W_i}$ cada conjunto de C.E. tiene su imagen determinada por una permutación computable que da lugar a un automorfismo. Sin embargo, cualquier cadena infinita de $0$ y $1$ da lugar a un automorfismo único.
Es importante, ya que $p_0$ y $p_1$ siempre mapea conjuntos c.e. a conjuntos que difieren infinitamente mucho esto muestra el resultado más fuerte que tenemos $2^ \omega $ muchos automorfismos que difieren no trivialmente.
alasdairg
Puntos
1518
Supongo que te refieres a la imagen en vez de a la inversa...
En ese caso, en mi opinión, la respuesta es que esa función existe. Ya que se puede construir una función $ \phi $ como sigue: para los números que representan pares válidos (código de una máquina de Turing, entrada) devuelva 1, si la máquina se detiene en la entrada, 0 en caso contrario. Para todos los demás números, devuelva 0. Es evidente que esta función no es recursiva. Sin embargo, para todos los conjuntos r.e., la imagen es $\{0\}$ o $\{0,1\}$ que son ambas R.E.
