# Non-Borel sets without axiom of choice

This is a simple doubt of mine about the basics of measure theory, which should be easy for the logicians to answer. The example I know of non Borel sets would be a Hamel basis, which needs axiom of choice, and examples of non Lebesgue measurable set would be Vitali sets, which seems to be unprovable without axiom of choice. Then I saw the answer of François G. Dorais. His construction of an uncountable $\mathbb{Q}$-independent set in $\mathbb R$ does not require axiom of choice. Which leaves a faint hope for the following:

Is it possible to construct without using the axiom of choice examples of non Borel sets?

There is a classic example of an analytic but non-Borel set due to Lusin, described by Gerald Edgar here, but it is not clear to me whether it needs axiom of choice since it seems to be putting restrictions on higher and higher terms in the continued fraction expansion. Since I do not know logic and set theory, I hoped of asking the experts.

-

No, it is not possible. It is consistent with ZF without choice that

the reals are the countable union of countable sets. (*)

From this it follows that all sets of reals are Borel. Of course, the "axiom" (*) makes it impossible to do any analysis. As soon as one allows the bit of choice that it is typically used to set up classical analysis as one is used to (mostly countable choice, but DC seems needed for Radon-Nikodym), one can implement the arguments needed to show

(**) The usual hierarchy of Borel sets (obtained by first taking open sets, then complements, then countable unions of these, then complements, etc) does not terminate before stage $\omega_1$ (this is a kind of diagonal argument).

Logicians call the sets obtained this way $\Delta^1_1$. They are in general a subcollection of the Borel sets. To show that they are all the Borel sets requires a bit of choice (One needs that $\omega_1$ is regular).

There is actually a nice result of Suslin relevant here. He proved that the Borel sets are precisely the $\Delta^1_1$ sets: These are the sets that are simultaneously the continuous image of a Borel set ($\Sigma^1_1$ sets), and the complement of such a set ($\Pi^1_1$ sets).

That there are $\Pi^1_1$ sets that are not $\Delta^1_1$ (and therefore, via a bit of choice, not Borel) is again a result of Suslin. He also showed that any $\Sigma^1_1$ set is either countable, or contains a copy of Cantor's set and therefore has the same size as the reals. His example of a $\Sigma^1_1$ not $\Delta^1_1$ set uses logic (a bit of effective descriptive set theory), and nowadays is more common to use the example of the $\Pi^1_1$ set WO mentioned by Joel, which is not $\Delta^1_1$ by what logicians call a boundedness argument.

A nice reference for some of these issues is the book Mansfield-Weitkamp, Recursive Aspects of Descriptive Set Theory, Oxford University Press, Oxford (1985).

-
You are right! – Joel David Hamkins Jul 21 '10 at 10:09
@Anweshi: Yes; but that's OK! The reals are still uncountable, and François' construction gives a $|\mathbb{R}|$-sized $\mathbb{Q}$-independent subset. The trick is that without AC, “countable union of countable sets” doesn't imply countable! (To get a counting of the union, you need to a choice of counting of each set in the union.) – Peter LeFanu Lumsdaine Jul 21 '10 at 11:09
Andres, I think you don't need any AC to get a complete analytic set, right? This just uses a $\Sigma_1$ truth definition. And these sets cannot be $\Delta^1_1$ by diagonalization. But the issue is that we don't know that $\Delta^1_1=$ Borel without $AC_\omega$, since it may not be a $\sigma$-algebra, if we are unable to make countable choices. – Joel David Hamkins Jul 21 '10 at 11:49
@Peter. The result that the reals can be a countable union of countable sets is due to Feferman and Levy (1963). One place to see a proof is in Jech's book The Axiom of Choice, p.142. – John Stillwell Jul 21 '10 at 12:33
@DK No, it doesn't. It just means that any proof that the set is not Borel uses some amount of choice. (Usually, a really small amount.) For example, define $\mathsf{WO}$ as follows: You can use the decimal expansion of a real $x$ to code a subset of $\mathbb N\times \mathbb N$, there are several standard ways of doing this; now put $x\in\mathsf{WO}$ iff the subset that is coded is a well-ordering. This set is not Borel, but the proofs require choice. In the models I discuss in the answer, $\mathsf{WO}$ is Borel, but essentially by accident. – Andrés Caicedo Oct 11 '13 at 12:39

If you assume the countable axiom of choice, then most sets of reals are not Borel. Under AC, what you get is that there are continuum many Borel sets, that is, $2^{\aleph_0}$ many, but $2^{2^{\aleph_0}}$ many sets of reals, so most sets of reals are not Borel. Under countable choice $AC_\omega$, what we have is a surjection from the reals onto the Borel sets, and this is still enough to conclude that most sets of reals are not Borel.

To see that there are only continuum many Borel sets, one can think about how the Borel sets are constructed. We begin with the basic open sets, of which there are countably many, and then systematically close under countable unions, intersections and complements. It follows that the Borel sets are constructed in a hierarchy of length $\omega_1$, and that every Borel set has a construction template, known as a Borel code, that details exactly how it was constructed from the basic open sets. One can think of the Borel code as a well-founded countable tree, whose leaves are labeled with basic open sets and whose other nodes are labeled with union, intersection and complement, meaning that this is the operation to be applied to the children node in order to know which set is coded at the parent node. Every such tree is a countable object, coded by a real.

Under $AC_\omega$, the collection of sets of reals coded by such Borel codes is a $\sigma$-algebra containing all open sets, and the smallest such, so it is exactly the collection of Borel sets. The proof that it is a $\sigma$-algebra uses $AC_\omega$, becasue when we have a countable family of Borel sets, to make the code for their union, we can simply glue together Borel codes for each of them, provided we can choose representing Borel codes. Thus, under $AC_\omega$, we can map the reals onto the set of Borel sets. But by Cantor's theorem, we cannot map the reals onto the power set of the reals, and so in this sense, most sets of reals are not Borel.

Under $AC_\omega$, one can also give concrete examples of sets that are not Borel. For example, the set of reals known as WO is the set of reals that code a binary relation on the natural numbers that is a well order. This is a complete $\Pi^1_1$ set, and cannot be Borel.

To explain a bit more: if I have a relation $R$ on the natural numbers for which $\langle\mathbb{N},R\rangle$ is a well order, then I can code this relation $R$ as a single binary sequence, by placing a $1$ in the $2^n3^m$ digit exactly if $nRm$. The set of such sequences coding such well-orders has complexity $\Pi^1_1$, since to be a well-order means that it is a linear order (which is easy to express using only natural number quantifiers) plus the assertion that every subset has a minimal element (which is the universal quantifier over reals). But more, it is complete $\Pi^1_1$, which means that every $\Pi^1_1$ set reduces to WO. But (under $AC_\omega$) the Borel sets are exactly the $\Delta^1_1$ sets, which are the sets that are both $\Pi^1_1$ and $\Sigma^1_1$, meaning that their complement is $\Pi^1_1$.

Basically, any set that is defined using well-foundedness will essentially involve $\Pi^1_1$ and WO, and take you out of the Borel context. The set of all well-founded countable trees, the set of well-founded countable relations, the set of well-orders, and so on are all complete $\Pi^1_1$ sets, and therefore not Borel.

One can similarly work on the analytic side, to come up with $\Sigma^1_1$ examples. There is a universal $\Sigma^1_1$ set, an analytic subset of the plane whose slices are all analytic sets, and such a set cannot be Borel, under $AC_\omega$, since if it were, I could flip the values on the diagonal and produce an analytic set that is not a slice.

-
Oops ... Of course I knew the cardinality argument. What I had in mind was concrete examples. Could you elaborate on that part a bit? I must confess I didn't understand the last two phrases. – Anweshi Jul 21 '10 at 0:33
I edited the question to reflect this. I hope you don't mind it. – Anweshi Jul 21 '10 at 0:35
Oh, I am sorry again. The part I didn't understand was not the Cardinality argument. It was the statement"....well order is a complete $\Pi_1^1$ set, and cannot be Borel.". Here I missed what is $\Pi_1^1$. – Anweshi Jul 21 '10 at 0:44
$\Pi^1_1$ means that the set is definable by a statement of the form $\forall y\, \varphi(x,y,z)$, where the quantifer $y$ ranges over reals, and $\varphi$ has only quantification over natural numbers, and $z$ is a real parameter. These are also known as the co-analytic sets. – Joel David Hamkins Jul 21 '10 at 0:51
It seems I have slipped some AC use into a part of my cardinality calculation, since I only have surjections both ways between Borel sets and the reals, which isn't enough to get a bijection. (One needs injections to emply Cantor-Schroeder-Bernstein.) But it is sufficient anyway for my conclusion, since Cantor shows there is no surjection $\mathbb{R}\to P(\mathbb{R})$, but I did exhibit a surjection of $\mathbb{R}$ onto the Borel sets. So we retain the conclusion that most sets are not Borel. I wonder what the exact AC content is of an actual bijection between $\mathbb{R}$ and the Borel sets? – Joel David Hamkins Jul 21 '10 at 3:17

There are some very nice examples of non-Borel sets. Two that I particularly like are the differentiable functions (as a subset of the space of continuous functions on [0,1], say) and the set of all infinite graphs that contain an infinite clique (as a subset of the set of all graphs with vertex set $\mathbb{N}$ with the product topology). In general, a continuous image of a Borel set need not be Borel, and many natural non-Borel sets arise this way.

-
So are we to conclude from Andres Caicedo's answer that any PROOF that [the differentiable functions] is not Borel must use the Axiom of Choice? Probably, as remarked by Joel, we probably merely show the set is not $\Delta^1_1$ and then rely on AC to conclude it is not Borel. – Gerald Edgar Jul 22 '10 at 11:53
Gerald, yes, by Andres' answer, you need to use at least some choice to prove that there is any non-Borel set at all. In particular, in the model of ZF he mentions, Gowers' examples here are Borel, like the other examples we've had, because every set in that model is Borel. It appears that countable AC is sufficient to get the basic theory moving, and I expect that would be sufficient to prove that these examples are not Borel (but I haven't checked). – Joel David Hamkins Jul 22 '10 at 11:59

Measure theory without the Axiom of Choice (not even countable choice) is discussed in Fremlin, Measure Theory, Volume 5, Chapter 56. This is freely available online. Thanks to MO and ex-falso-quodlibet for making me aware of this extensive text in this answer.

He mentions Feferman & Levy's result that it is consistent that the reals are a countable union of countable sets, as per Andres' answer. This makes the standard definition of Borel sets unhelpful, as everything is Borel. However, it is still possible to do analysis and measure theory without choice. You just need the right definitions. Fremlin discusses codable Borel sets. Unions and intersections of 'codable sequences' of codable Borel sets are themselves codable Borel sets. The basic idea is to represent exactly how a set is built up in terms of successive sequences of unions and set-complements, starting from an enumeration of a base for the topology. This done via countable tree structures, which define a construction of subsets of R (or any Polish space) by applying countable unions of complements as you step along the tree. This definition uses a countable transfinite induction to construct the map from trees to codable Borel sets. An important point being:

In the presence of countable choice, codable Borel sets = Borel sets.

I see that Andres & Joel mention this as a theorem in their answers. However, it is not true without countable choice. The union of a sequence of codable Borel sets does not have to be Borel, so even if the reals could be written as a countable union of countable sets it does not follow that all subsets are codable Borel. However, given a sequence of codable Borel sets with a specified choice of codings, their union is codable Borel. Without countable choice, it makes sense to work with codable Borel sets instead of the standard Borel sets. Then, many standard results carry across to the situation without countable choice. E.g., a set is codable Borel if and only both it and its complement are analytic sets (continuous images of closed subsets of $\mathbb{N}^\mathbb{N}$).

There are certainly explicitly constructable subsets of the reals which are not codable Borel. I think Joel's arguments should carry through to the situation without countable choice.

One way to construct explicit examples of non codable Borel sets is to construct an analytic set whose complement is not analytic. Lusin's example (linked to in the question) fits into this method, although I'm not sure if it still works without choice. There are other more difficult to describe examples which do though. (I ran out of time on this answer, so will return to it later).

[continued...]

There is a standard way of constructing non-Borel sets, which is mentioned in, e.g., Cohn, Measure Theory (Corollary 8.2.17) and, even without countable choice, the argument still works to give you a non-codable-Borel set. It is a diagonalization kind of argument. This constructs a subset of Baire space $\mathcal{N}=\mathbb{N}^\mathbb{N}$ (under the product topology). This is a Polish space homeomorphic to the irrational numbers in [0,1] by the continued fraction representation (I'm taking $\mathbb{N}=\{1,2,\ldots\}$ for convenience).

If X,Y are Polish spaces, then say a subset $S\subseteq X\times Y$ is universal if every closed subset of X is of the form $S_y=\{x\in X\colon(x,y)\in S\}$. It is always possible to construct a closed universal subset of $X\times\mathcal{N}$. If $U_1,U_2,\ldots$ is an enumeration of a base for the topology on X, then

$$S=\left\{(x,y)\in X\times\mathcal{N}\colon x\in\bigcap_{n=1}^\infty U_{y(n)}^c\right\}$$

is closed and universal.

Now, take S to be a closed universal subset of $X\times\mathcal{N}$ where $X=\mathcal{N}\times\mathcal{N}$.

The set $A=\{x\in\mathcal{N}\colon \exists y\in\mathcal{N}{\rm\ s.t.\ } (x,y,x)\in S\}$ is an analytic but non-codable-Borel subset of $\mathcal{N}$.

A subset of a Polish space X is analytic if it is the projection of a closed subset of $X\times\mathcal{N}$ onto X. The set A above is the projection of the set $\{(x,y)\in\mathcal{N}^2\colon(x,y,x)\in S\}$, so is analytic. If it was codable Borel, then its complement would be the projection of some closed set $B\subseteq\mathcal{N}^2$. By universality, $B=S_x$ for some $x\in\mathcal{N}$. However, $$x\in A^c\iff \exists y{\rm\ s.t.\ } (x,y)\in S_x \iff \exists y{\rm\ s.t.\ }(x,y,x)\in S\iff x\in A$$ would give a contradiction.

In fact, I think I can show that the set you linked to by Lusin is not codable Borel, without using choice. By continued fraction representation, it is the same as saying that the following is not codable Borel.

S = the set of $x\in\mathcal{N}$ for which there is an increasing sequence $0\lt i_1\lt i_2\lt\cdots$ such that each $x(i_k)$ divides $x(i_{k+1})$.

In the presence of choice, this is standard (Kechris, Classical Descriptive Set Theory has a proof, but I don't have a copy). I expect that the proof can be adapted in the absence of countable choice but, as I don't know the standard proof of this, I can give a very very rough sketch of my own. The idea is to consider the set of trees $\mathcal{T}$, where each node has a countable set of children corresponding elements of $\mathbb{N}$. Any such tree is defined by the set of finite paths $(i_1,\ldots,i_n)\in\mathbb{N}^*=\bigcup_{n=1}^\infty\mathbb{N}^n$ it contains, and $\mathcal{T}$ forms a Polish space (using the product topology on $\{0,1\}^{\mathbb{N}^*}$). Let $\mathcal{T}_0\subseteq\mathcal{T}$ be the trees containing no infinite paths. These correspond to the Borel codes. Then, $\mathcal{T}_0$ is itself not codable Borel (*). Next, each tree can be represented uniquely by an element $x\in\mathcal{N}$ in such a way that passing from a node to one of its children corresponds to going from i to $j\gt i$ where $x(i)$ divides $x(j)$. Then, $\mathcal{T}_0$ correponds precisely to the set S above which, therefore, is not codable Borel.

(*) That $\mathcal{T}_0$ is not Borel is standard (in the presence of AoC). I don't know the proof of this, maybe it can be shown using a similar argument to the one above for non-analytic sets. However, I can put together an alternative rough argument of my own that it is not codable Borel. The idea is that each tree corresponds to a program for some super-Turing machine which can perform countable Boolean operations at once, and those without infinite paths are guaranteed to halt. If $\mathcal{T}_0$ was codable, then there would be a Borel code $T\in\mathcal{T}_0$ which generates $\mathcal{T}_0$. This is similar to having a Turing program which solves the halting problem, and we could derive a contradiction in a similar way. There are some messy details in getting this analogy to go through properly, but it seems like it should work.

-
Out of curiosity: does analysis get anything out of knowing that one can do analysis without choice? – Mariano Suárez-Alvarez Jul 22 '10 at 1:12
Good question. I'd be lying if I said I knew the answer to that one. I personally haven't ever done any measure theory without at least countable choice. A more careful consideration of Fremlin's discussion in his book might help to answer that. – George Lowther Jul 22 '10 at 1:24
Yes, this issue about codable Borel sets was exactly what I was describing with borel codes, and you can only build a code for the union if you have the codes for the sets already chosen. – Joel David Hamkins Jul 22 '10 at 1:24
Yes. I didn't realize how close that was to your argument when I first posted. My construction of non Borel sets (which I added now) is rather different though. – George Lowther Jul 22 '10 at 22:04