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?