# Does closure against countable union survive union of classes?

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.

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.

• Nice answer, but to another question. You've shown that any language in the closure of $\mathcal{C}\cup\mathcal{C'}$ is decidable, which is actually more interesting, I'll add that to the question. Moreover you actually pointed out that the answer to (1) is: "no, since it's not even always closed under finite union". Note, that there's no need to treat finite unions separately since a series may have only finitely many different values, if one likes. Mar 20, 2013 at 15:29
• Usually when you say that a collection is closed under countable unions, you allow choosing the same point (in this case, language) more than once, so in particular the collection is closed under finite (non-empty) unions. Mar 21, 2013 at 0:25
• This is exactly what I said, but you treated them specially, by assuming the $T$s to be infinite. Mar 21, 2013 at 0:30
• Right - now I see what you mean. Mar 21, 2013 at 0:34

The answer to (1) is no:

Given $L \in \mathcal{C} = \{n\text{-}\mathrm{SAT}\mid n\in\mathbb{N}\}$ and $L' \in \mathcal{C'} = \{n\text{-}\mathrm{UNSAT}\mid n\in\mathbb{N}\}$ the union $L\cup L'$ does contain satisfiable and unsatisfiable formulas, which non of the languages in $\mathcal{C}\cup\mathcal{C'}$ do.

As Yuval Filmus indirectly pointed out the countable union of sets in $\mathcal{C}\cup\mathcal{C'}$ is just a finite union of languages $L \in \mathcal{C}$ and $L' \in \mathcal{C'}$ since they both are closed under countable union and any series of languages in $\mathcal{C}\cup\mathcal{C'}$ can be partitioned into two series of languages in $\mathcal{C}$ and $\mathcal{C'}$ respectively.