The property of being an index set is not computably invariant

Question

Let $\omega$ denote the set of natural numbers including $0$.

Definition 1. Let $A\subseteq \omega$. Then we call $A$ to be an index set if the following holds, $$\forall x\forall y((x\in A\land \varphi_x\equiv \varphi_y)\implies y\in A)$$where $\varphi_x,\varphi_y$ denotes the $x$-th and $y$-th partial computable functions (with respect to some suitable numbering).

Definition 2. A computable bijection $f: \omega\to\omega$ is said to be a computable permutation.

Definition 3. A property $P$ of subsets of $\omega$ is said to be computably invariant if for any $A\subseteq \omega$ whenever $f$ is a computable permutation and $A$ satisfies the property $P$, $f(A)$ must also satisfy the property $P$.

Problem. Prove that the property of being an index set is not computably invariant.

I am not looking for a complete solution, but just some hint to get me started. Can anyone help?

Answer 1

Amongst the computable permutations are all transpositions: permutations which just swap some pair of elements. Often an easy way to show that some property isn't computably invariant (or invariant with respect to some other collection of permutations) is to show that it can be "killed" by a transposition. Note that transpositions are trivially computable.

So suppose $X$ is an index set; we want to try to show that there is some transposition $\pi$ such that $\pi[X]$ is not an index set. This won't always be possible; along the way we'll think up some more restrictions on $X$.

Clearly in order to be relevant a transposition has to swap something in $X$ with something not in $X$ (otherwise it just leaves $X$ as a whole unchanged). This indicates that we'll also want nontriviality, that is, we also want to assume $X\not=\emptyset$ and $X\not=\omega$. That's fine - there are indeed nontrivial index sets (and it's unsurprising that we need nontriviality here).

So let $X$ be a nontrivial index set, pick $a\in X,b\not\in X$, and let $\pi$ be the transposition swapping $a$ and $b$ and leaving everything else unmoved. Is $\pi[X]$ still an index set?

Hint $1$:

Use the padding lemma.

Hint $2$:

By the padding lemma there is some $c\in\omega$ with $a\not=c$ but $\varphi_a\equiv\varphi_c$.

Answer:

... But then $a\not\in \pi[X]$ but $c\in\pi[X]$, so $\pi[X]$ isn't an index set.

Postscript:

You might reasonably wonder whether appeal to the padding lemma was necessary - is there some "coarser" way to prove this, say using just the unsolvability of the halting problem? It turns out that the answer is no: something nontrivial about the standard enumeration of partial computable functions will be needed here, since if we work over a Friedberg numbering every set is an index set. For the same reason, an appeal to the padding lemma is necessary for the proof of Rice's theorem.