There is a $\Sigma^1_1$ universal set and this is not Borel. Where did we use the axiom of choice?

Question

It is well-known that there is a $\boldsymbol{\Sigma}^1_1$ universal set $U \subset \omega^\omega \times \omega^\omega$. That is, there is a $\boldsymbol{\Sigma}^1_1$ subset $U$ of $\omega^\omega \times \omega^\omega$ that satisfies the following condition: For every $\boldsymbol{\Sigma}^1_1$ subset $A$ of $\omega^\omega$, there exists a $x \in \omega^\omega$ such that $$ A = U_x = \{ y \in \omega^\omega : (x, y) \in U \}. $$

(For a proof, see Moschovakis' "Descriptive Set Theory" Theorem 1D.1, 1D.2, 1D.3.)

And, by a diagonal argument, the following statement holds: If $U$ is $\boldsymbol{\Sigma}^1_1$ universal set, then $P = \{x \in \omega^\omega : (x, x) \in U \}$ is $\boldsymbol{\Sigma}^1_1$ but not $\boldsymbol{\Pi}^1_1$.

Thus, $P$ is not Borel set since a set is Borel iff it is $\boldsymbol{\Sigma}^1_1$ and $\boldsymbol{\Pi}^1_1$.

By the way, in ZF (the set theory without the axiom of choice), there is a possibility that every set of reals is Borel.

Therefore, the above argument needs the axiom of choice. Where did we use the axiom of choice?

Answer 1

There are two notions of "Borel set" which coincide assuming choice but do not in $\mathsf{ZF}$ alone. The issue isn't with the argument itself, but rather how we phrase its conclusion.

The terminology below is mine. Annoyingly in my opinion, in the choiceless context "Borel" tends to be used for "barely Borel." I'm not sure what "explicitly Borel" sets are officially called, but I've heard "coded Borel" in conversation.

---

The simplest notion of Borel set is simply "Element of the smallest $\sigma$-algebra containing the open sets." Call these sets barely Borel.

On the other hand, you have the sets which have Borel codes: that is, well-founded appropriately-labelled subtrees of $\omega^{<\omega}$ telling us exactly how the set in question is built out of open sets via countable unions, countable intersections, and complements. Call these the explicitly Borel sets.

When we take the usual argument that there is a non-Borel set and run it through in $\mathsf{ZF}$, what we actually wind up proving is:

$\mathsf{ZF}$ $\vdash$ "There is a non-explicitly Borel set of reals."

In fact, this doesn't require complex machinery at all: there is an obvious surjection from $\mathbb{R}$ to the set of barely Borel sets (send each real to the explicitly Borel set it codes, or to $\emptyset$ if it codes no such set) and we can directly diagonalize against this to produce a non-explicitly Borel set. The more intricate argument establishes:

$\mathsf{ZF}$ $\vdash$ "The set of codes for ill-founded subtrees of $\omega^{<\omega}$ is ${\bf\Sigma^1_1}$ but not explicitly Borel."

This is perfectly consistent with:

$\mathsf{ZF}$ $\not\vdash$ "There is a non-barely Borel set of reals"

because in ZF the explicitly Borel sets need not form a $\sigma$-algebra.

---

As an aside, note that this situation in fact "localizes" (as Asaf Karagila's answer says): we also have notions of explicitly/barely $\bf \Pi^0_\alpha$/$\bf \Sigma^0_\alpha$/$\bf \Delta^0_\alpha$ sets, and they behave differently. And in principle we can go even further. For example, we could consider the sets which are explicit $\omega$-unions of barely $\bf \Pi^0_{17}$ sets, and it's not clear to me how this interacts with the more "homogeneously defined" pointclasses in $\mathsf{ZF}$ alone.

Answer 2

The problem starts a lot sooner than that.

Working in $\sf ZFC$ we can easily show that $\boldsymbol{\Sigma}^0_n$ is closed under countable unions, and likewise $\boldsymbol{\Pi}^0_n$ is closed under countable intersections.

This is not true anymore in $\sf ZF$. Exactly in these models where all sets are Borel. For example, if the real numbers are a countable union of countable sets, then $\boldsymbol{\Sigma}^0_2$ is not closed under countable unions anymore.

So the problem is not with the proof of this theorem, but rather with the whole machinery. It just collapses down on itself.