I am interested in "Relative Decision Problems" in the following sense: Let $\mathbb{N} \supseteq U \supseteq S$. Is there an algorithm such that on a given input $u \in U$ decides whether $u \in S$?
My concerns come from the cases when the intermediate set $U$ is undecidable:
on one hand, it looks conceivable to me, to consider the decision problem "$S \subseteq U$" even when $U$ is undecidable. Is it so? (Can't you assume this uncomputable information known, and still have a reasonable well formulated "algorithmic" question of, say, second level?).
if so, it looks like that the undecidability of $U$ should make the decidability of "$S \subseteq U$" sensible to the context: eg. decidable if you assume the input in U, and undecidable if you assume the input in $\mathbb{N}$. Is it so? (If so, it would mean that this "relative decision problems" are not only not absurd, but also carry some kind of new algorithmic information, right?)
If the answer to the former questions is YES (which is mi initial guess) and the "relative decision problem" makes sense, then I'd like to know which is the appropiate context to formulate it. In particular, since I want the algorithmic question to be well formulated, I should need a reasonable description of the input set for this "second level" algorithm. But the input set is undecidable by assumption, so... how to do it?
Thank you in advance.
I think what you want is related to the notion of computable separability.
Two sets $A,B$ are separable if there exists some computable (partial) $f$ which evaluates $0$ on $A$ and $1$ on $B$. (Note: no requirements on $\mathbb{N}\setminus (A \cup B)$.)
In your case, to "relatively decide" $S \subseteq U \subseteq \mathbb{N}$ seems to be equivalent to separating $S$ and $U \setminus S$.