Problem 9.
For A ⊆ Σ
∗ and n ∈ N, we define the n
th slice of A to be the language
An = {y ∈ Σ
∗
|<n, y> ∈ A} ,
where <n, y> = <sn, y> and s0, s1, . . . is the standard enumeration of Σ∗
.
Let C and D be classes of languages.
1. C parametrizes D (or C is universal for D) if there exists A ∈ C such that
D = {An|n ∈ N}.
2. D is C-countable if there exists A ∈ C such that D ⊆ {An|n ∈ N}.
(a) Prove: A class D of languages is countable if and only if D is P(Σ∗
)-countable.
(b) Prove that DEC is not DEC-countable.
Problem 10.
(a) Assume that C and D are sets of languages and g : C
onto −−→ D. Prove: if C is countable,
then D is countable.
(b) Prove: if C is a countable set of languages, then ∃C and ∀C are countable.
Problem 11. Prove that the class of countable languages (defined as CTBL in class) is a
σ-ideal on P(Σ∗
).
1
Problem 12 Prove all the inclusions in the infinite diagram.
∆0
1
⊇
Σ
0
1
⊆
Π0
1
⊆
⊇
∆0
2
⊇
Σ
0
2
⊆
Π0
2
⊆
⊇
∆0
3
⊇
Σ
0
3
⊆
Π0
3
⊆
⊇ .
.
.
Problem 13. Prove that there is a function g : N → N with the following properties.
(i) g is nondecreasing, i.e., g(n) ≤ g(n + 1) holds for all n ∈ N.
(ii) g is unbounded, i.e., for every m ∈ N there exists n ∈ N such that g(n) > m.
(iii) For every computable, nondecreasing, unbounded function f : N → N, f(n) > g(n)
holds for all but finitely many n ∈ N.
Problem 14. Prove that a partial function f : ⊆ Σ
∗ → Σ
∗
is computable if and only if its
graph
Gf = {<x, f(x)> | x ∈ dom f}
is c.e.
Problem 15. Let A ⊆ Σ
∗ be c.e., and let B be an infinite decidable subset of A. Prove: If
A is undecidable, then A B is undecidable.
Problem 16. Let A = L(U) be the universal c.e. language defined in class lectures, and let
B ⊆ Σ
∗
. Prove: If A ≤m B and Σ∗ A ≤m B, then B is neither c.e. nor co-c.e.