2
$\begingroup$

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.

$\endgroup$
1
  • 1
    $\begingroup$ 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. $\endgroup$ – DanielV Sep 14 '18 at 7:09
1
$\begingroup$

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.$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.