Complexity of index sets in nonprincipal ultrafilters Let $U$ be a nonprincipal ultrafilter on $\omega$. It can be shown that the set $I = \{e \mid W_e \in U\}$ (where $W_e$ is the $e$th r.e. set in some given enumeration) cannot be $\Delta_2^0$ (in fact, it's at least $\Pi_2^0$-hard). Now I wish to show that there is a nonprincipal ultrafilter $U$ such that $I$ is $\Delta_3^0$. 
I'm not sure how such a construction should go. I tried constructing such an ultrafilter by creating a chain of sets that at each stage would guarantee the union is an ultrafilter with the desired properties, but nothing I did quite worked out. Any help would be much appreciated!
 A: I propose to first build a suitable ultrafilter in the Boolean algebra generated by the r.e. sets and then extend it to the Boolean algebra of all subsets of $\omega$.  Only the first part of this is relevant to your question; the second part is automatic since, quite generally, one can extend, to any given Boolean algebra, any ultrafilter in any Boolean subalgebra.  So here goes the first part.  
I'll build a decreasing $\omega$-sequence of infinite r.e. sets, $A_0\supseteq A_1\supseteq\dots$.  The intention is that, at stage $n$, the ultrafilter under construction is known to contain $A_n$ and all sets that include it modulo finite.  I start with $A_0=\omega$.  In the step from $A_n$ to $A_{n+1}$, I want to decide whether the $n$-th r.e. set $W_n$ is in my ultarafilter or not.  If $W_n$ is almost disjoint from $A_n$, then the decision has already been made, negatively, so I don't need to do anything; more precisely , I define $A_{n+1}$ to be $A_n$.  If, on the other hand, $W_n\cap A_n$ is infinite, then I put $W_n$ into my ultrafilter by setting $A_{n+1}=W_n\cap A_n$.
That completes the construction of the ultrafilter in the Boolean algebra generated by the r.e. sets.  (Note that, by making decisions about all r.e. sets, I have automatically also made decisions about all their Boolean combinations.)  Now what is the complexity of my construction?
At each step, I must decide whether a certain r.e. set $W_n\cap A_n$ is infinite.  That is a $\Pi^0_2$ question: "For every $k$, there exists a computation witnessing that some integer $>k$ is in $W_n\cap A_n$."  So an oracle for $0''$ suffices to answer this question and thus to carry out my whole computation.  
Therefore, the set of $n$ such that $W_n$ is in my ultrafilter, which is also the set of $n$ such that the decision in going from $A_n$ to $A_{n+1}$ was affirmative, is recursive in $0''$.  That is, it is $\Delta^0_3$.
