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?

  • $\begingroup$ 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. $\endgroup$ Apr 17, 2014 at 2:09
  • $\begingroup$ @Andres Good point. I assumed that the Wikipedia article made it clear, but it doesn't quite do so in the beginning. $\endgroup$ Apr 17, 2014 at 2:11
  • $\begingroup$ @Andres Is it obvious that there is no such code? $\endgroup$ Apr 17, 2014 at 2:16
  • 1
    $\begingroup$ 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. $\endgroup$ Apr 17, 2014 at 2:19
  • $\begingroup$ @Trevor: So $\infty$-Borel are sets which have codes? $\endgroup$
    – Asaf Karagila
    Apr 17, 2014 at 2:23

2 Answers 2


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).

  • 1
    $\begingroup$ 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. $\endgroup$ Jul 14, 2014 at 13:09
  • 1
    $\begingroup$ 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. $\endgroup$ Mar 4, 2016 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$.

  • $\begingroup$ 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 :-) $\endgroup$ May 13, 2014 at 2:50
  • $\begingroup$ 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. $\endgroup$ May 13, 2014 at 19:58
  • $\begingroup$ 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. $\endgroup$ May 13, 2014 at 20:03
  • $\begingroup$ 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. $\endgroup$ May 13, 2014 at 20:12
  • $\begingroup$ 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}}$? $\endgroup$ May 13, 2014 at 21:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.