Links between "productive" and "completely productive" sets?

Question

In a computability course I met the two following notions :

A set $B$ is "completely productive" if there exists a total computable function $f$ such that : $\forall x \in \mathbb N \ (f(x) \in \overline B \Leftrightarrow f(x) \in \mathcal W_x)$.

and

A set $B$ is "productive" if there exists a total computable function $f$ such that : $\forall x \in \mathbb N \ (\mathcal W_x \subseteq B \Rightarrow f(x) \in B\setminus\mathcal W_x)$.

I was wondering what were the links between these two notions ? I noticed that if we consider the complement of the halting set $\mathcal K$, it was both "completely productive" and "productive". For instance, is one of the notion stronger than the other one ?

Thanks in advance !

Edit : The result of equivalence between these two notions has been proved by Myhill (Rogers, theory of recursive functions and effective computability) !

Answer 1

The two notions ("productive" and "completely productive") are equivalent. (Edit: @Maman has pointed out that this equivalence to due to Myhill, according to Rogers' recursion theory book.)

@AndreasBlass showed in his answer that completely productive implies productive.

For the other direction, let $B$ be productive, with $f$ a recursive function satisfying the defining property $$\forall x (W_x \subseteq B \Rightarrow f(x) \in B\setminus W_x).$$

Use the recursion theorem to find a recursive function $g$ such that, for all $x,$ $$W_{g(x)} = \begin{cases} \{f(g(x))\},&\text{ if }f(g(x))\in W_x,\\ \emptyset,&\text{ otherwise.} \end{cases}$$

(The recursion theorem can be applied because an r.e. index for the set defined by $$\begin{cases} \{f(y)\},&\text{ if }f(y)\in W_x,\\ \emptyset,&\text{ otherwise.} \end{cases}$$ can be computed uniformly in $x$ and $y.$ Here's how to enumerate that set: Just compute $f(y)$ and then start enumerating $W_x.$ Check each value enumerated; if $f(y)$ ever shows up in the enumeration of $W_x,$ output $f(y)$ and halt. If it never shows up, the algorithm will never halt and we'll output nothing at all.)

We claim that the composition $f\circ g$ witnesses that $B$ is completely productive:

For any $x,$ if $f(g(x))\not\in W_x,$ then $W_{g(x)}=\emptyset\subseteq B,$ and so, using the fact that $f$ witnesses the productiveness of $B,$ we have that $f(g(x))\in B\setminus W_{g(x)},$ so $f(g(x)\in B.$

Conversely, if $f(g(x))\in W_x,$ then $W_{g(x)} = \{f(g(x))\},$ so $f(g(x))\in W_{g(x)}.$ Using once again the fact that $f$ is a witness to the productiveness of $B,$ we can conclude that $W_{g(x)}\not\subseteq B.$ But $W_{g(x)} = \{f(g(x))\},$ so it follows that $f(g(x))\not\in B.$

Answer 2

As the terminology suggests, any completely productive set is productive. To prove it, let $B$ be completely productive, and let $f$ be as required in the definition. I claim that the same $f$ also witnesses that $B$ is productive. Indeed, if $W_x\subseteq B$, then the statements $f(x)\in\overline B$ and $f(x)\in W_x$ can't both be true. So, by our choice of $f$, they must both be false. That is, $f(x)\in B-W_x$.