2
$\begingroup$

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.

  • 1
    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} \}$.2012-02-22
  • 0
    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.2012-02-23

1 Answers 1

1
  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?

  • 0
    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.2012-02-24
  • 0
    @ArthurFischer Nice, that's very succinct!2012-02-24
  • 0
    @AlexBecker Sorry to bring up an old question, but what if I took $A$ to be a simple set s.t. $\text{Odd}⊆A$? Then wouldn't your suggestion for (1) not work? The answer says "it is probably simpler to show that there exists a simple set $A$ s.t. $A$ contains infinitely many odd numbers, and take $A\cup {2n : n \in \mathbb{N}}$" but if $A$ contains all the odds, then the union will be $\mathbb{N}$ which is no longer a simple set.2017-05-08
  • 0
    @arjafi I know this is not your answer, but your comment to Alex seems to suggest you understand it, even though the reasoning in your comment seems to be fleshing out your suggestion to solving the question as opposed to Alex's approach. Are my concerns for Alex's answer unfounded?2017-05-08
  • 0
    @gowrath It's been a while since I've looked at this, but your concern seems to be right on.2017-05-13