1

I'm trying to do exercise X.2.16 from Soare's Recursively Enumerable Sets and Degrees, but I have no idea how ro solve it. Any hints would be appreciated.

An infinite set is strongly hh-immune or ssh-immune if there is no uniformly r.e. sequence $\{ W_{f(n)} \}_{n\in \omega}$ of pairwise disjoint r.e. sets such that $W_{f(n)} \cap B \neq \emptyset$ for every $n$.

A set $C$ is hh-immune if there is no uniformly r.e. sequence $\{ W_{f(n)} \}_{n\in \omega}$ of pairwise disjoint finite sets such that $W_{f(n)} \cap C \neq \emptyset$ for every $n$.

Prove that if $A$ is a coinfinite r.e. set, then $\overline{A}$ is hh-immune if and only if $\overline{A}$ is shh-immune.

Leo163
  • 2,647

1 Answers1

1

ssh implies hh (no sequence of sets implies no sequence of finite sets)

The equivalence is only true because $A$ is r.e. Try to suppose that $\overline{A}$ is not ssh-immune. Then there is a re sequence of sets. Try to build a sequence of finite sets from them, by taking (recursively) only a finite subset of each one.

A re set is the image of some recursive partial function.

Note that when you enumerate a r.e set $S$, each time you output a new element of the set, you can verify if the previous elements are in $A$ (because $A$ is re). If they are not (your search never end), stop your output (by not halting, this is convenient). Hence your output image is finite (if $S\cap\overline{A}\neq\emptyset$ or $S$ finite) and contains exactly one element of $S\cap \overline{A}$.

Xoff
  • 10,310