Given a productive set, there is a collection of c.e. sets union of which is the productive set, as we know that every c.e. set is with a c.e. function with a index. My question: is the set of the indices of c.e.sets that cover a productive set also productive one?
$\begingroup$
$\endgroup$
2
-
1$\begingroup$ This is a bit unclear. Are you asking whether, for $P$ productive and $P=\bigcup_{e\in E}W_e$, we must have $E$ also be productive? (Note that there is not a unique way to cover a productive set by c.e. sets. Also, note that we can never have this $E$ be c.e.: a c.e. union of c.e. sets is c.e., and productive sets are never c.e.) $\endgroup$– Noah SchweberCommented Oct 1, 2021 at 5:12
-
$\begingroup$ @NoahSchweber Yes, this is what I ask about. I mean, for a P productive and $P=\bigcup e \in E$, We, we must have E also be productive? Is this a trivial question? $\endgroup$– XL _At_Here_ThereCommented Oct 2, 2021 at 22:58
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
No, it isn't. This is a consequence of the fact that we have a choice of infinitely many equivalent indices for each c.e. set. Let $E$ be a set of indices such that
$$(e, j \in E \land e \neq j) \implies W_e \neq W_j $$ $$ P = \bigcup_{e \in E} W_e$$
For any $e$ let $e' \neq e$ with $W_e = W_{e'}$ (note that if $e \in E$ then $e'$ isn't by assumption). Now we build $\hat{E}$ by meeting requirements $R_i$ ensuring that $\phi_i$ isn't a production function for $\hat{E}$.
Let $e_i$ be an enumeration of elements of $E$ in order. Suppose at the start of stage $s$ we've have $\hat{E}_s = \lbrace \hat{e}_0, \ldots, \hat{e}_{n} \rbrace$ Let $j_s$ be such that $W_{j_s} = \hat{E}_s$ (must exist as it's finite). Now compute $\phi_s(j_s)$. If it doesn't converge or $\phi_s(j_s) \in \hat{E}_s$, or $\phi_s(j_s) = e_k, k \leq n$ then we've met $R_i$ as it's either not in $\hat{E}$ or is in $W_{j_s}$. So set $\hat{e}_{n+1} = e_{n + 1}$.
If $\phi_s(j_s)$ isn't of the form $e_k$ or $e'_k$ for some $k$ it similarly won't be in $\hat{E}$ so do the same.
If $\phi_s(j_s) = e_k$ or $\phi_s(j_s) = e'_k$ for $k > n$ then simply set $\hat{e}_k$ to be equal to whichever one disagrees with $\phi_s(j_s)$ so $\phi_s(j_s) \neq \hat{e}_k$ and set $\hat{e}_l, n < l < k$ to be $e_l$ giving us $E_{s+1}$.
--
However, note that if $E$ is the set of all $e$ with $W_e$ contained in $P$ then I'm pretty sure it will be productive since we can just consider the set of all indexes for the empty c.e. set and notice that we can m-reduce $\bar{0'}$ to that set.
