Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Let $f : \mathbb{N}^k \to \mathbb{N}$ be a computable total function such that $f (\vec{x}) > \max \vec{x}$ for all $\vec{x}$.

Question. Why is there a decidable set $A$ such that $\operatorname{im} {\left. f \right|_{A^k}} = \mathbb{N} \setminus A$?


It feels like there should be an inductive process which gives the solution. Let $A_0 = \mathbb{N} \setminus {\operatorname{im} f}$. If there is such an $A$, then $A_0 \subseteq A$ for sure. Let for each natural number $n$, let $B_n = \mathbb{N} \setminus {\operatorname{im} f \big|_{{A_n}^k}}$ and $A_{n+1} = \mathbb{N} \setminus {\operatorname{im} f \big|_{{B_n}^k}}$. One can then show inductively that $$A_0 \subseteq A_1 \subseteq A_2 \subseteq \cdots \subseteq B_2 \subseteq B_1 \subseteq B_0$$ Let $A = \bigcup_n A_n$ and $B_\infty = \bigcap_n B_n$. If $\vec{x} \in A^k$, then $\vec{x} \in {A_n}^k$ for some $n$, so $f (\vec{x}) \notin B_n$, hence $\vec{x} \notin B$. On the other hand, if $y \notin B$, then $y \notin B_n$ for some $n$, so there is some $\vec{x} \in {A_n}^k$ such that $f (\vec{x}) = y$, and $\vec{x} \in A^k$. Thus $\operatorname{im} f \big|_{A^k} = \mathbb{N} \setminus B$. So far so good.

Under the hypothesis, it's easy to see that $f$ maps decidable subsets of $\mathbb{N}^k$ to decidable subsets of $\mathbb{N}$. Thus, $A$ is semidecidable, and $B$ is co-semidecidable. If $A = B$ then it follows that $A$ is decidable... but is it true that $A = B$?

share|improve this question

2 Answers 2

up vote 3 down vote accepted

We define $A$ as the union $\bigcup_s A_s$ of the finite approximations $A_s$. Start out at stage $0$ with $A_0=\{0\}$. Note that $f[A_0^k]=\{f(0,\ldots,0)\}$, and by assumption $f(0,\ldots,0)>0$, so $A_0$ is disjoint from $f[A_0^k]$. Suppose inductively that $A_s$ is defined and $f[A_s^k]$ is disjoint from $A_s$. Let $n_s$ be the least number not in $f[A_s^k]$ and let $A_{s+1}=A_s\cup\{n_s\}$. By induction, $n_s$ is larger than any element of $A_s$, since otherwise it would have been added at an earlier stage. From this, it follows that $f[A_{s+1}^k]$ is still disjoint from $A_{s+1}$, since any input not using $n_s$ is in $f[A_s^k]$ and hence not in $A_s\cup\{n_s\}$, and any input using $n_s$ is larger than $n_s$ and hence not in $A_{s+1}$. So we maintain the inductive hypothesis.

Let $A=\bigcup_s A_s$. It follows that $f[A^k]$ is disjoint from $A$, but every element not in $f[A^k]$ was added at the stage when it became the least such element. Thus, $f[A^k]=\mathbb{N}-A$, as desired.

share|improve this answer
1  
Note that $A$ is decidable, since to tell if $n\in A$ or not, just start the process and see if $n$ makes it into $A$, or if the process skips over $n$ at some stage. –  JDH May 9 '12 at 1:30

We prove by induction on $i$ that $A \cap [i] = B \cap [i]$, where $[i] = \{0,\ldots,i\}$. Since $0 \notin \operatorname{im} f$, we have $0 \in A \cap B$, proving the base case.

Assume that $A \cap [i-1] = B \cap [i-1] = C$. If $i \in f(C^k)$ then $i \notin B$. Otherwise, $i \in A$. In both cases, $A \subseteq B$ implies $A \cap \{i\} = B \cap \{i\}$.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.