Are these sets of indices also index sets?

Question

An index set is a set of all indices of some family of computably enumerable sets. It is known that the empty set is an index set and that $K = \{e \mid e \in W_e\}$ is not an index set.

The following was an exam question I didn't manage to answer:

Which of the following sets are index sets?

1) $\emptyset $

2) $K= \{ x \mid x \in W_x \}$

3) $E‌ = \{2,4,6,8, \dots \}$

4)‌ $\{ x \mid \phi_x = \phi_{x^2‌}\}$

I think:

It is known $K$ (i.e., the halting set)‌ is not an index set so (2) is ruled out. I read on this on last page problem 4 that the set of even numbers is an index set, so I'm not sure that (1) and (3) is true! But the answer sheet wrote just (1) is true. I don't know what is the definition of $E$ in (3) and not sure about (4).

Can anyone clarify me in order to better understand this challenging question? Why are (3) and (4) not index sets? I'm not familiar with notation (4), any description?

Answer 1

We start with a bit of notation:

1. $\phi_x$ is the partial function computed by program $x$.
2. $W_x = \operatorname{dom} \phi_x$, that is, the set of inputs on which program $x$ halts.
3. An index set is a set of programs $I$ such that if $\phi_x = \phi_y$ then $x \in I \Leftrightarrow y \in I$. (That is, $I$ is a union of equivalence classes of the equivalence relation $x \equiv y \Leftrightarrow \phi_x = \phi_y$.)

Rice's theorem immediately shows that if $I$ is a non-trivial index sets (that is, $x \in I$ and $y \notin I$ for some $x,y$) then $I$ is not computable.

We can now go over the four sets in the question:

1. $\emptyset$ is trivially an index set.

2. $K = \{ e : e \in W_e \}$ is not an index set. Indeed, the recursion theorem shows that some $e$ satisfies $W_e = \{e\}$. There are infinitely many programs which halt only on input $e$ and output $\phi_e(e)$. Pick one of them, $e' \neq e$. Then $e \in K$ and $e' \notin K$ even though $\phi_e = \phi_{e'}$. (This proof is taken from S. Barry Cooper, Computability Theory, mention by Pål GD in the comments.)

3. $E = \{2,4,6,8,\ldots\}$ is computable and so not an index set by Rice's theorem.

4. $\{ x : \phi_x = \phi_{x^2} \}$ is (probably) not an index set. Indeed, for it to be an index set it must hold that whenever $\phi_x = \phi_{x^2} = \phi_y$ then also $\phi_y = \phi_{y^2}$, which sounds unlikely. (The recursion theorem gives us infinitely many $x$ such that $\phi_x = \phi_{x^2}$, and for each such $x$, there are infinitely many $y$ such that $\phi_x = \phi_y$. It would be a major coincidence if for all $x,y$ we would have $\phi_y = \phi_{y^2}$.)

In part 4 there is an argument but not a proof, and this is not a coincidence. Whether $I = \{ x : \phi_x = \phi_{x^2} \}$ is an index set or not depends on the definition of $\phi$, that is on the universal Turing machine. Every choice corresponds to an admissible numbering, and there are some admissible numberings for which $I$ is an index set (see here), and there are others for which $I$ is not an index set (see here). So the answer for part 4 is really "we don't know" or "it depends". Nevertheless, for any natural admissible numbering, you will find out that $I$ is not an index set; unless you engineer $I$ to be an index set, it won't be an index set.

For convenience, I will repeat the constructions showing that $I$ can be an index set and can be not an index set:

1. $I$ can be an index set: Fix some admissible numbering $\phi_x$. Let $p_i$ be the $i$th prime. Define a new admissible numbering $\psi_x$ by $\psi_{p_i^k} = \phi_i$ for all $k \geq 1$, and $\psi_x = 0$ whenever $x$ is not a prime power. Thew new admissible numbering satisfies $\psi_x = \psi_{x^2}$ for all $x$ and so $I = \mathbb{N}$ is trivially an index set.

2. $I$ can be not an index set: Fix some admissible numbering $\phi_x$. Define a new admissible numbering $\psi_x$ by $$ \psi_x = \begin{cases} 0 & x = 0,1,2,3 \\ 1 & x = 4 \\ \phi_{x-5} & x \geq 5 \end{cases} $$ In this case $\psi_1 = \psi_{1^2} = \psi_2$ but $\psi_2 \neq \psi_{2^2}$, showing that $I$ is not an index set.

I conjecture that under some reasonable interpretation, the fraction of admissible numberings for which $I$ is an index set tends to zero.

Answer 2

Let's review what an index set is.

Given a Gödel numbering $\phi$ and a set $P \subseteq \mathcal{P}$ of (partially) recursive functions, we call

$\qquad\displaystyle I_P := \{ i \mid \phi_i \in P \}$

the index set of $\mathcal{P}$.

Assuming that we have a Gödel numbering is central; otherwise we can't do much with this notion, for instance Rice's theorem¹ assumes one². In particular, three of the four proofs below need that $\phi$ is a Gödel numbering.

Working from this definition, we can approach the four candidates.

1. Clearly, $\emptyset = I_{\emptyset}$.

2. I assume that you mean the standard (special) Halting set, i.e.

   $\qquad\displaystyle K = \{ i \mid \phi_i(i)\!\uparrow \}$.

   I will now show that there is some $i^{\star} \in K$ for which all other indices of $\phi_{i^{\star}}$ are not in $K$. Note that this is not trivial; $K$ certainly does contain all indices of the empty function (the one that loops everywhere), and none of any total function.

   Let

   $\qquad\displaystyle f(i,x) = \begin{cases} 1, &i \neq x;\\ \uparrow, &i = x.\end{cases}$

   Clearly, $f \in \mathcal{P}$. By smn theorem, there is totally recursive $g$ so that $\phi_{g(i)}(x) = f(i,x)$ for all $i$ and $x$. Now, by fixed-point theorem there is $i^{\star}$ with $\phi_{g(i^{\star})} = \phi_{i^{\star}}$; that is,

   $\qquad\displaystyle \phi_{i^{\star}}(x) = \begin{cases} 1, &i^{\star} \neq x;\\ \uparrow, &i^{\star} = x.\end{cases}$

   Clearly, $i^{\star} \in K$. Now, since $\phi$ is a Gödel numbering there are infininitely many indices for $\phi_{i^{\star}}$; $\phi_{j}(j) = \phi_{i^{\star}}(j) = 1$, so $j \notin K$. Hence, $K$ let $j \neq i^{\star}$ be any one of them. By definition (of $f$), is not an index set.

3. It is another straight-forward application of smn- and fixpoint theorem to show that for each Gödel numbering, there are functions that have (among others) two indices $i$ and $i+1$. It follows directly that $E = 2\mathbb{N}$ is not an index set.

   Use $f(i,x) = \lfloor \tfrac{i}{2} \rfloor$. We obtain that $\phi_{i^*} = \lfloor \tfrac{i^*}{2} \rfloor$ for some $i^*$. Clearly, $\phi_{i^*+1} = \phi_{i^*}$ if $\phi_{i^*} \in 2\mathbb{N}$, and $\phi_{i^*-1} = \phi_{i^*}$ if $\phi_{i^*} \in 2\mathbb{N}+1$.

4. Yes, and no. There are Gödel numberings for which $M_{\varphi} = \{ x \mid \varphi_x = \varphi_{x^2} \}$ is an index set, and there are such for which it is not.

   Let $\phi$ be an arbitrary Gödel numbering. We will construct new Gödel numberings for each case.

   • With $p_i$ the $i$th prime number, define

     $\qquad\displaystyle h(x) = \begin{cases} i, &\exists i,k \in \mathbb{N}.\ a=p_i^k;\\ 1, &\text{else}. \end{cases}$

     Now $\psi$ defined by $\psi_j = \phi_{h(j)}$ is a Gödel numbering (check the definition; in particular, $h$ is totally recursive). Furthermore, $M_\psi = \mathbb{N}$ which is clearly an index set (of $\mathcal{P}$); check the two cases $x = p_i^k$ for some $i$ and $k \geq 1$ (then $x^2 = p_i^{2k}$, i.e. $\psi_x = \phi_i = \psi_{x^2}$), and $x \neq p_i^k$ for all $i,k$ (then $x^2$ is not a power of a single prime either and $\psi_x = \phi_1 = \psi_{x^2}$).

   • Define $\nu$ by

     $\qquad\displaystyle \nu_x = \begin{cases} \phi_1, &x \leq 2; \\ \phi_2, &3 \leq x \leq 4; \\ \phi_{x-4}, &x \geq 5. \end{cases}$

     Check again the definition to see that $\nu$ is a Gödel numbering. Now, by definition $\nu_1 = \nu_2$ but $1 \in M_\nu$ while $2 \notin M_\nu$, hence $M_\nu$ is not an index set.

---

1. If you don't like the Wikipedia article, this may help.
2. There seems to be the notion of admissible numberings but I'm not familiar with that one.