Set of languages

For A ⊆ Σ
∗ and n ∈ N, we define the n
th slice of A to be the language
An = {y ∈ Σ
∗
| ∈ A} ,
where = 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 ∈ 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.