Some non r.e. sets *S* are, in a way of speaking, “effectively non r.e.” in that we have an algorithmic way to refute their r.e.-ness in the context of any claim of the form “*W*_{x} = *S*”. That is, we can *construct* a counterexample *m* ∈ *S* – *W*_{x}. Such sets were called *productive* by Dekker.

**2.8.0.15 Definition.** A set *S* is *productive* with a *productive function f* ∈ if, for all *x*, whenever we have *W*_{x} ⊆ *S* then *f*(*x*) ∈ *S* – *W*_{x}.

**2.8.0.16 Example.** is productive with productive function *x.x.* Indeed, let *W*_{x} ⊆ . Note that this entails that *x* ∈ *W*_{x} is false, for it says _{x}(*x*) ↓, that ...

Start Free Trial

No credit card required