Return to Answer

It is not difficult to see that there are only continuum many Borel sets, that is,  $2^{\aleph_0}$ many. But there are $2^{2^{\aleph_0}}$ many sets of reals. So 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 hiearchy 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. Thus, we can map the reals onto the set of Borel sets, and conversely, so they have the same size, without using AC.

One can also give very 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 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, since if it were, I could flip the values on the diagonal and produce an analytic set that is not a slice.

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.

It is not difficult to see that there are only continuum many Borel sets, that is, $2^{\aleph_0}$ many. But there are $2^{2^{\aleph_0}}$ many sets of reals. So 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 hiearchy 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. Thus, we can map the reals onto the set of Borel sets, and conversely, so they have the same size, without using AC.

One can also give very 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 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$.

It is not difficult to see that there are only continuum many Borel sets, that is, $2^{\aleph_0}$ many. But there are $2^{2^{\aleph_0}}$ many sets of reals. So 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 hiearchy 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. Thus, we can map the reals onto the set of Borel sets, and conversely, so they have the same size, without using AC.

One can also give very 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 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, since if it were, I could flip the values on the diagonal and produce an analytic set that is not a slice.

It is not difficult to see that there are only continuum many Borel sets, that is, $2^{\aleph_0}$ many. But there are $2^{2^{\aleph_0}}$ many sets of reals. So 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 hiearchy 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. Thus, we can map the reals onto the set of Borel sets, and conversely, so they have the same size, without using AC.

One can also give very concrete examples of sets that are not Borel. For example, the set of reals that code a binary relation on the natural numbers that is a well order is a complete $\Pi^1_1$ set, and cannot be Borel.

It is not difficult to see that there are only continuum many Borel sets, that is, $2^{\aleph_0}$ many. But there are $2^{2^{\aleph_0}}$ many sets of reals. So 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 hiearchy 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. Thus, we can map the reals onto the set of Borel sets, and conversely, so they have the same size, without using AC.

One can also give very 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 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$.