Is a countable infinite union of $\Sigma_1$ sets is $\Sigma_1$?

243 Views Asked by At

I’m reading Kunen’s book Foundations of mathematics. My question is whether a countable union of $\Sigma_1$ sets in $HF$ is also $\Sigma_1$ or not. I wonder if we can think $\Sigma_1$ sets as open sets in HF.

1

There are 1 best solutions below

6
On BEST ANSWER

$\Sigma_1$ subsets of $\mathit{HF}$ are the recursively enumerable ones, as you might have read in Kunen's book. The intuition of being “open” sets is not completely incorrect, if you consider them effectively open.

With this in mind, it can be concluded that the union of an effectively enumerated family of $\Sigma_1$ sets is again $\Sigma_1$. But, following Andreas' comment above, any subset of $\omega$ can be obtained a countable union of $\Sigma_1$ sets; and there are indeed such sets that are not $\Sigma_1$— for instance, the set of (codes for) non halting Turing machines.