Let $ X $ be a decidable subset of $ \mathbb{N} $ and let $ Y = \{p\,|\,\text{p is prime and }\exists x \in X : p|x\} $.
I know that $ Y $ is recursively enumerable so I have to use universal function and related theorems about recursively enumerable but undecidable sets. I don't really understand how to use this to make an example.
Any help would be greatly appreciated!
The key idea is to recognize that to tell that something is an element of $Y$, we may need to search arbitrarily far through $X$. E.g. maybe $2\in Y$ but the first multiple of $2$ in $X$ is googleplex. So the strategy for building $X$ will be to "outwait" any (computable) attempt to guess what the corresponding $Y$ is.
For simplicity, let's look at a slight variation of $Y$: the set $$Z=\{i: \exists x\in X(p_i\vert x)\},$$ where $p_i$ is the $i$th prime.
Let's first whip up our "atomic module" - the strategy we could use to solve a tiny part of the problem. Given a computable $f$ purporting to decide $Z$, we can build $X$ to defeat $f$ as follows:
Pick some prime $p_i$.
Wait for $f(i)$ to halt, and don't put any multiple of $p_i$ into $X$ while we do this (so $i$ doesn't enter $Z$ yet).
If $f(i)$ halts and outputs "NO" at some point in time, put some multiple of $p_i$ into $X$ (so $i$ enters $Z$ now and $f$ is permanently wrong); if that never happens, just never put any multiple of $p_i$ into $X$ at all (so $i$ never enters $Z$ but $f$ doesn't tell us that).
But now we have to do a bunch of those at once! The issues now are:
Don't numbers with multiple prime factors cause issues?
How do we handle multiple $f$s at once (remember, we have to defeat all computable $f$s)?
How do we make sure $X$ is decidable?
The first and second are straightforward: only work with prime powers, and just pick a different prime for each $f$, respectively.
The third is the one that's more interesting, and where the "outwait" idea is fully fleshed out. The point is that we can make lots of negative decisions while preserving the possibility of a later positive decision, a la:
For example, assuming we give the computable function $f$ the prime number $2$, we'll keep preventing powers of $2$ from entering $X$ until we see that we want to put a power of $2$ into $X$ - that is, until we see $f(2)$ halt and output NO. Do you see how to formalize this? (HINT: "if $f(2)$ hasn't halted by stage $n$, ...")