# Is membership of x in an infinite set decidable?

In order to prove a certain function to be partially computable, I need to show an $\mathbb S$-program that computes it. I could really use the predicate $X \in B$ in my program to draw my conclusion. To give you the idea of what I am dealing with here it is one of my problems:

Give an infinite set $B$ such that $\Phi(x,x)\uparrow$ for all $b \in B$ and such that $$H(x) = \begin{cases}1 \text{ if } \Phi(x,x)\downarrow \\ 0 \text{ if } x \in B \\ \uparrow \text{ otherwise}\end{cases}$$ show that $H(x)$ is partially computable.

I am wondering if membership for infinite set is decidable and therefore can be used to write $\text{IF } X \in B$ such program. Am I allowed?

Edit: the notation $\Phi(x,x)\uparrow$ means the function is undefined.

• It depends on the set. It is decidable whether a number belongs to the set of all primer. It is not decidable whether a number is the code of a total function. You should explain more carefully what your exact problem is. Also, the rest of the planet does not necessarily know what a "$\mathbb{S}$-program" might be (but we can also tell it doesn't matter). – Andrej Bauer Nov 21 '13 at 21:04
• Is the beginning of the second paragraph supposed to be "$B$ such that $\Phi(x,x)\uparrow$ for all $x \in B$"? – Andrej Bauer Nov 21 '13 at 21:04
• I am going to go in a limb here and guess that your set $B$ is assumed to be recursively enumerable. Then the whole thing becomes a homework, more or less. – Andrej Bauer Nov 21 '13 at 21:05
• Some infinite sets can be searched in finite time see here – adrianN Nov 22 '13 at 9:47
• @adrianN I can't tell whether I should be honored, amused, or disappointed that you're referring to my own blog (but a post written by a guest contributer). – Andrej Bauer Nov 22 '13 at 22:01

No, this is not allowed, in general, if we know nothing about the set $B$.
As Andrej Bauer explains in the comments: if the set $B$ is arbitrary and there are no guarantees about the set $B$ (as you state in the comments), then no, you cannot write "IF $X \in B$" in a program, as the predicate $X \in B$ might not be computable (depending upon the set $B$).
Re-reading your question, I see that you are allowed to choose a set $B$ of your choice (subject to some conditions). If you're able to choose $B$ in a way that makes $B$ recursively enumerable, then $B$ is no longer completely arbitrary and you now have an additional condition on $B$ which makes this a straightforward homework (as Andrej Bauer also explains in the comments).