Given the following two statements: 𝑆1: If 𝐿1 and 𝐿2 are recursively…

Conclusion: Both S1 and S2 are correct.

• S1 (closure under union and intersection): Given Turing recognizers (enumerators or recognizers) for L1 and L2, you can construct recognizers for both the union and the intersection as follows.

  1. Union: On input w, simulate both recognizers for L1 and L2 in a dovetailed (interleaved) fashion. If either recognizer accepts w, have the combined machine accept. If w is in L1 ∪ L2, at least one recognizer will eventually accept, so the combined machine accepts. If w is not in the union, the simulation may run forever, which is permitted for a recognizer.

  2. Intersection: On input w, dovetail the simulations of the two recognizers and accept only when both recognizers have accepted. If w is in L1 ∩ L2, both recognizers will eventually accept and the combined machine accepts. If w is not in the intersection, the combined machine may never accept, which matches the behaviour of a recognizer.

• S2 (countability of recursively enumerable languages): Each Turing machine has a finite description over a finite alphabet, so there are only countably many distinct Turing machine descriptions. Every recursively enumerable language is the language recognized by at least one Turing machine, so the collection of recursively enumerable languages is at most countable. Hence the set of recursively enumerable languages is countable (indeed countably infinite). Note that the set of all languages over Σ is uncountable, so many languages are not recursively enumerable.