Quick description
The Borel sets for a given topology are defined to be the smallest class of sets that contains all open sets and is closed under countable unions and intersections. Therefore, to prove that every Borel set has a certain property, it is sufficient to prove it for open sets (or even for simpler sets such as intervals), and then to prove that countable unions or countable intersections of sets with the property have the property. It is also possible to express such arguments in terms of transfinite induction.
Prerequisites
Basic real analysis, measure theory.
Example 1
The following problem arises in connection with measure differential inclusions, which are problems of the form

where is a closed convex set-valued function with possibly unbounded values.
Given a vector measure with values in
and a non-negative measure
(positive for open sets), the problem is to show that if
for any open set where
is a closed convex set, then
where
which is known as the asymptotic or recession cone of .
Since we are assuming the result for open sets, it is sufficient to prove that the property is closed under countable unions and intersections. We can make this task slightly easier by noting that finite unions and intersections of sets with the desired property also have the desired property; this in turn means that we only need to deal with nested countable unions and intersections.
Considering nested unions, suppose with
. Then either
for all
, or there is an
where
. In the former case,
for all
, and so taking limits,
as
is a closed convex cone. In the latter case, we have
for all
, and so taking limits the result again holds.
Considering nested intersections, suppose with
. Then either
or
. In the former case,
for all
, and taking limits of
gives the desired result. If
then either
for some
or
for all
. In
then
for all
and taking limits of
again gives the desired result. Finally, considering
for all
we see that

Taking limits and using the definition of gives the desired:
.
General discussion
One can think of the Borel sets as being built up from the open sets by means of successive operations of countable unions and intersections. However, there are transfinitely many stages to this process, so transfinite induction is needed.
More precisely, we build up the Borel sets for a metric space as follows: for each ordinal we have a class of sets
, where
-
is the set of open sets,
-
is the set of countable unions or countable intersections of sets in
,
-
is
is a limit ordinal.


Note that contains all the closed sets (for a metric space) and so contains all the complements of sets in
.
Thus, the complement of any set in
can be found in
for finite
; if
is infinite, then complements of sets in
are in
.
To prove the above result, we could use a transfinite induction on the levels of the Borel hierarchy. We start with the fact that (Target) holds for for all .
If (Target) holds for all for
with
a limit ordinal, then clearly by definition of
, (Target) also holds for all
.
To deal with successor ordinals, one has to prove that if (Target) holds for sets then it holds for
and
. This we showed above.
Comments
Example 1 could use some
Tue, 05/05/2009 - 18:11 — Anonymous (not verified)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
Tue, 05/05/2009 - 18:40 — gowersIt 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
Thu, 07/05/2009 - 11:59 — dstewartThe 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
Thu, 07/05/2009 - 13:22 — gowersNot 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
of
matrices with that property. Then I know that every matrix in the group
generated by
has that property as well. Why? Well, I could build up
stage by stage and do an inductive argument. Alternatively, I could say that I know that the set of all
matrices with that property forms a subgroup of the group of all
invertible matrices, and that subgroup contains
. Therefore, it contains the group generated by
. 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
Tue, 19/05/2009 - 01:28 — emertonAt the moment, example 1 contains a reference to
, although these are not defined until later in the article. Maybe someone with a better feeling for the material can correct this.
Thanks – I didn't quite
Tue, 19/05/2009 - 07:52 — gowersThanks – I didn't quite make enough modifications to the earlier version of the article, but have fixed it now.