Proving an infinite set not having any infinite decidable subsets is immune

188 Views Asked by At

Or, in other words, prove that an infinite set $S \subset \mathbb{N}$ that has no infinite decidable subsets also has no infinite enumerable subsets.

One idea I had is to show that the complement of $S$ has a non-empty intersection with any infinite enumerable set (kind of the reverse of how the existence of simple sets is proven), but since $S$ is not something we construct, I'm not sure how to proceed.

1

There are 1 best solutions below

0
On BEST ANSWER

Self-answering my second question on this branch of math.

I managed to prove that every enumerable set $S$ has a decidable subset (it's sufficient to show a monotonically increasing function defined via a computable function $f$ whose domain or codomain is $S$). The result immediately follows.