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

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?

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.

• I think it is cool. Apr 22, 2020 at 17:26
• As an aside, there's an interesting "inversion" occurring in the computability-theoretic side of things, with respect to the two main definitions of hyperarithmetic (there are many others). Call a set "barely hyperarithmetic" if it is $\Delta_1^1$, and "explicitly hyperarithmetic" if it is computable from $\emptyset^{(\alpha)}$ for some computable $\alpha$. These notions wind up coinciding, and to a certain extent they behave like the analogues of barely Borel and explicitly Borel, respectively. Apr 22, 2020 at 17:33
• However, there is a sense in which the former definition is more restrictive! In the context of reverse mathematics, $\mathsf{ATR_0}$ (asserting that explicitly hyperarithmetic sets exist) is strictly stronger than $\Delta^1_1$-$\mathsf{CA_0}$ (asserting that barely hyperarithmetic sets exist). The issue is that the proof that every set of the latter type is also of the former type relies on $\mathsf{ATR_0}$ in the first place, whereas the proof of the other inclusion - while conceptually more complicated - has less axiomatic overhead. Apr 22, 2020 at 17:33
• Didn't we already have a discussion about Bairely Borel, and Berenstein Baires? Apr 22, 2020 at 17:47
• I'd say it's more than just fair. It's practically necessary. Apr 22, 2020 at 17:52

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.