Linear regression

Problem 9.
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(Σ∗
   )