Infinite sets having no RE subsets

Question

I'm back trying to learn recursion theory on my own. I'd like to prove the following result: There exists an infinite set having no infinite R.E. subset. Constructive comments are appreciated.

Proof: To show the claim, we proceed by reductio. Suppose every infinite set has infinite R.E. subsets. WOLOG, let $Z$ = {$Z_0$, $Z_1$, . . .} be a countable collection of infinite sets. By hypothesis, for every $Z_i$ $\in$ $Z$ there is a $W_j$ such that $W_j$ $\subset$ $Z_i$, where j is the index of an R.E. set. Hence we can form a collection say $W$ = {$W_0$, $W_1$, . . .} of these R.E. sets. Note that every R.E. subset for the collection $Z$ is represented in $W$. We also note that R.E. sets are closed under arbitrary unions. Hence, we can take $\bigcup$$W$, which must be an R.E. set, and so is the R.E. subset for some member of $Z$. But all of these subsets were represented in $W$, since $W$ was assumed exhaustive. This latter fact contradicts our assumption that $W$ was exhaustive, so that there must be an infinite set with no R.E. subset after all.

Answer 1

For any fixed $S=\{s_1, s_2, \ldots \}$, the probability that all the $s_i$'s are in a random set is $\frac{1}{2} \times \frac{1}{2} \times \cdots =0$. Since probability is countably sub-additive, the probability that one of any fixed countable collection is a subset of a random set is 0. Thus most sets have no infinite c.e. subset.

Answer 2

You have an enumeration of the infinite r.e. sets. Let $m_0$ and $n_0$ be the two smallest elements of the first set, $m_1$ and $n_1$ the smallest elements of the second set different from $m_0$ and $n_0$, and so on. Then $\{m_k:k\in\omega\}$ does not contain any infinite r.e. set.

Added: Such sets are called immune. And as bof notes in the comments, the construction above has nothing to do with recursive enumerability; it’s just a handy way to construct an infinite set that doesn’t contain any member of a specified (sufficiently small) family of infinite sets.