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.

Improve this question
$\endgroup$
0

2 Answers 2

Reset to default
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.

Improve this answer
$\endgroup$
4
  • $\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
    Commented Mar 20, 2013 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
    Commented Mar 21, 2013 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
    Commented Mar 21, 2013 at 0:30
  • $\begingroup$ Right - now I see what you mean. $\endgroup$
    – Yuval Filmus
    Commented Mar 21, 2013 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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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