# Proof that the Cardinality of Borel Sets on $\mathbb R$ is $c$ without using the ordinals .

I'm trying to prove that cardinality of Borel sets is $c$ without using the concept of ordinal number. I know that the Cardinal of Borel sets are greater than $c$ because of every point in $\mathbb R$ is Borel set, therefore it's enough to show that the cardinal of borel sets is at most $c$ . My idea about this question is as follow : $$B_{(I,J)}=\left(\bigcup_{i\in I}A_i\right)\cup \left(\bigcap_{j\in J}A_j\right)$$ here $I,J$ are arbitrary subset of $\mathbb N$ and since $\mathbb R$ is second countable so has countable basis $\{{A_i}\}_{i \in \mathbb N}$ . I seek to construct a sigma-algebra on $\{B_{(I,J)}\}$

Can somebody improve my idea or give me another idea?

Thanks

• All these sets are uniosn of open sets and an $F_\sigma$, so are only $F_\sigma$. A far stretch from all Borel sets. – Henno Brandsma May 2 '16 at 20:44
• @HennoBrandsma : I edited ! I seek to construct a sigma-algebra on $\{B_{(I,J)}\}$ – Mojtaba May 4 '16 at 2:41
• @AndrésCaicedo : Do you have another idea? please explain more! – Mojtaba May 4 '16 at 3:09

Your idea is sound, but it requires more work. As pointed out, you have only described so far a very small subcollection of the Borel sets. Instead, show that you can associate to each Borel set a code that keeps track of the "history" of its construction starting from basic open sets, and then count the number of such codes.

There is a lot of leeway on how we could do this. To be concrete, we will use as codes infinite sequences of natural numbers. Since there are only $$\mathfrak c$$ many such sequences, this will do the trick.

The Borel sets are the elements of the $$\sigma$$-algebra generated by the open intervals with rational endpoints. The codes are the "certificates of membership". Given a code, you can easily reconstruct from it the Borel set it is coding.

• Begin by enumerating the open intervals with rational endpoints. The $$n$$th such interval is represented by the infinite sequence of natural numbers $$(0,n,0,\dots)$$, where $$n$$ is followed by infinitely many $$0$$s.

• If $$A_0,A_1,\dots$$ have codes $$a_0,a_1,\dots$$ (where each $$a_i$$ is an infinite sequence of natural numbers), the code for $$\bigcup_n A_n$$ is the sequence $$(1,m_1,m_2,\dots)$$ where $$m_{2^n(2k+1)}$$ is the $$k$$th element of the sequence $$a_n$$.

• If $$A$$ has code $$a$$, the complement of $$A$$ has code the sequence that starts with $$2$$ and is followed by $$a$$.

The class of codes that represent Borel sets in the form just described forms a (definable) subset of the collection of all infinite sequences of natural numbers, and therefore has size at most $$\mathfrak c=|\mathbb R|=|\mathbb N^{\mathbb N}|$$. Let's call this collection of sequences $$\mathsf{BC}$$, for Borel codes. Consider now the class of Borel sets that are coded by some sequence in $$\mathsf{BC}$$. By the first clause, this class contains all open intervals with rational endpoints and therefore, by the second clause, it contains all open sets. The second clause also gives us that the class is closed under countable unions, and the third clause gives us that it is closed under complements. It follows that this class is a $$\sigma$$-algebra that contains all open sets, and therefore contains all Borel sets. Since each sequence in $$\mathsf{BC}$$ codes a Borel set, what we have is that each Borel set is coded this way or, if you wish, that the clas of Borel sets is the surjective image of $$\mathsf{BC}$$ and therefore (by the axiom of choice!) has size at most $$\mathfrak c$$ as well.

On the other hand, each singleton is a Borel set, and therefore there are at least $$\mathfrak c$$ such sets. By the Bernstein-Cantor-Schröder theorem, we are done.

Ok. Two remarks. One is that the ordinals are not too far from here anyway. To verify whether a sequence is in $$\mathsf{BC}$$ you try to decode it and see that it comes according to the instructions above from "simpler" sequences in $$\mathsf{BC}$$. To formalize this so that there is no circularity, one typically uses a rank function (and therefore ordinals).

Two, any Borel set has many codes associated to it (since, for instance, $$A$$ is the complement of the complement of $$A$$, and is also the countable union $$\bigcup_n A_n$$ where each $$A_n$$ is just $$A$$), but this does not matter, in the sense that, under the axiom of choice, if there is a surjection from a set $$B$$ to a set $$C$$, then $$|C|\le|B|$$. However, choice needs to be invoked here. For example, it is consistent with $$\mathsf{ZF}$$ (without the axiom of choice) that every set of reals is Borel, in fact, that every set of reals is the countable union of countable sets, and there are certainly more sets of reals than there are reals.

Results of Hjorth make this even more dramatic in some settings: the axiom of dependent choice for reals is the statement that every tree $$T$$ on a subset of $$\mathbb R$$ with no end nodes has an infinite branch; this axiom is a strong enough version of choice that in particular rules out the pathological example I mentioned above. Assuming this axiom, and the axiom of determinacy, Hjorth proved not only that there are more Borel sets than reals. In fact, $$|\mathbf\Sigma^0_\alpha|<|\mathbf\Sigma^0_\beta|$$ for $$1\le\alpha<\beta<\omega_1$$, and Neeman improved this to show that moreover $$|\mathbf\Delta^0_{\alpha+1}|<|\mathbf\Sigma^0_{\alpha+1}|$$ for $$1\le\alpha<\omega_1$$.

Here, $$\mathbf\Sigma^0_1$$ is the class of open sets and, for $$\alpha\ge1$$ a countable ordinal, $$\mathbf\Pi^0_\alpha$$ is the class of complements of $$\mathbf\Sigma^0_\alpha$$ sets, $$\mathbf\Delta^0_\alpha=\mathbf\Sigma^0_\alpha\cap\mathbf\Pi^0_\alpha$$, and for $$\alpha>1$$, $$\mathbf\Sigma^0_\alpha$$ is the class of countable unions of sets in $$\bigcup_{\beta<\alpha}\mathbf\Sigma^0_\beta$$, so that the Borel sets are the sets in $$\bigcup_{\alpha<\omega_1}\mathbf\Sigma^0_\alpha$$.

(On the other hand, under the full axiom of choice, all these classes have the same size as the reals.)

In set theory, particularly in choiceless settings, it is sometimes important to have codes of Borel and more complicated sets, since they give us more information than just the set they code: They are, as I said, "certificates of membership".

Let me give two hints of the usefulness of this approach:

David Fremlin uses a similar construction to define and develop the basic properties of Lebesgue measure without assuming any choice. The traditional approach just does not work without choice: It is consistent in the absence of choice that the reals are the countable union of countable sets. Since countable sets have measure zero, countable additivity of the measure would imply that $$\mathbb R$$ and therefore every set has measure zero. When working with codes, the saving grace is that there is no code for the reals witnessing that $$\mathbb R$$ is a countable union of countable sets: we do not have enough choice to simultaneously pick up the representations of all these countable sets to put them together in a single code. In the choiceless approach, we associate measures to the codes rather than directly to the sets. One then needs to check that if a set has two different codes (which, as I indicated above, happens), both have the same associated measure.

Another example is in the theory of determinacy. Here, we actually extend the coding mechanism so we can represent sets much more complicated than just the Borel sets. Nevertheless, the codes we use are still small objects, and so they are easier to argue with (combinatorially) than the sets they represent. This is really useful. (I even have a paper indicating several concrete applications of this approach.)

• Thanks , I constructed a Sigma algebra on my idea. – Mojtaba May 7 '16 at 19:23
• A little question : when you say "This associates to each Borel set a sequence.", isn't it the other way round ? As far as i understand, your process associates (by transfinite induction, right ?) a Borel set to each code. Now, how can you prove that each Borel set is attained ? – Plop Oct 23 '16 at 15:23
• @Plop Sure, the process assigns Borel sets to codes. To see that each Borel set is attained, check that the collection of sets assigned to codes is a $\sigma$-algebra containing all open sets, which should be immediate by design. – Andrés E. Caicedo Oct 23 '16 at 16:49
• @user49404 I should probably edit the answer to address this, as it comes up with some frequency. I'll do that now, thanks for reminding me. – Andrés E. Caicedo Dec 5 '18 at 22:06
• (@user49404 Edited.) – Andrés E. Caicedo Dec 5 '18 at 22:42