2
$\begingroup$

Let $\{A_n : n \in \mathbb{N}\}$ be a collection of c.e. (computably enumerable) sets. Is $\bigcup_n A_n$ c.e.?

That is, is the union of c.e. sets c.e.? Otherwise, under what conditions will this be true?

$\endgroup$
2
$\begingroup$

Every language can be written as a countable union of singletons $\{x\}$.

On the other hand, the union of finitely many c.e. languages is c.e.

$\endgroup$
3
  • $\begingroup$ We can be more general, the union of a c.e. set of c.e. sets is c.e itself, not just finite. $\endgroup$
    – orlp
    Apr 3 at 13:25
  • $\begingroup$ Thanks but how does one go about proving this. Is this a standard theorem etc. Any links online where proof is available $\endgroup$ Apr 3 at 14:24
  • 1
    $\begingroup$ Take it as an exercise. $\endgroup$ Apr 3 at 15:16
0
$\begingroup$

For any c.e. collection of c.e. sets, the union is c.e., however if the collection itself is not c.e, then not (a counterexample is $S_x = \{x + n : n \in \mathbb{N}\}$, then $\bigcup_{x\in\mathbb{R}} S_x$ is not c.e. even though it's a union of only c.e. sets).

To see the above by explicit construction, first if you allow duplicates in your enumeration (this isn't strictly the union of sets) then we have an explicit map from $\mathbb{N} \to \mathbb{N}^2$. See for example the inverse of the Cantor pairing function. Then we can first select which c.e. set to pick, and then which element from that set. You can explicitly filter out the duplicates afterwards to get a proper enumeration.

$\endgroup$
4
  • 1
    $\begingroup$ I am bit confused. Did you mean the answer to the question I posted as true or false ? ie. The union of ce sets here it's over natural numbers till inifinity. So is the ce ? $\endgroup$ Apr 3 at 14:34
  • $\begingroup$ How do you even define c.e for a set of sets? $\endgroup$
    – nir shahar
    Apr 3 at 14:48
  • $\begingroup$ A collection $A_n$ of c.e. sets is uniformly c.e. if there is a Turing machine that on input $n$, enumerates all words in $A_n$. We can relax that even further in various ways. For example, we could have a Turing machine which enumerates pairs $(n_i,w_i)$, which correspond to the collection $A_n = \{ w_i : n_i = n \}$. $\endgroup$ Apr 3 at 15:15
  • $\begingroup$ @Amitwadhwa It depends on whether you have a Turing machines that can generate the elements of $A_n$. IMO the standard definition of a c.e. set is unwieldy and confusing and an (equivalent) definition that simply asks for a Turing machine $M$ that maps integer $n$ to an encoding of the $n$th element of the set (in some arbitrary order without duplicates) is much simpler to think about and compose to answer questions like these. If you can construct a Turing machine computing a bijective mapping between $\mathbb{N}$ and some set $S$, then $S$ is r.e. $\endgroup$
    – orlp
    Apr 3 at 15:48

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.