Why are all sets we can construct Borel sets?

Question

It is said in the textbook https://measure.axler.net/

However, any subset of $\mathbb R$ that you can write down in a concrete fashion is a Borel set.

How should we understand this sentence?

Here are some ideas I can think of

• I have once heard that we can suppose the Borel sets includes all subsets of $\mathbb R^n$ if we don't admit the axiom of choice and it does not conflict with ZF set theory. But I am not sure whether this can explain the universality of Borel sets.

• Also, it seems that Borel set is somehow alike "Computable numbers" proposed by Alan Turing, but I am not sure how to draw this analogy.

Answer 1

The statement is false. Look here for a concrete description of a non-Borel set.

May be the author confused non-Borel sets with non-measurable sets, which can't be constructed explicitly because the proof of its existence is only possible via the Axiom of Choice.

Answer 2

"Concrete" isn't a word with a precisely defined meaning here. The author is using the word "concrete" to indicate that Borel descriptions are more complicated than computable or constructive definitions, but less complicated than using arbitrary definitions in set theory (or even just definitions in 2nd-order arithmetic aka analysis).

In general, to be considered concrete here, a description should not require more than countably much context outside of the object being described. The idea is that a notion about real numbers isn't concrete if it involves quantifying, for instance, over all reals, or over all sets of reals.

Each Borel set is describable by a code showing how to build it up from open sets using countable unions, countable intersections, and/or complements -- this code is essentially a countable well-founded tree.

A Borel code is concrete in the sense that the relation $$\text"r\text{ belongs to the Borel set with Borel code }s\text"$$ is absolute; you can tell whether $r$ belongs to the Borel set with Borel code $s$ by looking at just $r$ and $s$ (you don't need to know about the rest of the set-theoretic universe). (To be clear here, the countably much extra information needed to determine whether $r$ belongs to this Borel set is precisely the Borel code $s.)$

In fact, Borel sets are right at the edge of this notion of concreteness. Although each Borel set can be described concretely in this way, you can't view the whole collection of Borel sets as being defined concretely — knowing the whole collection of Borel sets requires knowing countings of all the countable ordinals. If we have two transitive models $M$ and $N$ of ZFC with $\aleph_1^M\lt\aleph_1^N,$ then $N$ has many Borel sets that $M$ doesn't know anything about (since the corresponding Borel code will require using a countable well-founded tree whose height isn't countable in $M,$ so this Borel code won't belong to $M).$

In summary, each Borel set is concrete in that membership in it can be described fully by a countable object (a corresponding Borel code), without involving any additional context. But knowing the entire collection of Borel sets requires knowing how to count all ordinals less than $\aleph_1,$ which is far too much additional context for this to be considered concrete (and, in fact, depends on the model of set theory that you're working in).

---

You can certainly define non-Borel sets in ZFC, as indicated in the Wikipedia link in another answer. But that definition won't be concrete — the usual examples will involve quantifying over all real numbers. So determining whether some real $r$ belongs to this non-Borel set $X$ depends on more than just $r;$ you need to know about all real numbers. If it were concrete, you'd need to know just $r$ (and maybe countably much additional information).

---

As for Borel sets being like computable numbers, a better analogy can be drawn between the Borel hierarchy and the hyperarithmetic hierarchy (which is basically an effective version of the Borel construction).

---

Addendum on the axiom of choice:

Since a lot of the comments seem to be about the axiom of choice (AC), let me say that I think this is a red herring.

First of all, Axler's book says that it uses the axiom of choice freely (although the author does point out where AC is used). So AC really isn't an issue for OP's question at all.

Secondly, even if you're working without AC, in the typical situation where you are using Borel sets, you would be assuming the axiom of dependent choices (DC), which lets you develop all the usual theory of Borel sets and Lebesgue measure (except a few pathologies such as the existence of a set of reals that is not Lebesgue measurable).

Finally, even in the absence of countable choice, Borel codes work well and still represent a concrete description of a set of reals. (In this situation, Borel sets should be defined as those sets of reals which have a Borel code. Without countable choice, it’s possible that having a Borel code is not equivalent to being in the smallest $\sigma$-algebra containing all the open sets.)