# Sets that are not $\infty$-Borel

I have seen a few techinques for proving that certain sets of real numbers are $\infty$-Borel (definition) but it just occurred to me that I don't know of any way to prove that a set of real numbers is not $\infty$-Borel.

I'm afraid this may turn out to be a silly question, but here goes: can non-$\infty$-Borel sets exist? If $\mathsf{AC}$ holds then every set of reals is trivially $\infty$-Borel, and if $\mathsf{AD}$ holds then it is an open question whether every set of reals is $\infty$-Borel. So to get a non-$\infty$-Borel set we may need to look in some weirder model.

Here we say that a set is $\infty$-Borel if it has an $\infty$-Borel code—an object that describes how the set is built up from open sets via the operations of complementation and well-ordered union. Such a code is essentially a set of ordinals $S$. An equivalent definition is that a set $A$ is $\infty$-Borel if there is a set of ordinals $S$, an ordinal $\alpha > \sup(S)$, and a formula $\varphi$ such that for every real $x$ we have $x \in A \iff L_\alpha[S,x] \models \varphi[S,x]$.

In the linked Wikipedia article as well as in other places, I have seen a discussion of the potential difference between the class of $\infty$-Borel sets and the class of sets generated from the open sets under the operations of complementation and well-ordered union. The observation is that it's not clear whether, without $\mathsf{AC}$, we can choose $\infty$-Borel codes for $\infty$-Borel sets in a sequence, even if each set in the sequence has such a code.

However, I do not recall ever seeing a proof of the consistency of

1. $\mathsf{ZF} + {}$"the class of $\infty$-Borel sets is not closed under wellordered union," or even of

2. $\mathsf{ZF} + {}$"some set of reals is not $\infty$-Borel."

Assuming that (2) is consistent, I would like to see a proof of this. Or if the stronger theory (1) is consistent, a proof of this would be even better.

If $\mathbb{R}$ is a union of countably many countable sets, then every set of reals is generated from the open sets under the operations of complementation and well-ordered (countable) union. In this case (1) and (2) are equivalent. Perhaps they are both true in this case?

• Hi Trevor. You really need to discuss the definition here, as there is always the issue of whether you are just looking at algebras or sets, or working instead with codes (which I think should really be what one does), and the answers may differ. For instance, there is no code witnessing that $\mathbb R$ is a countable union of countable unions of singletons. – Andrés E. Caicedo Apr 17 '14 at 2:09
• @Andres Good point. I assumed that the Wikipedia article made it clear, but it doesn't quite do so in the beginning. – Trevor Wilson Apr 17 '14 at 2:11
• @Andres Is it obvious that there is no such code? – Trevor Wilson Apr 17 '14 at 2:16
• It is not obvious, but it is true. The thing is, one can actually develop a poor-man's $\mathsf{ZF}$ version of Lebesgue measure for Borel sets in the codes, so even in the Feferman-Levy model we can carry out some measure theory. Fremlin discusses this in detail in his book. I do not see why this answers the question, though. And, anyway, if it does, then we are still left with the non-effective version. – Andrés E. Caicedo Apr 17 '14 at 2:19
• @Trevor: So $\infty$-Borel are sets which have codes? – Asaf Karagila Apr 17 '14 at 2:23

Henle, Mathias and Woodin showed that if every set of reals is Ramsey, then forcing with $\mathcal{P}(\omega)/\mathrm{Fin}$ adds no new sets of ordinals. Any new set of reals in the extension (e.g., the ultrafilter given by the generic filter) would fail to be $\infty$-Borel in the extension. So I suppose that answers (2). I don't know about (1).

• The forcing also adds no functions from the ordinals to the ground model. So the extension won't be a counterexample to (1), unless the ground model is. – Paul Larson Jul 14 '14 at 13:09
• I believe that Trevor and I have worked out an answer to (1). Add infinitely many Cohen reals over $L$, with finite support. Now consider $L(A, S)$, where $A$ is the set of reals $E_0$-equivalent to one of the generic reals, and $S$ is the $\omega$-sequence of $E_0$-degrees. If you want to have DC as well, add $\omega_1$ many Cohen reals instead, and take $L(R, S)$, where $R$ is the set of all reals from the forcing extension, and $S$ is as before, with the corresponding sequence. Rumour has it that Woodin has constructed a similar example. – Paul Larson Mar 4 '16 at 20:14

This is a nice question Trevor. This is not an answer but it is a bit too long for a comment. If we assume that every set is $\infty$-Borel (say we're just assuming $AD^+$), then there is no proper ($\subsetneq \mathcal{P}(\mathbb{R}))$ pointclass $\boldsymbol\Delta$ closed under complements, arbitrary length unions and intersections. So if we can find a selfdual pointclass closed under complements, arbitrary length unions and intersections then there exists a set which is not $\infty$-Borel.

I don't think this can follow from just $AD$ (not really sure about this though, it is still possible), because all selfdual pointclasses $\boldsymbol\Delta$ are closed under unions of length strictly less than $\delta(\boldsymbol\Gamma)$ for $\boldsymbol\Gamma$ closed under $\forall^{\mathbb{R}}$, conjunctions, disjunctions and such that $PWO(\boldsymbol\Gamma)$ holds and $\boldsymbol\Delta=\boldsymbol\Gamma \cap \boldsymbol{\check\Gamma}$. In general, if $\boldsymbol\Gamma$ is non-selfdual, closed under $\forall^{\mathbb{R}}$ with $PWO(\boldsymbol\Gamma)$ and $\boldsymbol\Delta$ is closed under real quatification, then for $\kappa=o(\boldsymbol\Delta)$, $\boldsymbol\Delta$ is closed under union of length strictly less than $cof(\kappa)$. But the set of $o(\boldsymbol\Delta)$ for $\boldsymbol\Delta$ satisfying these assumptions is cofinal in $\Theta$, these are the places where we are at the base of a Type II or Type III projective -like hierarchy. Maybe if we reach a pointclass $\Lambda$ closed under complements and arbitrary length unions and intersections that set of such $o(\boldsymbol\Delta)$ would be bounded (pure speculation/conjecture)

As an aside there is another nice characterization of $\infty$-Borel sets: a set $X$ is $\infty$-Borel if there is a tree $T$ on $\omega \times \lambda$ such that $x\in X$ holds iff Player I wins the games $G$ where Player I and II play a branch $f\in \lambda^{\omega}$ and the playoff is Player I wins iff $(x,f)\in [T]$. The tree $T$ is the code for the set $X$.

• I'm not sure if your first paragraph is valid in full generality: it seems like you need a way to choose codes for $\infty$-Borel sets in your well-ordered union. If you assume $\mathsf{AD}^+$ then every $\text{OD}$ set has a $\text{OD}$ $\infty$-Borel code, and if you can relativize this fact to the sequence, then I think you can use it to pick codes. Also, are you saying that you think $\mathsf{AD} + {}$"not every set of reals is $\infty$-Borel" is consistent? I hope that's not the only way to solve this problem, or this question might be in the "unanswered" queue for a while :-) – Trevor Wilson May 13 '14 at 2:50
• I should clarify the first paragraph. The pointclass $\boldsymbol\Delta$ in the 1st paragraph is $\boldsymbol B_{\infty}$, the $\infty$-Borel sets. So we know assuming $AD^+$ (or $AD + V=L(\mathbb{R})$) that $\boldsymbol B_{\infty}=\mathcal{P}(\mathbb{R})$. So what I believe (and I don't have any good argument for it) is that the conclusion should follow just from $AD$ because of there are cofinally many of these $\boldsymbol\Delta$ pointclasses as in the 2nd paragraph in the Wadge Hierarchy under $AD$. So I believe $AD$+"not every set of reals is $\infty$-Borel" should be inconsistent. – 16278263789 May 13 '14 at 19:58
• Aside from the fact above about the pointclasses $\boldsymbol\Delta$ at the base of a projective-like hierarchy (and I don't know if it is really relevant to the problem), I don't know if $AD$+"not every set of reals is $\infty$-Borel" could be consistent. This could possibly still hold after all. – 16278263789 May 13 '14 at 20:03
• Oh, I see, I was confused regarding your first paragraph, which essentially says that if every set of reals is $\infty$-Borel, then every set of reals is generated from open sets under the operations of complementation and well-ordered unions and intersections. I misread it as the converse for some reason. – Trevor Wilson May 13 '14 at 20:12
• Say we consider $AD_{\mathbb{R}}$. Then assuming $AD^+$, $AD_{\mathbb{R}}$ is equivalent to " Every set of reals is Suslin". A set of reals $X$ has a strong $\infty$-Borel code iff $X$ is Suslin. Is there anything known about the consistency strength of $ZF+AD^+ +\neg AD_{\mathbb{R}}$? – 16278263789 May 13 '14 at 21:58