Un conjunto homogéneo de algún tipo

Question

Deje $f : \mathbb{N}^k \to \mathbb{N}$ ser una computable total de la función tal que $f (\vec{x}) > \max \vec{x}$ todos los $\vec{x}$.

Pregunta. ¿Por qué hay un decidable set $A$ tal que $\operatorname{im} {\left. f \right|_{A^k}} = \mathbb{N} \setminus A$?

---

Se siente como debería ser un proceso inductivo que da la solución. Deje $A_0 = \mathbb{N} \setminus {\operatorname{im} f}$. Si hay un $A$, $A_0 \subseteq A$ seguro. Deje que para cada número natural $n$, vamos a $B_n = \mathbb{N} \setminus {\operatorname{im} f \big|_{{A_n}^k}}$$A_{n+1} = \mathbb{N} \setminus {\operatorname{im} f \big|_{{B_n}^k}}$. Entonces, uno puede mostrar de forma inductiva que $$A_0 \subseteq A_1 \subseteq A_2 \subseteq \cdots \subseteq B_2 \subseteq B_1 \subseteq B_0$$ Deje $A = \bigcup_n A_n$$B_\infty = \bigcap_n B_n$. Si $\vec{x} \in A^k$, $\vec{x} \in {A_n}^k$ algunos $n$, lo $f (\vec{x}) \notin B_n$, por lo tanto $\vec{x} \notin B$. Por otro lado, si $y \notin B$, $y \notin B_n$ algunos $n$, por lo que hay algunos $\vec{x} \in {A_n}^k$ tal que $f (\vec{x}) = y$, e $\vec{x} \in A^k$. Por lo tanto $\operatorname{im} f \big|_{A^k} = \mathbb{N} \setminus B$. Hasta ahora tan bueno.

Bajo la hipótesis, es fácil ver que $f$ mapas decidable subconjuntos de a $\mathbb{N}^k$ a decidable subconjuntos de a $\mathbb{N}$. Por lo tanto, $A$ es semidecidable, y $B$ es co-semidecidable. Si $A = B$, entonces se sigue que $A$ es decidable... pero es cierto que $A = B$?

Answer 1

Definimos $A$ como la unión de $\bigcup_s A_s$ de lo finito aproximaciones $A_s$. Comenzar en la etapa de $0$$A_0=\{0\}$. Tenga en cuenta que $f[A_0^k]=\{f(0,\ldots,0)\}$, y por supuesto de $f(0,\ldots,0)>0$, lo $A_0$ es disjunta de a $f[A_0^k]$. Supongamos inductivamente que $A_s$ está definido y $f[A_s^k]$ es disjunta de a $A_s$. Deje $n_s$ ser el que menos no en $f[A_s^k]$ y deje $A_{s+1}=A_s\cup\{n_s\}$. Por inducción, $n_s$ es más grande que cualquier elemento de a $A_s$, ya que de lo contrario habría sido añadido en una etapa anterior. De esto se sigue que el $f[A_{s+1}^k]$ es todavía disjunta de a $A_{s+1}$, ya que de entrada no uso de $n_s$ $f[A_s^k]$ y, por tanto, no se en $A_s\cup\{n_s\}$, y ninguna entrada con $n_s$ es mayor que $n_s$ y, por tanto, no se en $A_{s+1}$. Por lo tanto, mantenemos la hipótesis inductiva.

Deje $A=\bigcup_s A_s$. De ello se desprende que $f[A^k]$ es disjunta de a $A$, pero cada elemento no en $f[A^k]$ fue añadido en la etapa en que se convirtió en el menos tal elemento. Por lo tanto, $f[A^k]=\mathbb{N}-A$, como se desee.

Answer 2

Podemos demostrar por inducción sobre $i$ que $A \cap [i] = B \cap [i]$ donde $[i] = \{0,\ldots,i\}$. Desde $0 \notin \operatorname{im} f$,$0 \in A \cap B$, lo que demuestra el caso base.

Suponga que $A \cap [i-1] = B \cap [i-1] = C$. Si $i \in f(C^k)$$i \notin B$. De lo contrario, $i \in A$. En ambos casos, $A \subseteq B$ implica $A \cap \{i\} = B \cap \{i\}$.