MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Let $\phi$ be an acceptable programming system. For every recursive function $f$, let $(f)=\{x:\phi_x=\phi_{f(x)}\}$ the set of fixed points of $f$. Now, let $S$ be a set and suppose that there exist recursive functions $f$ and $g$ such that $(f)\subseteq S$ and $(g)\subseteq N\setminus S$. The question is: are there recursive functions $F$ and $G$ such that $(F)\subseteq S$, $(G)\subseteq N\setminus S$ and $\phi_{F(x)}\neq\phi_{G(x)}$, for all $x$?

share|cite|improve this question
For those not in the know, this is a follow-up to . – Emil Jeřábek Mar 13 '13 at 13:17


We'll build $f$ and $g$. We'll diagonalize against a pair $(F, G)$ using an index $x$ for a function we will construct, and we'll also construct $\phi_{f(x)}$ and $\phi_{g(x)}$ (using several instances of the Recursion Theorem). For $x$ which are not indices used for diagonalization, we define $\phi_{f(x)}$ the constant 0 function and $\phi_{g(x)}$ the constant 1 function.

Initially we keep $\phi_x$ empty, while defining $\phi_{f(x)}(0) = \phi_{g(x)}(0) = 0$ (and making no other definitions). We wait until $F(x)$ and $G(x)$ converge, and then begin studying $\phi_{F(x)}$ and $\phi_{G(x)}$. If $\phi_{F(x)}$ contains any definitions other than $\phi_{F(x)}(0) = 0$, then we can define $\phi_x = \phi_{F(x)}$ and declare $x \not \in S$. Similarly for $\phi_{G(x)}$.

Assuming this doesn't happen, if we never see the definition $\phi_{F(x)}(0) = 0$, then we can simply declare $x \not \in S$. Similarly if we never see $\phi_{G(x)}(0) = 0$. So eventually $\phi_{F(x)} = \phi_{G(x)}$, and we've defeated this pair.

share|cite|improve this answer

I don't quite follow Dan's answer, so I'll post my own solution to this question. Possibly this works out to be the same but with more details filled in. I'll show that given any answer to the previous question one can construct an $S$ for which the answer to the current question is no.

Suppose we have been given $f$ and $g$ such that $(f) \cap (g) = \emptyset$ but such that for any $F$ and $G$ with $(F) \subseteq(f)$ and $(G) \subseteq (g)$ there is $x \in \mathbb{N}$ such that $\phi_{F(x)} = \phi_{G(x)}$. For example we can take the $f$ and $g$ from my previous answer. We first show that we can strengthen this result slightly.

Lemma Suppose that $(F) \setminus (f)$ and $(G) \setminus (g)$ are both finite. Then there is some $x \in \mathbb{N}$ such that $\phi_{F(x)} = \phi_{G(x)}$.

Proof Define $F'$ so that for $n \in (F) \setminus (f)$, $\phi_{F'(n)} \neq \phi_n$ and $\phi_{F'(n)} \neq \phi_{G(n)}$, and for $n \in \mathbb{N} \setminus ((F) \setminus (f))$, $F'(n) = F(n)$. Similarly define $G'$ so that for $n \in (G) \setminus (g)$, $\phi_{G'(n)} \neq \phi_n$ and $\phi_{G'(n)} \neq \phi_{F'(n)}$. Then $(F') \subseteq (f)$ and $(G') \subseteq (g)$, so we can take $x$ such that $\phi_{F'(x)} = \phi_{G'(x)}$. Then for this same $x$ we have that $\phi_{F(x)} = \phi_{G(x)}$, as required.

We now construct in stages $S_0 \subseteq S_1 \subseteq \ldots$ and $T_0 \subseteq T1 \subseteq \ldots$ such that for all $i$, $S_i \cap T_i = \emptyset$, and $S_i \setminus S_0$ and $T_i \setminus T_0$ are both finite.

Set $S_0 = (f)$ and $T_0 = (g)$.

Now assume that we have defined $S_i$ and $T_i$ for $i \leq n$. We define $S_{n + 1}$ and $T_{n + 1}$ as follows. Decode $n$ as a pair of numbers $n = (n_1, n_2)$. We will ensure that for $F = \phi_{n_1}$ and $G = \phi_{n_2}$, if for every $x \in \mathbb{N}$ $\phi_F(x) \neq \phi_G(x)$, then either $(F) \cap T_n \neq \emptyset$, or $(G) \cap S_n \neq \emptyset$.

If $F := \phi_{n_1}$ or $G := \phi_{n_2}$ is partial or if there is some $x$ such that $\phi_{F(x)} = \phi_{G(x)}$, then take $S_{n + 1} = S_n$ and $T_{n + 1} = T_n$. Otherwise, by the lemma we know that one of $(F) \setminus (f)$ and $(G) \setminus (g)$ must be infinite. Suppose that $(F) \setminus (f)$ is infinite. Then since $S_n \setminus (f)$ is finite, there must be some $k$ such that $k$ is in $(F) \setminus (f)$ but not in $S_n \setminus (f)$. Therefore if we take $T_{n + 1} = T_n \cup \{k\}$, we have ensured that $T_{n + 1} \cap S_n = \emptyset$ but that $T_{n + 1} \cap (F) \neq \emptyset$. Define $T_{n + 1}$ as such and let $S_{n + 1} = S_n$. Similarly, if $(G) \setminus (g)$ is infinite, then we extend $S_n$.

Finally take $S := \bigcup_n S_n$. Then we clearly have $(f) \subseteq S$ and $(g) \subseteq \mathbb{N} \setminus S$ but such that whenever $\phi_{F(x)} \neq \phi_{G(x)}$ for every $x$, either $(F) \cap (\mathbb{N} \setminus S) \neq \emptyset$ (and so $(F) \nsubseteq S$), or $(G) \cap S \neq \emptyset$, as required.

share|cite|improve this answer

Your Answer


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.