# About the generating structure of Borel field

On P.32 of [P.Billingsley] Probability and Measure, 3ed, 1993, the author wrote:

...and there are Borel sets that cannot be arrived at from the intervals by any finite sequence of set-theoretic operations, each operation being finite or countable. It can even be shown that there are Borel sets that cannot be arrived at by any countable sequence of these operations. On the other hand, every Borel set can be arrived at by a countable ordered set of these operations if it is not required that they be performed in a simple sequence.

Then the author referred me to the following exercise which I cannot figure it out:

For any class $\mathcal{H}$ of sets in $\Omega$ let $\mathcal{H}^{*}$ consist of sets in $\mathcal{H}$, the complements of sets in $\mathcal{H}$ and the finite and countable unions of sets in $\mathcal{H}$. Given a class $\mathcal{A}$, put $\mathcal{A}_{0}=\mathcal{A}$ and define $\mathcal{A}_{1},\mathcal{A}_{2},\cdots$ inductively by: $$\mathcal{A}_{n}=\mathcal{A}_{n-1}^{*}$$ That each $\mathcal{A}_{n}$ is contained in $\sigma(\mathcal{A})$ follows by induction.

(1)Prove that if $\Omega=(0,1]$, $\mathcal{A}_{0}=\emptyset$ and the intervals with rational endpoints in $\Omega$,$\cup^{\infty}_{n=0}\mathcal{A}_n$ is strictly smaller than $\sigma(\mathcal{A}_{0})$

(2)Extend the above construction to infinite ordinals $\alpha$ be defining $$\mathcal{A}_{\alpha}=(\cup_{\beta<\alpha}\mathcal{A}_{\beta})^{*}$$ Show that if $\Omega$ is the first uncountable ordinal, then
$$\cup_{\beta<\Omega}\mathcal{A}_{\beta}=\sigma(\mathcal{A})$$ Moreover, show that if the cardinality of $\mathcal{A}$ does not exceed that of the continuum, then the same is true of $\sigma(\mathcal{A})$, Thus the Borel field has the power of the continuum as its own cardinality.

(i)I cannot figure out how to prove the second problem altough the author provided a hint:

Use the fact that, if $\alpha_{1},\alpha_{2},\cdots$is a sequence of ordinals satisfying $\alpha_{n}<\Omega$, then there exists an ordinal $\alpha$ such that $\alpha<\Omega$ and $\alpha_{n}<\alpha$ for all $n$.

(ii)In particular, I do not quite understand what is the significance of "countable ordered set" here? What role does the "order" play in this construction?

(iii)"It can even be shown that there are Borel sets that cannot be arrived at by any countable sequence of these operations." Where can I find a reference for this issue?

• I think "a countable sequence of these operations" is in this notation $\mathcal A_\omega$. But a countable ordinal is "a countable ordered set" so that part refers to $\mathcal A_\alpha$ for a countable ordinal. – Gerald Edgar Sep 10 '15 at 0:47
• @GeraldEdgar I am very confused about author's words so do you know any text that addresses the same problem more clearly? Thanks. – Henry.L Sep 10 '15 at 0:52
• I first saw this in Hewitt & Stromberg, Real and Abstract Analysis. – Gerald Edgar Sep 10 '15 at 0:55
• Please add a link to the Math.SE question. – Nate Eldredge Sep 10 '15 at 2:38
• I think you'll have to read up a little on the basics of ordinals and cardinal arithmetic, then (2) becomes essentially trivial. The hint (your box) gives the claimed representation of $\sigma(A)$, and the claim on the cardinality follows from $|A_{\alpha}|=c$ (by induction) and $c^{\omega}=c$. – Christian Remling Sep 10 '15 at 22:50

Hint Use the fact that, if $\alpha_{1},\alpha_{2},\cdots$is a sequence of ordinals satisfying $\alpha_{n}<\Omega$, then there exists an ordinal $\alpha$ such that $\alpha<\Omega$ and $\alpha_{n}<\alpha$ for all $n$.

Proof By the $\mathbb{R^{1}}$ ordered topology ([H&S] (4.42)), the first uncountable $\Omega$ ([H&S] (4.49) proved its existence) is often written as $[0,\Omega)$ Every increasing sequence ${\alpha_{i}}$ of elements of $[0,\Omega)$ converges to a limit in $[0,\Omega)$ since the supremum ($\cup_{i=1}^{\infty}\alpha_{i}$) of every countable set of countable ordinals is another countable ordinal. This proves the hint above. The $\alpha$ in that hint is actually the limit of the sequence ${\alpha_{i}}$.#

Since for any class $H$ of sets in $\Omega$ the class $H^{∗}$ consist of sets in $H$, the complements of sets in $H$ and the finite and countable unions of sets in $H$, we have:

Prop 1 If the cardinality of $H$ is countable, the cardinality of $H^{*}$ cannot exceed countable cardinality.

Proof All the complements of this class is another class with the same cardinality, and the countable unions of countably many elements in $H$ is still countable.#

Prop 2 $|A_{\alpha}|\neq \omega$(countable cardinal)

Proof If there exists some $\alpha_{0}$ such that $|A_{\alpha_{0}}|=\omega$, then choose the least such $\alpha_{0}$ ([H&S] (4.47)). $|A_{\alpha_{0}}|=|(\cup_{\beta<\alpha}A_{\beta})^{*}|=\omega$, hence by Prop 1 $|\cup_{\beta<\alpha}A_{\beta}|=\omega$ and hence $|A_{\beta}|=\omega,\forall \beta < \alpha_{0}$. Now each such $\beta$ violates the minimality of $\alpha_{0}$#

And since $c\geq |A_{\alpha}|\neq \omega$, it has to be $|A_{\alpha}|=c$ due to the continuum hypothesis.

Prop 3$\cup_{\beta<\Omega}A_{\beta}=\sigma(A)$

Proof $\cup_{\beta<\Omega}A_{\beta}\supset \sigma(A)$ is clear since every element in this sigma field should be obtained via a sequence(countable or not) of these operations. $\cup_{\beta<\Omega}A_{\beta}\subset \sigma(A)$ is also clear by definition of $\sigma(A)$ that it is the smallest sigma field containing these operations' result.#

Then by Prop 2 and the formula $\cup_{\beta<\Omega}A_{\beta}=\sigma(A)$, $|\sigma(A)|=c^{\omega}=c$

I still feel a bit uncertain about Prop 3, can anyone make it clearer to me? I am deeply appreciate all your help.

Reference [H&S] Hewitt & Stromberg, Real and Abstract Analysis.

# Comments by Dave L. Renfro:

What follows is a proof of "Prop 3", which your comments indicated a concern with. My notation varies slightly from your notation because I wrote it earlier this morning where I didn't have access to the internet.

If $\mathcal{C}$ is a collection of subsets of a given set $X,$ let ${\mathcal{C}}^{*}$ be the collection of sets, each of which is an at most countable union of sets, each of which either belongs to $\mathcal{C}$ or its complement belongs to $\mathcal{C}.$ We now define the possibly larger collections ${\mathcal{C}}_{\alpha}$ for each ordinal $\alpha$ by letting ${\mathcal{C}}_0 = \mathcal{C} \cup \{X\}$ and ${\mathcal{C}}_{\alpha} = \left(\cup_{0 \leq \beta < \alpha} {\mathcal{C}}_{\beta} \right)^{*}$ for each ordinal $\alpha > 0.$ I will show that ${\mathcal{C}}_{\omega_1} = \sigma(\mathcal{C})$ by showing ${\mathcal{C}}_{\omega_1} \subseteq \sigma(\mathcal{C})$ and $\sigma(\mathcal{C}) \subseteq {\mathcal{C}}_{\omega_1}.$

First, note that ${\mathcal{C}}_{\alpha} \subseteq \sigma(\mathcal{C})$ for each ordinal (at most countable or not, although we only need this for at most countable ordinals). This is either obvious or it can be proved by transfinite induction, depending on how formal you want to make things. It follows that ${\mathcal{C}}_{\omega_1} \subseteq \sigma(\mathcal{C}).$ To show the opposite inclusion, I'll prove that ${\mathcal{C}}_{\omega_1}$ is a $\sigma$-algebra containing each of the sets in $\mathcal{C},$ and from this the result is immediate by using the fact that $\sigma(\mathcal{C})$ is the minimal (with respect to inclusion) $\sigma$-algebra that contains each of the sets in $\mathcal{C}.$ For closure under complements, if $A \in {\mathcal{C}}_{\omega_1},$ then we have $A \in {\mathcal{C}}_{\alpha}$ for some countable ordinal $\alpha,$ and hence $A^c$ (the complement of $A$ relative to $X$) belongs to ${\mathcal{C}}_{\alpha + 1} \subseteq {\mathcal{C}}_{\omega_1}.$ For closure under at most countable unions, if each of $A_{1},$ $A_{2},$ $A_{3},$ $\ldots$ belongs to ${\mathcal{C}}_{\omega_1},$ then there exist at most countable ordinals $\alpha_{1},$ $\alpha_{2},$ $\alpha_{3},$ $\ldots$ such that $A_1 \in {\mathcal{C}}_{\alpha_1},$ $A_2 \in {\mathcal{C}}_{\alpha_2},$ $A_3 \in {\mathcal{C}}_{\alpha_3},$ $\ldots$ Let $\lambda$ be an at most countable ordinal such that $\alpha_n < \lambda$ for each positive integer $n.$ Then $\cup_{n=1}^{\infty} A_n$ is an element of ${\mathcal{C}}_{\lambda},$ and hence $\cup_{n=1}^{\infty} A_n$ is an element of ${\mathcal{C}}_{\omega_1}$ since ${\mathcal{C}}_{\lambda} \subseteq {\mathcal{C}}_{\omega_1}.$ The proof for closure under at most countable intersections is exactly analogous to that for at most countable unions, but you can also appeal to the fact that any nonempty collection of sets closed under complements and at most countable unions is also closed under at most countable intersections (use De Morgan's Laws).

Some Useful References:

Robert B. Ash, Measure, Integration, and Functional Analysis (1972).

Section 1.2 (pp. 3-13 & 244-245) is useful. In particular, Exercise 9 (p. 12) gives two constructions (as induction over the positive integers) for the algebra generated by a collection of subsets from a given set, and Exercise 11 (p. 13) gives a construction (as transfinite induction over the countable ordinals) for the $\sigma$-algebra generated by a collection of subsets from a given set. Note that fairly detailed solutions to both of these exercises are given on pp. 244-245.

Billingsley, Probability and Measure, 3rd edition (1995).

See Problems 2.22, 2.23 on p. 36 and hints for their solution on pp. 554-555.

Inder K. Rana, An Introduction to Measure and Integration, 2nd edition (2002).

Theorem 4.5.1 (p. 111) states and proves a construction of the algebra generated by a collection of sets (as induction over the positive integers) and Theorem 4.5.2 (pp. 111-112) states and proves a construction of the $\sigma$-algebra generated by a collection of sets (as transfinite induction over the countable ordinals).

Halmos, Measure Theory (1950)

See Chapter I (pp. 9-29).

Felix Hausdorff, Set Theory (1937+ English translation of 3rd edition by John R. Aumann)

See §17, §18, §30, §32, §33.

Kuratowski/Mostowski, Set Theory, 2nd English edition (1976).

• Thanks to Mr.Edgar Mr.Remling. My intuition here is that the sequence of operations should be some how 'dense' to obtain every element in a sigma-field. – Henry.L Sep 11 '15 at 2:31
• Regarding Prop 3, I believe you have the inclusions pointing in the wrong direction in the first two lines of your proof. Also, you'll probably need to use transfinite induction to show the first inclusion. Specifically, show that for each countable ordinal $\beta,$ we have $A_{\beta} \subset \sigma(A),$ and once this is done the inclusion involving the union follows. Also, for the second inclusion you'll need to show that the union is actually a $\sigma$-algebra (the hint is helpful here) in order to show it contains $\sigma(A).$ – Dave L Renfro Sep 15 '15 at 17:14
• @DaveLRenfro Could you make it strict and full? I am very willing to learn this from you. Thanks for your kind words. – Henry.L Sep 15 '15 at 23:01
• In most "natural situations", each level is a proper subset of the next level (Borel sets in a complete metric space with no isolated points, for example), but of course in sufficiently artificial examples (e.g. finite $\sigma$-algebras) this might not be the case. The proofs I've seen that each level is strictly contained in the next level tend to be a bit technical, however. On the other hand, if by "full" you mean all the sets in the $\sigma$-algebra occur after $\omega_1$ levels, this is fairly straightforward to show using your "Hint". – Dave L Renfro Sep 16 '15 at 15:19
• For some references about these issues, see Is there any good text introducing a part of Borel-hierarchy which is in need in measure theory. – Dave L Renfro Sep 16 '15 at 15:21