a repository of mathematical know-how

Revision of Use transfinite induction to construct Borel sets from Tue, 05/05/2009 - 14:57

Quick description

Transfinite induction can be used to construct the Borel sets for a given topology. Since each stage of the construction can be carefully controlled, it is possible to prove results that hold for all Borel sets based on results for simple sets (such as open sets or even intervals).

We can construct the Borel sets for a metric space as follows: for each ordinal \alpha we have {\bold B}_\alpha:

  • {\bold B}_0 is the set of open sets,

  • {\bold B}_{\alpha+1} is the set of countable unions or countable intersections of sets in {\bold B}_\alpha,

  • {\bold B}_\alpha = \bigcup_{\beta<\alpha}{\bold B}_\beta is \alpha is a limit ordinal.

Then {\bold B}_{\omega_1} is the set of Borel sets where \omega_1 is the first uncountable ordinal.


Measure theory, transfinite induction.

Example 1

The problem in this case is given a vector measure \mu with values in \R^n and a non-negative measure \nu (positive for open sets) to show that if

for any open set U where K\subseteq \R^n is a closed convex set, that then


which is known as the asymptotic or recession cone of K.

We start the induction with the fact that (Target) holds for for all E\in{\bold B}_0.

If (Target) holds for all {\bold B}_\beta for \beta<\alpha with \alpha a limit ordinal, then clearly by definition of {\bold B}_\alpha, (Target) also holds for all E\in{\bold B}_\alpha.

The hard part is then dealing with successor ordinals.

The complexity can be reduced by realizing that finite unions and intersections of sets in {\bold B}_\alpha are also in {\bold B}_\alpha; this in turn means that we only need to deal with nested countable unions and intersections at each stage of the construction.

Considering nested unions, suppose E=\bigcup_{i=1}^\infty E_i with E_i\subseteq E_{i+1}. Then either \nu(E_i)=0 for all i, or there is an i where \nu(E_i)>0. In the former case, \mu(E_i)\in K_\infty for all i, and so taking limits, \mu(E)\in K_\infty as K_\infty is a closed convex cone. In the latter case, we have \mu(E_j)/\nu(E_j)\in K for all j\geq i, and so taking limits the result again holds.

Considering nested intersections, suppose E=\bigcap{i=1}^\infty E_i with E_i\supseteq E_{i+1}. Then either \nu(E)>0 or \nu(E)=0. In the former case, \nu(E_i)>0 for all i, and taking limits of \mu(E_i)/\nu(E_i)\in K gives the desired result. If \nu(E)=0 then either \nu(E_i)=0 for some i or \nu(E_i)>0 for all i. In \nu(E_i)=0 then nu(E_j)=0 for all j\geq i and taking limits of \mu(E_j)\in K_\infty again gives the desired result. Finally, considering \nu(E_i)>0 for all i we see that

\mu(E_j) = \nu(E_j)\,x_j,\qquad x_j \in K.

Taking limits and using the definition of K_\infty gives the desired: \mu(E)\in K_\infty.

General discussion


Example 1 could use some

Example 1 could use some motivation: where does this sort of statement come up and why would one want to prove it?

It doesn't look to me as

It doesn't look to me as though transfinite induction is needed here. All you need is that the Borel sets are the closure of the open sets under countable unions and intersections. So I think the article should have a title such as the following — "To prove a fact about all Borel sets, prove it for open sets and prove that it is preserved by countable unions and intersections" — and should be rewritten accordingly.

The title could definitely be

The title could definitely be changed. But transfinite induction is needed: to get from the base class of open sets to all Borel sets requires it, or something similar.

Not if you define the class

Not if you define the class of Borel sets to be the smallest class of sets that contains the open sets and is closed under countable unions and intersections. Then if you want to prove that some fact P is true of all Borel sets it is sufficient to prove that it holds for all open sets, and that a countable union or intersection of sets satisfying P satisfies P.

An analogy: suppose I have some property of invertible matrices and I know that the product of two matrices with that property has the property, and the inverse of a matrix with that property has the property. Now I take a set X of n\times n matrices with that property. Then I know that every matrix in the group G generated by X has that property as well. Why? Well, I could build up G stage by stage and do an inductive argument. Alternatively, I could say that I know that the set of all n\times n matrices with that property forms a subgroup of the group of all n\times n invertible matrices, and that subgroup contains X. Therefore, it contains the group generated by X. The second proof, uses a different notion of "subgroup generated by" and you need induction only to prove that the two notions are equivalent.

In the case of Borel sets, it is neater to use the definition above because it saves you having to mention ordinals every time you want to prove something.

Remark added 16/5/09: I have rewritten the article to reflect the fact that transfinite induction is not needed.

At the moment, example 1

At the moment, example 1 contains a reference to \mathbf{B}_{\alpha}, although these are not defined until later in the article. Maybe someone with a better feeling for the material can correct this.

Thanks &ndash; I didn't quite

Thanks – I didn't quite make enough modifications to the earlier version of the article, but have fixed it now.