Disjoint sets of fixed points 2

Question

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$?

Answer 1

No.

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.

Answer 2

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.