# Definition of Productive set

I don't understand the definition of Productive Set in the Cutland's Computability book.

DEFINITION: A set $$A$$ is productive if there is a total computable function $$g$$ such that whenever $$W_{x} \subseteq A$$, then $$g(x) \in A$$ \ $$W_{x}$$. The function $$g$$ is called a productive function for A.

I don't understand what is the domain of the function $$g$$. Could $$g$$ be defined as $$g:W_{x} \rightarrow A$$ \ $$W_{x}$$?

• What is $W_x$ ? – Holo Mar 12 at 23:30
• @Holo That's the standard notation for the $x$th recursively enumerable set in some fixed "reasonable" enumeration (the specific choice of enumeration - essentially, a choice of universal Turing machine - never really matters). – Noah Schweber Mar 12 at 23:33
• @NoahSchweber thanks – Holo Mar 12 at 23:35

The domain of $$g$$ is all of $$\mathbb{N}$$ - that's the case for every total function. The point is that $$g(x)$$ is defined whether $$W_x\subseteq A$$ or not; and whenever $$W_x$$ is a subset of $$A$$, we have $$g(x)\in A\setminus W_x$$.
In particular, you should think of $$g$$ as taking as input an index for an r.e. set, not an element of some specific r.e. set $$W_x$$.
It might be easier to consider the "higher-type" picture: we're intuitively interested in a map $$G$$ from the set $$\mathcal{W}$$ of all r.e. sets to $$\mathbb{N}$$, such that $$G(W)\in A\setminus W$$ whenever $$W$$ is an r.e. subset of $$A$$. That is, $$G$$ sends an r.e. subset of $$A$$ to something in $$A$$ that that set "misses" (and does wedon'tcarewhat on an r.e. set which isn't a subset of $$A$$).
Now this isn't actually what we get, since $$(1)$$ our $$g$$ is a map from $$\mathbb{N}$$ to $$\mathbb{N}$$ rather than $$\mathcal{W}$$ to $$\mathbb{N}$$ and $$(2)$$ more fundamentally, a $$g$$ witnessing productivity might not be "index-invariant" (just because $$W_x=W_y$$ doesn't mean $$g(x)=g(y)$$). But it may help convey a bit of the intuition.