Every infinite c.e. set has an infinite computable subset
7 May 2024
I initially solved this by taking the complement and proving the equivalent statement that every co-c.e. set whose complement is infinite has an infinite computable superset.
Broadly, the idea is to dovetail against each number with a twist. Since our set is co-c.e., we have a partial decider for whether a number is not in our set. We dovetail using this while also counting steps and an “upper-bound” for termination. After computation on a number of terminates, we reject this number as it is clearly not in our co-c.e. set, take note of the number of computation steps it has completed and accept the next number that doesn’t terminate within this number of steps.
This solution is convoluted though and we can do it by fixing a computable enumeration of our c.e. set and considering all numbers \(f(n)\) that satisfy \(f(n) > f(m)\) for all \(m < n\) which is much simpler.