Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

In Cooper's book, I can't think out the solutions of two exercises. that there exists a simple set S contains the set of all even numbers. 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.

share|cite|improve this question
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} \}$. – arjafi 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
  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?

share|cite|improve this answer
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. – arjafi Feb 24 '12 at 8:53
@ArthurFischer Nice, that's very succinct! – Alex Becker Feb 24 '12 at 9:04

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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