the definitions def-comp-enum and def-recur-enum below define an enumerable set to be the domain of some recursive function, but roger's defines it to be the range of some recursive function.
- a set is computably enumerable (c.e.) if is the domain of some partial computable function.
- let the th c.e. set be denoted by
note that any computable set is c.e. since if is computable, then , where if the characteristic function and otherwise.
the set is called recursively enumerable if there is a partially computable function such that
is recursively enumerable if either or there exists a recursive such that .
let be a nonempty set. then there is a primitive recursive function such that . that is, is the range of .
let be a partially computable function and let . (that is, is the range of .) then is r.e.
suppose that . then the following statements are all equivalent
- is r.e.;
- is the range of a primitive recursive function;
- is the range of a recursive function;
- is the range of a def-recursive-function-soare.
is c.e.. (taken from robert i. soare, 2016 theorem 1.6.4)
is the domain of the following p.c. function:
is not computable.
let .
by quantifier contraction theorem, the projection of a c.e. relation is c.e.
the following sets and relations are c.e.
the c.e. sets are closed under union and intersection uniformly, i.e., there are computable functions and such that and .
a set is computable iff both and are c.e., i.e. iff .
(taken from robert i. soare, 2016 theorem 2.1.14), (also in Martin Davis, Ron Sigal, Elaine J. Weyuker, 1994 chapter 4.4 recursively enumerable sets theorem 4.4)
a partial function is partial computable iff its graph is computably enumerable.
let be a nonempty r.e. set. then there is a primitive recursive function such that . that is, is the range of .
if is a recursive set, then is r.e.
is the set of all recursively enumerable sets computably enumerable itself?
no, this cant be true, otherwise RE in RE, which isnt correct in usual set theory, but what if the set theory foundation allowed such sets?. if we drop that axiom from set theory, then we could have , we can write a program that receives an element of RE and iterates through all numbers, and checks if the number is an encoding of a function that converges on all inputs, this is demonstrated in sol-noncomp-2. using this technique, we would diverge if there is no function that converges on all inputs of the elements, and converge otherwise. perhaps this result wouldnt be important however.
what is an example of a recursively enumerable set that is neither decidable nor m-complete?