A user-friendly Introduction to (un)Computability and Unprovability
via “Church’s Thesis” Part III
0.1. Recursively Enumerable Sets
In this section we explore the rationale behind the al- ternative name “recursively enumerable” —r.e.— or “com- putably enumerable” —c.e.— that is used in the literature for the semi-recursive or semi-computable sets/predicates.
To avoid cumbersome codings (of n-tuples, by single numbers) we restrict attention to the one variable case in this section.
That is, our predicates are subsets of N. Intro to (un)Computability via URMs—Part II © by George Tourlakis
2
0.1.1 Definition. A set A ⊆ N is called computably enumerable (c.e.) or recursively enumerable (r.e.) pre- cisely if one of the following cases holds:
•A=∅
• A = ran(f), where f ∈ R.
Thus, the c.e. or r.e. relations are exactly those we can algorithmically enumerate as the set of outputs of a (total) recursive function:
A = {f(0),f(1),f(2),…,f(x),…}
Hence the use of the term “c.e.” replaces the non techni- cal term “algorithmically” (in “algorithmically” enumer- able) by the technical term “computably”.
Note that we had to hedge and ask that A ̸= ∅ for any enumeration to take place, because no recursive function (remember: these are total) can have an empty range.
Intro to (un)Computability via URMs—Part II © by George Tourlakis
First we define:
0.1. Recursively Enumerable Sets 3 Next we prove:
0.1.2 Theorem. (“c.e.” or “r.e.” vs. semi-recursive)
Any non empty semi-recursive relation A (A ⊆ N) is the range of some (emphasis: total) recursive function of one variable.
Conversely, every set A such that A = ran(f) —where λx.f(x) is recursive— is semi-recursive (and, trivially, nonempty).
Intro to (un)Computability via URMs—Part II © by George Tourlakis
4
0.1.3 Example. The set {0} is c.e. Indeed, f = λx.0, our familiar function Z, effects the enumeration with rep- etitions (lots of them!)
x =01234… f(x)=0 0 0 0 0 …
Proof. of Theorem 0.1.2.
(I) We prove the first sentence of the theorem.
So, let A ̸= ∅ be semi-recursive.
By the projection theorem (see Notes #7) there is
a recursive relation Q(y, x) such that
x ∈ A ≡ (∃y)Q(y,x), for all x (1)
Thus, the totality of the x in A are the 2nd coor- dinates of ALL pairs (y, x) that satisfy Q(y, x).
So, to enumerate all x ∈ A just enumerate all pairs (y, x), and OUTPUT x just in case (y, x) ∈ Q.
Intro to (un)Computability via URMs—Part II © by George Tourlakis
Before we prove the theorem, here is an example:
0.1. Recursively Enumerable Sets 5
We enumerate all POSSIBLE PAIRS y, x by (y = (z)0, x = (z)1)
for each z = 0,1,2,3,….
RecallthatA̸=∅. Sofixana∈A. f belowdoes
the enumeration!
(z)1 if Q((z)0, (z)1)
f(z) =
a othw
The above is a definition by recursive cases hence f is a recursive function, and the values x = (z)1 that it outputs for each z = 0,1,2,3,… enumerate A.
Intro to (un)Computability via URMs—Part II © by George Tourlakis
6
(II) Proof of the second sentence of the theorem. So, let A = ran(f) —where f is recursive.
Thus,
x ∈ A ≡ (∃y)f(y) = x (1)
By Grz-Ops, plus the facts that z = x is in R∗ and the assumption f ∈ R,
the relation f(y) = x is recursive.
By (1) we are done by the Projection Theorem.
Intro to (un)Computability via URMs—Part II © by George Tourlakis
0.1. Recursively Enumerable Sets 7 0.1.4 Corollary. An A ⊆ N is semi-recursive iff it is
r.e. (c.e.)
Proof. For nonempty A this is Theorem 0.1.2. For empty A we note that this is r.e. by Definition 0.1.1 but is also semi-recursive by ∅ ∈ PR∗ ⊆ R∗ ⊆ P∗.
Corollary 0.1.4 allows us to prove some non-semi-recursiveness results by good old-fashioned Cantor diagonalisation.
See below.
Intro to (un)Computability via URMs—Part II © by George Tourlakis
8
0.1.5 Theorem. The complete index set A = {x : φx ∈ R} is not semi-recursive.
This sharpens the undecidability result for A that we es- tablished in Note #7.
Proof. Since c.e. = semi-recursive, we will prove instead that A is not c.e.
If not, note first that A ̸= ∅ —e.g., S ∈ R and thus all φ-indices of A are in A.
Thus, theorem 0.1.2 applies and there is an f ∈ R that enumerates A:
A = {f(0), f(1), f(2), f(3), . . .}
The above says: ALL programs for unary R-functions are f(i)’s.
Define now
d = λx.1 + φf(x)(x) (1) Seeing that φf(x)(x) = U(P)(f(x),x) —you remember
U(P)?— we obtain d ∈ P.
But φf(x) is total since all the f(x) are φ-indices of total functions by the underlined blue comment above.
By the same comment,
d = φf(i), for some i (2) Intro to (un)Computability via URMs—Part II © by George Tourlakis
0.1. Recursively Enumerable Sets 9 Let us compute d(i): d(i) = 1 + φf(i)(i) by (1).
Also, d(i) = φf(i)(i) by (2), thus
1 + φf(i)(i) = φf(i)(i)
which is a contradiction since both sides of “=” are
defined.
One can take as d different functions, for example, either
of d = λx.42 + φf(x)(x) or d = λx.1 −. φf(x)(x) works. And infinitely many other choices do!
Intro to (un)Computability via URMs—Part II © by George Tourlakis
10
0.2. Some closure properties of decidable and semi-decidable relations
We already know that
0.2.1 Theorem. R∗ is closed under all Boolean opera-
tions, ¬, ∧, ∨, →, ≡, as well as under (∃y)