simple sets, cofinite sets, filters

Question

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.

Answer 1

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.