On page 33 and 34 of Soare's Recursively Enumerable Sets and Degrees he defined the recursive enumeration of an r.e. set $A$ to be a strong array of finite sets $\{ A_s \}_{s \in \omega}$ such that $$\forall s, \ A_s \subseteq A_{s+1}$$ and $$A = \bigcup A_s$$ where a strong array of finite sets is a family $\{D_{f(x)}\}_{x \in \omega}$ such that f is total recursive and $e = 2^{x_1}+...+2^{x_n}$ is the canonical index of the finite set $D_e = \{ x_1, ... ,x_n \}$
At first I thought what Soare meant by that is $\{ A_s \}$ is just a family of increasing finite sets that's also a cover for $A$ such that it can be put in the form of $\{D_{f(x)} \}$, but then he asked the reader to show given enumerations $\{ X_s \}$ and $\{ Y_s \}$ for r.e. sets $X$ and $Y$, the set$$ X \setminus Y = \{z \ \mid \exists s[z \in X_s - Y_s]\} $$is r.e.. For some reason my intuition tells me that's not possible (forgive me if I'm being dumb here), but I can neither disapprove or prove that thought yet. But then I saw a second way to interpret what he meant that makes the excersize trivial:$\{ A_s \}$ is a strong array means there's some total recursive f s.t. $D_{f(s)} = A_s$ (all of the examples he's given so far fits that definition).
What's actually going on here? Am I being dumb as usual or did I misunderstood Soare the first time? (I guess I'm really asking a hint or an answer to his excersize, since I doubt I misunderstood his definition. I'll change the title accordingly once I've gotten or arrived at an answer)
$\endgroup$ 2 Reset to default
