4
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – frafl Mar 20 '13 at 15:29
  • $\begingroup$ 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. $\endgroup$ – Yuval Filmus Mar 21 '13 at 0:25
  • $\begingroup$ This is exactly what I said, but you treated them specially, by assuming the $T$s to be infinite. $\endgroup$ – frafl Mar 21 '13 at 0:30
  • $\begingroup$ Right - now I see what you mean. $\endgroup$ – Yuval Filmus Mar 21 '13 at 0:34
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.