patternMinor
Is the intersection of infinitely many recursive sets recursive?
Viewed 0 times
theinfinitelyintersectionrecursivemanysets
Problem
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.
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.
Solution
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$.
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$.
Context
StackExchange Computer Science Q#88020, answer score: 8
Revisions (0)
No revisions yet.