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

  • $\begingroup$ What is $W_x$ ? $\endgroup$ – Holo Mar 12 at 23:30
  • $\begingroup$ @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). $\endgroup$ – Noah Schweber Mar 12 at 23:33
  • $\begingroup$ @NoahSchweber thanks $\endgroup$ – 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.