3
$\begingroup$

Is the intersection of countably many countable sets countable? My thinking is yes, because the intersection of two sets results in a set of size less than or equal to the largest set. My other question, is the intersection of countably many countable sets recursively enumerable? I can imagine writing a program that lists the members of the union of countably many infinite sets by diagonal enumeration, but I can't say the same for intersection. My assumption is that this is not possible because we could never check to see whether the first element of the first set belongs to all the sets.

$\endgroup$
0

1 Answer 1

7
$\begingroup$

Is the intersection of countably many countable sets countable?

Yes, of course it is. Since a subset of a countable set is countable, it follows that the intersection of an arbitrary family of sets is countable if at least one of them is countable.

My other question, is the intersection of countably many countable sets recursively enumerable?

I think you meant to ask whether the intersection of countably many recursively enumerable sets is recursively enumerable. The intersection of finitely many r.e. sets is r.e., but the intersection of countably many r.e. sets is not necessarily r.e. For example, let $S_n$ be the set of all Turing machines which (starting on a blank tape) do not halt within the first $n$ steps. Each set $S_n$ is r.e. (in fact recursive), but the intersection $S=\bigcap_{n\in\mathbb N}S_n$ is not r.e. This is because the complement of $S$, the set of all Turing machines which halt, is r.e. but not recursive.

$\endgroup$
3
  • $\begingroup$ Thank you very much for answering my question! If you don't mind, can you tell me if the union of countably many r.e. sets is necessarily r.e.? $\endgroup$
    – user279420
    Oct 12, 2015 at 6:31
  • $\begingroup$ Well, every subset of $\mathbb N$ is the union of countably many singleton sets, which are of course recursive. On the other hand, the union of an r.e. set of r.e. sets is r.e. More precisely, if $W_n$ is the r.e. set produced by the $n^{\text th}$ Turing machine (in some effective enumeration of Turing machines), and if $S$ is an r.e. subset of $\mathbb N$, then $\bigcup_{n\in S}W_n$ is r.e. (At least it seems so to me, but I should warn you that I'm not a logician, I'm just going on intuition here.) $\endgroup$
    – bof
    Oct 12, 2015 at 6:43
  • $\begingroup$ Cool! Well I'm going to believe that it's r.e. until I find proof against it. Thanks for your honesty and again for answering my questions in full. $\endgroup$
    – user279420
    Oct 12, 2015 at 6:53

Your Answer

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