# Help on two exercises about computability theory

In Cooper's book, I can't think out the solutions of two exercises.

1.show that there exists a simple set S contains the set of all even numbers.

2.show that each creative set is contained in some simple set.

By the way,they are not homework question.

I read the book on my own and I am a beginner. Thanks for your hint.

-
For (1) you could probably take a known simple set $A$, and define $B = \{ 2n+1 : n \in A \} \cup \{ 2n : n \in \mathbb{N} \}$. –  Arthur Fischer Feb 22 '12 at 18:47
Thank you very much. My question may be too simple, Your answer is really helpful since I am a autodidact and a beginner in this area. –  user25494 Feb 23 '12 at 18:24
You questions are clearly not too simple. First of all, I don't think there is such a thing as a "too simple" question around here, and, secondly, I couldn't figure out an answer to the second one. I hope that Alex's answer/hint below is helpful. Cheers! –  Arthur Fischer Feb 24 '12 at 7:48

## 1 Answer

1. Arthur's hint probably works, but I haven't worked out how to show that the set of odd elements in any infinite computably enumerable set intersects $\{2n+1:n\in A\}$. However, it is probably simpler to show that there exists a simple set $A$ such that $A$ contains infinitely many odd numbers, and take $A\cup \{2n:n\in\mathbb N\}$.

2. To show that all creative sets are contained in some simple set, make use of the productive function associated with the compliment. In short, we can find sets that are contained in the compliment by using the productive function, and add some element from this set to our creative set. For example, if we have a creative set $C$ and find that $f(x)$ converges (which will happen if $W_x\subseteq \bar{C}$, we can put add some elements from $W_x$ into $\bar{C}$. Can you think of a way to do this without making the result cofinite?

-
Just to clear up my thinking about (1): if $X$ is an infinite r.e. subset of the complement of $\{ 2n+1 : n \in A \} \cup \{ 2n : n \in \mathbb{N} \}$, then $\{ n \in \mathbb{N} : 2n+1 \in X \}$ should be an infinite r.e. subset of $\overline{A}$, which we know is impossible. –  Arthur Fischer Feb 24 '12 at 8:53
@ArthurFischer Nice, that's very succinct! –  Alex Becker Feb 24 '12 at 9:04