Exists two recursively enumerable sets satisfying conditions?

66 Views Asked by At

Do there exist two recursively enumerable sets $X$, $Y$ such that $X \subseteq Y$ and:

(a) $X$ is creative while $Y$ is simple;

(b) $X$ is simple while $Y$ is creative?

1

There are 1 best solutions below

0
On BEST ANSWER

(a) Yes. Let $A$ be a creative subset of $\mathbb N$ and let $B$ be a simple subset of $\mathbb N.$ Let $X=\{2n:n\in A\}$ and let $Y=\{2n:n\in\mathbb N\}\cup\{2n+1:n\in B\}.$ Then $X$ is creative and $Y$ is simple and $X\subseteq Y.$

(b) No. It is clear from the definition that a recursively enumerable superset of a simple set is either simple or cofinite.