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.
[Math] Is the Intersection of Countably Many Countable Sets Countable
elementary-set-theory
Best Answer
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.