I am trying to show a basic property of index sets and also trying to find a counterexample of an index set. I'll write the statements of the problem.
Definition $I \subset \mathbb N$ is called an index set if there exists a class of partially computable functions $\mathcal C$ such that $I=\{x: \phi_x \in \mathcal C\}$.
a) Let $C_1,...,C_k$ be all index sets and let $C=C_1 \cap...\cap C_k$. Prove that $C$ is an index set.
b) Show an example of a set that is not an index set and is not computable (a set $A$ is computable if its characteristic function is a total computable function)
I think I did a) correctly and I am not sure if the set I could think for b) is ok.
I'll prove by induction that index sets are closed by finite intersection.
Let $n=2$ and $C=C_1 \cap C_2$ with $C_i$ an index set for $i=1,2$. Let $P_i$ be the class of partially computable functions such that $C_i$ is the index set corresponding to $P_i$.
Consider $P=P_1 \cap P_2$ and let $C'$ be the index set associated with $P$. If $f$ is in $P$, then $f=\phi_x$ ($x \in C'$) is a partially computable function, since $f$ is in both $P_1$ and $P_2$, then $x \in C_1 \cap C_2=C$. If $x$ is in $C$, then $x \in C_1 \cap C_2$, so there is a partially computable function $f$ in both $P_1$ and $P2$, so $f \in P$ and $x \in C'$.
It follows that $C$ is the index set corresponding to $P$.
Now suppose that the hypothesis is true for $n$, if $C_1,...,C_{n+1}$ are index sets, then we want to show that $C=C_1 \cap ... \cap C_{n+1}$ is an index set. By the inductive step we have that $C'=C_1 \cap ... \cap C_n$ is an index set, since $C=C' \cap C_{n+1}$ is an intersection of two index sets then $C$ is an index set.
Now, for b), the set $H=\{x : \phi_x(x) \downarrow \}$ is not computable, since $f(x)=HALT(x,x)$ is not a computable function. Now, I am not sure if it is not an index set.
I would really appreciate if someone could help me with part b) and tell me if there is anything wrong in part a). Thanks!
Your proof for (a) is right, but could be made a bit cleaner. Personally, the way I like to approach index sets is via the following:
Define an equivalence relation $\approx$ on $\mathbb{N}$: $c\approx d$ if $\varphi_c=\varphi_d$, that is, if $c$ and $d$ are indices for the same partial computable function.
We now forget about computability theory and just think about equivalence classes. An index set is just a set $X\subseteq\mathbb{N}$ which is $\approx$-invariant: if $c\in X$ and $c\approx d$, then $d\in X$. Equivalently, an index set is a union of $\approx$-equivalence classes (do you see why this is equivalent?).
This means that we can think of index sets in the same way that we think of unions of equivalence classes in arbitrary contexts. E.g. it might be intuitively easier to prove the more general (but not weighed down by computability theory) fact that if $C_1, ..., C_n$ are each unions of $E$-classes (for $E$ some equivalence relation on a set $A$), then so is $C_1\cap...\cap C_n$. And in fact this works for arbitrary intersections, and arbitrary unions, as well.
Meanwhile, your intuition for (b) is right, although there are easier examples. Let me first give an easier example, and then sketch why $H$ isn't an index set.
The easiest way in my opinion to build a non-index set is the following:
Pick some $n\in\mathbb{N}$.
By the Padding Lemma, we get a computable sequence $n_0<n_1<n_2<...$ of distinct indices for $\varphi_n$. (These won't be all the indices for $\varphi_n$, just some of them, since in general telling whether $m$ is an index for $\varphi_n$ is undecidable; but that's fine.)
Now let $X$ be your favorite noncomputable set, and let $$S_X=\{n_x: x\in X\}.$$ Since $X$ is not computable, we can find $a\in X$ and $b\not\in X$; do you see why the existence of $a$ and $b$ means that $S_X$ is not an index set? And, do you see why $S_X$ is not computable (HINT: use the computability of the sequence $n_0, n_1, n_2, ...$)?
Now, this isn't a very natural example of a noncomputable non-index set. You are right that $H$ forms an example, and it's clearly a better one; but showing that $H$ isn't an index set does take a moment of thought.
Suppose we had some $x$ such that $\varphi_x(x)\downarrow$ but $\varphi_x(y)\uparrow$ for all $y\not=x$. Then clearly we'd have $x\in H$.
On the other hand, by the Padding Lemma, we can find some $x'>x$ with $\varphi_{x'}=\varphi_x$. Can we have $x'\in H$?
So if we can find such an $x$, we'll be done. Do you see how to show that such an $x$ exists? (HINT: use the Recursion Theorem . . .)