[Solved]: Does closure against countable union survive union of classes?

Problem Detail: 

A class of languages $\mathcal{C}$ is closed under countable union (cucu) if for all series of languages in $\mathcal{C}$ ($(L_i)_{i\in\mathbb{N}} \in \mathcal{C}^\mathbb{N}$) the language $\bigcup_{i\in\mathbb{N}}L_i = \{x\mid \exists i\in\mathbb{N}: x \in L_i\}$ is an element of $\mathcal{C}$.

As we know most (if not all but $\mathsf{ALL} = \wp(\Sigma^*)$) interesting complexity classes are not closed under countable union as every Language $L$ is the countable union of some singleton Laguages $\{w_i\}$.

However there are some classes of decidable languages which are cucu like:

• $\{\{w\in\Sigma^*\mid |w| \leq i\}\mid i\in\mathbb{N}\}$
• $\{n\text{-}\mathrm{SAT}\mid n\in\mathbb{N}\}$
• every $\mathcal{C}$ s.t. every $L \in \mathcal{C}$ is cofinite

---

My questions:

1. Let $\mathcal{C},\mathcal{C'} \subset \mathsf{REC}$ be two classes of decidable languages s.t. both are cucu. Is $\mathcal{C} \cup \mathcal{C'}$ cucu?
2. Is there some "real" complexity class (i.e. defined by some machine model, grammar type, $\lambda$-calculus restriction etc.) that is cucu? (You may restrict it artificially (e.g. NFA, where each final state has a path to another final state), if it fits otherwise.)
3. Edit (after Yuval Filmus' answer): Given $\mathcal{C},\mathcal{C'}$, as in (1), does the closure of $\mathcal{C} \cup \mathcal{C'}$ under countable union only contain decidable languages?

(1) is the main question, (2+3) only addenda.

Asked By : frafl

Answered By : Yuval Filmus

The answer to (3) is yes. Suppose that $S \subseteq \mathcal{C} \cup \mathcal{C}'$. Then $S$ is countable, because $\mathcal{C}\cup\mathcal{C'}$ contains only decidable languages of which there are only countable many. Now let $T = S \cap \mathcal{C}$, $T' = S \cap \mathcal{C}'$. By assumption $L = \bigcup T \in \mathcal{C}$, $L' = \bigcup T' \in \mathcal{C}'$. Since $L,L'$ are decidable, $L \cup L'$ is decidable.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/10648

 Ask a Question

 Download Related Notes/Documents