# Computably enumerable set is finite iff every computably enumerable subset is computable

I want to show that the property of a set being finite is lattice theoretic, i.e. definable in the first order language of the set $\mathcal{E}$ of computably enumerable (c.e) sets with set inclusion.

What I know: $\text{Comp}$ is lattice theoretic, where $\text{Comp}(X)$ holds if and only if $X$ is computable because $\text{Comp}(X) \Leftrightarrow (\exists Y)[X \cup Y = \omega \, \land \, X \cap Y = \emptyset]$ and $\emptyset, \omega, \cup, \cap$ are definable from $\subseteq$ in $\mathcal{E}$.

Now in https://pdfs.semanticscholar.org/70d9/83339041d96257d3a7cdcd5393418c64ed44.pdf on page 2 it says

Being finite is definable in $\mathcal{E}$. A set X is finite iff every subset of X is computable.

And I want to prove, that this is actually true. It is quite easy to see, that if $X$ is finite, every subset of $X$ is computable since every such subset is finite aswell. But how do I prove the converse? I want to prove, that:

If every c.e. subset $B$ of a c.e. set $X$ is computable then $X$ is finite.

Or stated in other words:

If $X$ is c.e. and $|X| = \infty$, then there exists some c.e. $B$ with $B \subseteq X$ and $B$ is uncomputable.

Could you help me with this? Thank you in advance.

• Doesn't this follow immediately from $2^{\mathbb N} > \mathbb N$ ? I think the fact that X is c.e. is irrelevant, all that matters is that it is infinite. I could be misunderstanding the question. – DanielV Sep 14 '18 at 7:09

Suppose $X$ is a c. e. infinite set. Then there is a computable bijection $f:\mathbb N\to X.$ Let $A$ be some uncomputable c.e. subset of $\mathbb N$ and let $B=f(A).$ Now show that $B$ is an uncomputable c.e. subset of $X.$