simple sets, cofinite sets, filters Let $\mathcal S$ be the class of simple sets and $\mathcal C$ the class of cofinite sets. Prove that $\mathcal S\bigcup \mathcal C$ is a filter in $\mathcal E$. 
Definitions:
An infinite set is "immune" if it contains no infinite c.e. set.
A c.e. set $A$ is simple if $\bar{A}$ is immune.
A filter of $\mathcal E$ is a subset of the lattice that is closed upward and under intersections.
 A: Fairly Complete Outline: It suffices to show that $\mathcal{S} \cup \mathcal{C}$ is closed under (r.e.) supersets and intersections.


*

*Clearly every r.e. superset of a simple set is either simple or cofinite, and every superset of a cofinite set is cofinite, so $\mathcal{S} \cup \mathcal{C}$ is closed under supersets.

*Now suppose $A , B \in \mathcal{S} \cup \mathcal{C}$, and go through the cases to show that $A \cap B \in \mathcal{S} \cap \mathcal{C}$:

*

*If $A , B \in \mathcal{S}$, then $A \cap B$ is r.e. and co-infinite.  If $A \cap B$ were finite, then $A \cap \overline{ A \cap B } = A \cap \overline{B}$ would be an infinite r.e. subset of $\overline{B}$, and so $A \cap B$ must be infinite.  If $Z \subseteq \overline{A \cap B} = \overline{A} \cup \overline{B}$ is an infinite r.e. set, then, without loss of generality, $Z \cap A \subseteq \overline{B}$ is infinite (and r.e.), contradicting the simplicity of $B$!

*If $A \in \mathcal{S}$ and $B \in \mathcal{C}$, then $A \cap B$ is r.e., infinite and co-infinite.  If $Z \subseteq \overline{ A \cap B } = \overline{A} \cup \overline{B}$ is r.e., then $Z \cap B \subseteq \overline{A}$ is r.e., and so it must be finite, and so $Z$ itself is finite.  Thus $A \cap B$ is simple.

*If $A , B \in \mathcal{C}$, then $A \cap B$ is cofinite.


