How can I show that a maximal set is simple?

Question

Let's say that a set $S\subset \mathbb N$ is maximal if $S$ is recursively enumerable and if $W$ is another recursively enumerable set, then $(\mathbb N- S)\cap W$ is either finite or cofinite.

I'm trying to prove that a maximal set is simple. This involves showing two things: (a) $\mathbb N - S$ is infinite, and (b) for any infinite recursively enumerable set $I$, $I\cap S\ne \emptyset$.

I don't see why either of these should hold. For example, suppose for contradiction that $S\cap I$ is empty ($I$ as above). Then $(\mathbb N- S)\cap I= I$. By the assumption, this intersection, hence $I$, is finite or cofinite. It cannot be finite because $I$ is infinite, so $\mathbb N- I$ is finite. What does it contradict to?

Similarly, I don't see any contradiction if I assume that $\mathbb N- S$ is finite.

Answer 1

Lets start with what we know:

1. A subset $A$ of $\mathbb{N}$ is maximal if $A$ is coinfinite, recursively enumerable, and for every other recursively enumerable subset $B$ of $\mathbb{N}$, either (a) $B$ is cofinite, (b) $B$ is a finite variant of $A$, or (c) $B$ is not a superset of $A$.
2. If $C$ is maximal and $D$ is recursively enumerable and $D \neq C$, then $(\mathbb{N}-C)\cap D$ is either finite or cofinite.
3. A subset $E$ of $\mathbb{N}$ is immune if it is $E$ infinite, and there is no infinite subset of $E$ that is recursively enumerable.
4. A subset $F$ of $\mathbb{N}$ is simple if $F$ is recursively enumerable and its complement $(\mathbb{N} - F)$ is immune.

We want to show that a maximal subset $S \subseteq \mathbb{N}$ is simple. So we want to show that $S$ is recursively enumerable and that the complement of $S$ , which we write from now on as $(\mathbb{N}-S)$ is immune.

• We know by $(1)$ that $S$ is recursively enumerable, so all that we have to do is show that the $(\mathbb{N}-S)$ is immune.

To show that the $(\mathbb{N}-S)$ is immune we have to show that the $(\mathbb{N}-S)$ is infinite, and there is no infinite subset of the $(\mathbb{N}-S)$ that is recursively enumerable.

• Since $S$ is maximal, by $(1)$, $S$ is coinfinite and so $(\mathbb{N}-S)$ is infinite.

All that is left is to show that there is no infinite subset of $(\mathbb{N}-S)$ that is recursively enumerable.

• Suppose for the sake of contradiction that there is some infinite subset of $(\mathbb{N}-S)$ that is recursively enumerable, let's call it $W$. Since $S$ is maximal, by $(2)$, $(\mathbb{N}-S) \cap W$ is either finite or cofinite. But we claimed already that $W$ was a subset of $(\mathbb{N}-S)$, so since the intersection of a set with a subset of itself is equal to the subset, we have that $(\mathbb{N}-S) \cap W = W$ is either finite or cofinite. But we already said it was infinite, so $W$ must be cofinite. If $W$ is cofinite, then referring to $(1)$, $W$ is neither a finite variant of $S$, nor is $W$ not a superset of $S$. But if it is not the case that $W$ not a superset of $S$, then $W$ is a superset of $S$. So now we have the fact that $W \subseteq (\mathbb{N}-S)$ and $S \subseteq W$. Or in other words, $S \subseteq W \subseteq (\mathbb{N}-S)$, i.e., $S \subseteq (\mathbb{N}-S)$, which is a contradiction. Thus there is no infinite subset of $(\mathbb{N}-S)$ that is recursively enumerable.

So now all of the conditions have been met, so a maximal subset is simple.

---

For your second question, if $(\mathbb{N}-S)$ was finite, then $S$ wasn't coinfinite, and thus wasn't maximal to begin with, so we can't assume that $(\mathbb{N}-S)$ is finite.

Let me know if there is anything else I can clarify!