I am taking a course on recursion theory, and have the following problem:
Prove that there are $\Sigma_1$ subsets $A, B$ of $\mathbb{N}\times \mathbb{N}$ which cannot be separated by a $\Sigma_1$ set. Prove the same for subsets of $\mathbb{N}$, and conclude that $\Sigma_1$ does not have the separation property.
The second part is more clear to me, but I'm unable to prove the first sentence. I was given the following hint for the first part:
Let $W^2_e$ be the domain of $\{e\}_2$, the $e$-th binary recursive function, so that the $W^2_e$ enumerate the $\Sigma_1$ subsets of $\mathbb{N}\times\mathbb{N}$. Think of a pair $\langle e,f\rangle$ is coding sets $A′ = W_e^2$ and $B′ = W_f^2$ and decide whether this pair should go in $A$ or in $B$ in a way that would prevent $A′, B′$ from separating $A, B.$
I'm assuming I should use uniformization, but it's not very clear to me how I should do so, even with the hint. Any guidance would be much appreciated.
For context,
The separation property for a collection $\Gamma$ of sets states that for any two disjoint sets $A, B$ in $\Gamma$, there are $A^{\prime}, B^{\prime} \in \Gamma$ so that $A^{\prime} \supseteq A, B^{\prime} \supseteq B, A^{\prime}, B^{\prime}$ are disjoint, and $A^{\prime} \cup B^{\prime}$ is the entire space. $A^{\prime}, B^{\prime}$ are then said to separate $A, B$.
And
(Uniformization) If $A \subseteq \mathbb{N}^2$ is recursively enumerable, then there is a (partial) recursive function $f$ so that $x \in \operatorname{dom}(f) \Longleftrightarrow \exists y(x, y) \in A$, and $(x, f(x)) \in A$ for all $x \in \operatorname{dom}(f)$.
For posterity's sake, I've figured it out. It was actually extremely simple and analogous to the proof for $\Sigma_1$ separation failing for subsets of $\mathbb{N}$.
Let $$A=\{(e,f)\mid \{f\}^2(e,f)\downarrow\}\qquad B=\{(e,f)\mid \{e\}^2(e,f)\downarrow\}$$ both subsets of $\mathbb{N}\times\mathbb{N}.$ Clearly both $\Sigma_1.$
Suppose $A',B'\subset\mathbb{N}\times\mathbb{N}$ are $\Sigma_1$ sets separating $A,B,$ i.e $A\subset A',B\subset B'$, $A'\cap B'=\emptyset,$ and $A'\cup B'=\mathbb{N}\times\mathbb{N}.$ Since they are $\Sigma_1,$ we have $e,f$ so that $A'=W_e^2$ and $B'=W_f^2.$
Then we know $(e,f)$ is either in $A'$ or $B'.$
If $(e,f)\in A'=W_e^2,$ then $$\{e\}^2(e,f)\downarrow\implies (e,f)\in B\subset B'$$ If $(e,f)\in B'=W_f^2,$ then $\{f\}(e,f)\downarrow\implies (e,f)\in A\subset A'$.
Thus in either case, $(e,f)\in A'\cap B',$ a contradiction. So $A,B$ cannot be separated.