7
$\begingroup$

Is the intersection of infinitely many recursive sets $\bigcap_{i}U_{i}$ (where each set is different ) recursive? Recursively enumerable? I know the union need not be recursive, because deciding if an element is in the set $U_i$ is the same as deciding the Halting Problem since you for each element you'll have to decide if the function that computes if $x \in U_i$ for some $i$ will terminate.

$\endgroup$
  • $\begingroup$ Should "infinite recursive sets" be "infinitely many recursive sets"? $\endgroup$ – Andrej Bauer Feb 12 '18 at 18:07
  • $\begingroup$ @AndrejBauer yes $\endgroup$ – user43288 Feb 12 '18 at 18:10
  • $\begingroup$ By that reasoning everything is the same as deciding the halting problem. I want to know if the input number equals 42, to do that I have to decide if the program that only halts if the input number is 42 will halt. $\endgroup$ – user253751 Feb 12 '18 at 22:31
6
$\begingroup$

Since you already know about unions, you could figure this out by remembering the de Morgan laws: the complement of a union is the complement of the intersection of complements. With this in mind: let $U_i$ be the set of (indices of) Turing machines that do not halt within $i$ steps of execution. So, the complement $\mathbb{N} \setminus U_i$ is the set of (indices) of those machines that halt within the first $i$ steps.

Now we have: $$\textstyle\bigcap_i U_i = \mathbb{N} \setminus \bigcup_i (\mathbb{N} \setminus U_i) = \mathbb{N} \setminus H$$ where $H$ is the halting set. The complement of $H$ is neither recursive nor recursively enumerable.

By the way, you state that "deciding if an element is in the set $U_i$ is the same as deciding the Halting Problem ..." which is not necessarily true. For instance, if I set $U_i = \{42\}$ for all $i$, then all the $U_i$ are decidable. You need to pay attention to what your $U_i$'s are.

$\endgroup$
8
$\begingroup$

For each $i\in \mathbb{N}$, take $S_i = \mathbb{N}\setminus \{i\}$. You can now build any set you want as $X = \bigcap_{i\notin X}S_i$.

Similarly, an easier proof that a union of recursive sets can be anything at all is to let $T_i=\{i\}$ and now any set $X$ is $X = \bigcup_{i\in X}T_i$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy