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

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

$\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?

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$ – Andrés E. Caicedo Apr 17 '14 at 2:194more comments