0

when Recursively enumerable sets are not closed under complement ,then how come they are closed under intersection because the definition of intersection comes as

L1 intersection L2= complement(L1' union L2') for languages L1 and L2

So When complement is not closed but union is closed can the complement of the union of the complements be closed?

I am not getting that when at the end the major operation to be performed is complement only then how come it becomes closed ?

RADHA GOGIA
  • 197

1 Answers1

5

Recursively enumerable sets are closed under union, but not complementation; this is true.

So the argument "take the complement of the union of the complements" does not show that the recursively enumerable sets are closed under intersection.

However, just because one argument doesn't work, doesn't mean the principle is false. Indeed, recursively enumerable sets are closed under intersection: if $\varphi_e$ enumerates $X$ and $\varphi_f$ enumerates $Y$, then consider the machine $\varphi_i$ which - on input $n$ - first runs $\varphi_e(n)$; then, if that halts, runs $\varphi_f(n)$; then, if that halts, halts. Then we have $$n\in dom(\varphi_i)\iff n\in dom(\varphi_e)\cap dom(\varphi_f),$$ as desired.

This can make things seem very nice and symmetric: r.e. sets are closed under both union and intersection. However, this is not the case once we start talking about infinite unions and intersections. Obviously the r.e. sets are not closed under arbitrary infinite unions/intersections. However, we can talk about recursive unions and recursive intersections:

  • Given a recursive sequence $s_0, s_1, s_2, . . . \in\omega$, is $\bigcup_{i\in\omega} W_{s_i}$ recursively enumerable?

  • Given a recursive sequence $s_0, s_1, s_2, . . . \in\omega$, is $\bigcap_{i\in\omega}W_{s_i}$ recursively enumerable?

Now the asymmetry between union and intersection comes clear. The recursively enumerable sets are closed under effective union: given a recursive sequence $s_i$ and a number $n$, we run

  • $\varphi_{s_0}(n)$ for one step,
  • $\varphi_{s_1}(n)$ for two steps and then $\varphi_{s_0}(n)$ for two steps,
  • $\varphi_{s_2}(n)$ for three steps, then $\varphi_{s_1}(n)$ for three steps, then $\varphi_{s_0}(n)$ for three steps,
  • . . . That is, we simulate running all of the $\varphi_{s_i}$s at once, via "dovetailing" (this process of "run a bit, then come back later"). If any one of these computations halts, we halt. This gives a description of a machine witnessing that $\bigcup_{i\in\omega} W_{s_i}$ is recursively enumerable.

The point, though, is that it was crucial that we run our various machines $\varphi_{s_i}$ in parallel. To compute the recursive intersection, we would need to run them in sequence, and this would take infinitely long: we'd need to wait until $\varphi_{s_0}(n)\downarrow$, then $\varphi_{s_1}(n)\downarrow$, then $\varphi_{s_2}(n)\downarrow$, . . . So the recursively enumerable sets are not closed under recursive intersection.

Exercise: show that if $A$ is recursively enumerable, then $\overline{A}$ is the recursive intersection of r.e. - in fact, cofinite - sets.

So there is a fundamental asymmetry between union and intersection in the recursively enumerable sets. If the recursively enumerable sets were closed under complementation, then this asymmetry would disappear via complement-union-complement - and in fact, for the recursive sets (which are closed under complementation), recursive intersection and recursive union have the same closure properties (the recursive sets are closed under neither; exercise).

Noah Schweber
  • 245,398