Definition of Productive set

406 Views Asked by At

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}$?

1

There are 1 best solutions below

0
On

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.