σ-algebras and Borel sets

The lesson "Measuring the size of sets" defined a measure as a rule that gives a size to every set of a suitable collection of sets, and left open which collection that is. This lesson answers. The answer is not simply "all sets", for two reasons. The first is about knowledge: an observer who has only partial information about an outcome can decide membership in some sets and not in others, and a size makes sense only for sets whose membership can be decided. The second is about mathematics: on the interval $[0, 1)$ there is a set to which no length can be given without breaking the rules of a measure. The collections that avoid both problems are called σ-algebras. The lesson defines them, shows that on a finite set they are the same thing as splitting the set into blocks, builds the Borel sets, the σ-algebra on which length will live, and ends with Vitali's set, the reason length cannot be given to every set.

Events as answerable questions

A die is rolled behind a screen, so the set of possible outcomes is $\Omega = \{1, 2, 3, 4, 5, 6\}$ and nobody sees which face came up. Two observers are told something about the result. Observer P is told only whether the face is even or odd. Observer S is told only whether the face is at most 2.

Afterwards, P can answer the question "was the face even?", which asks whether the outcome lies in $\{2, 4, 6\}$, and the question "was it odd?", which asks about $\{1, 3, 5\}$. P cannot answer "was it a 4?", because the parity does not settle it. So the sets that P can decide are exactly four: the empty set (the question "is the face one of no faces?", always answered no), $\{2, 4, 6\}$, $\{1, 3, 5\}$, and $\Omega$ itself (always answered yes). For S the four sets are $\emptyset$, $\{1, 2\}$, $\{3, 4, 5, 6\}$ and $\Omega$. In this lesson an event is a set of outcomes whose membership an observer can decide.

These collections have a shape. If you can answer "is the outcome in $A$?", you can answer "is it outside $A$?" by flipping the answer. If you can answer the questions about $A$ and about $B$, you can answer "is it in $A$ or in $B$?". So the collection $\{\emptyset, \{1, 2\}, \{2, 3, 4\}, \Omega\}$ cannot be everything that an observer decides: flipping the answer about $\{1, 2\}$ gives $\{3, 4, 5, 6\}$, and combining the two answers gives $\{1, 2, 3, 4\}$, and neither is in the collection. A believable list of events has to be closed under these operations, and the next section turns this closure into a definition.

σ-algebras

Let $\Omega$ be the set of all outcomes and let $\mathcal{F}$ be a collection of subsets of $\Omega$. It is a σ-algebra on $\Omega$ if it has three properties:

• $\Omega \in \mathcal{F}$. The question "is the outcome somewhere in $\Omega$?" can be answered; the answer is always yes.
• If $A \in \mathcal{F}$, then the complement $A^c = \Omega \setminus A$ is in $\mathcal{F}$. If you can answer a question, you can answer its opposite.
• If $A_1, A_2, A_3, \ldots \in \mathcal{F}$, then $A_1 \cup A_2 \cup A_3 \cup \cdots \in \mathcal{F}$. If you can answer every question of a countable list, you can answer "is the answer yes to at least one of them?".

The sets of $\mathcal{F}$ are called measurable sets or events, and the letter σ in the name refers to the countable unions in the third property. P's four sets form a σ-algebra: the complement of $\{2, 4, 6\}$ is $\{1, 3, 5\}$, the complement of $\Omega$ is $\emptyset$, and every union of two or more of the four sets is again one of the four. The same holds for S. The collection $\{\emptyset, \{1, 2\}, \{2, 3, 4\}, \Omega\}$ of the previous section is not a σ-algebra, since it contains $\{1, 2\}$ but not its complement $\{3, 4, 5, 6\}$.

Each property rules out an inconsistency. Without the first, no event would say that something happened. Without the second, an observer could know that the face is in $\{1, 2\}$ yet be unable to say that it is not. Without the third, answering infinitely many questions would produce no answer.

Consequences of the three properties

A few more closure properties follow at once, and each needs only a line.

• The empty set is an event, because $\emptyset = \Omega^c$ is the complement of the first event.
• A union of finitely many events is an event: to form $A \cup B$, use the third property on the list $A, B, \emptyset, \emptyset, \ldots$.
• A countable intersection of events is an event. This is De Morgan's rule, which turns an intersection into a complement of a union of complements:

The right side is built from complements and one countable union, so it lies in $\mathcal{F}$. Two sets give that $A \cap B$ is an event, and then the difference $A \setminus B = A \cap B^c$ is one too. In words: every logical combination of countably many answerable questions is answerable.

Countable unions and algebras

Why countable unions and not just finite ones? A collection with only the first two properties and closure under finite unions is called an algebra of sets. Algebras are too small for the questions that matter, as two examples show.

The first example is a die rolled again and again without end. Let $A_n$ be the event "roll number $n$ shows a six". Each $A_n$ is a question about a single roll. The question "does a six ever appear?" is the union $A_1 \cup A_2 \cup A_3 \cup \cdots$ of infinitely many of them, and no finite union can express it: after any finite number of rolls the answer may still be undecided. Whoever wants to attach a size to "a six eventually appears" needs the countable union.

The second example lives on $[0, 1]$. Let $\mathcal{A}$ be the collection of all finite unions of intervals of $[0, 1]$, where the intervals may be open, closed or half-open, and a single point counts as a degenerate interval. The complement of a finite union of intervals is again one, so $\mathcal{A}$ is an algebra. It contains every single point $\{q\}$. But it does not contain the set $\mathbb{Q} \cap [0, 1]$ of rational numbers, although this set is the countable union $\{q_1\} \cup \{q_2\} \cup \cdots$ of events of $\mathcal{A}$. If a finite union of intervals equalled the rationals, no interval in it could have positive length, because every such interval contains irrational numbers. The union would consist of finitely many single points, yet there are infinitely many rationals.

There is also a reason from the definition of a measure: countable additivity, $\mu(A_1 \cup A_2 \cup \cdots) = \mu(A_1) + \mu(A_2) + \cdots$ for disjoint sets, has a meaning only if the countable union is itself in the domain of $\mu$.

Measurable spaces and measure spaces

A set $\Omega$ together with a σ-algebra $\mathcal{F}$ on it is a measurable space, written $(\Omega, \mathcal{F})$. It fixes which sets may receive a size without yet giving any size. Adding a measure $\mu$, a function defined on the sets of $\mathcal{F}$ with the rules of "Measuring the size of sets", gives a measure space $(\Omega, \mathcal{F}, \mu)$. The sets of $\mathcal{F}$ are the measurable sets; a set outside $\mathcal{F}$ is not measured at all, which is different from having size zero.

Every set $\Omega$ has two extreme σ-algebras. The smallest is the trivial σ-algebra $\{\emptyset, \Omega\}$: an observer who is told nothing can decide only the two questions that every outcome answers in the same way. The largest is the power set $2^{\Omega}$ of all subsets: an observer who sees the outcome exactly can decide every question. For the die, the power set has $2^6 = 64$ sets. Everything else lies between the two.

Take counting measure on the die, $\mu(A) =$ the number of faces in $A$. On the power set, $\mu(\{2\}) = 1$. On P's σ-algebra, $\{2\}$ is not an event, so $\mu(\{2\})$ has no value, while $\mu(\{2, 4, 6\}) = 3$ keeps its value. Restricting a measure to a smaller σ-algebra keeps its values and drops the sets that cannot be decided.

A measure space has three parts: the outcomes $\Omega$, the σ-algebra $\mathcal{F}$ of sets that may be measured, and the measure $\mu$ on $\mathcal{F}$. Changing the σ-algebra changes the question "what has a size", not the sizes of the sets that remain.

Finite σ-algebras and partitions

When $\Omega$ is finite, a σ-algebra can be described by a list of blocks. Look at P again: it cannot tell 1 from 3 or from 5, and cannot tell 2 from 4 or from 6. It sees the die as two blocks, $\{1, 3, 5\}$ and $\{2, 4, 6\}$, and every event it can decide is a union of blocks: none of them, the first, the second, or both. A split of $\Omega$ into disjoint non-empty blocks that together cover $\Omega$ is a partition.

The blocks that a finite σ-algebra cannot cut into smaller events are its atoms. Formally, an atom is a non-empty event that has no non-empty event as a proper subset. Three facts hold for every σ-algebra $\mathcal{F}$ on a finite set, and the first one is proved in a few lines.

• The atoms form a partition of $\Omega$. For an outcome $\omega$, let $A_\omega$ be the intersection of all events that contain $\omega$. There are finitely many events, so $A_\omega$ is an event, the smallest one containing $\omega$. Suppose $x \in A_\omega$. Then $A_x \subseteq A_\omega$, because $A_\omega$ is an event containing $x$. Also $\omega \in A_x$: otherwise $A_\omega \setminus A_x$ would be an event that contains $\omega$ but not $x$, smaller than $A_\omega$. So $A_\omega \subseteq A_x$, and the two sets are equal. Any two of the sets $A_\omega$ are therefore equal or disjoint, and they cover $\Omega$. Each is an atom, since a smaller event inside $A_\omega$ would contain some $y$, and then $A_y = A_\omega$ would lie inside it; and every atom is one of them.
• Every event is a union of atoms: an event $A$ equals the union of the sets $A_\omega$ over its outcomes $\omega \in A$.
• Conversely, every partition gives a σ-algebra, namely all unions of its blocks (the empty union included). If there are $k$ atoms, each of them is either in a given event or not, so there are $2^k$ events.

So on a finite set, σ-algebras and partitions are the same thing seen two ways. P has $k = 2$ atoms and $2^2 = 4$ events; S has the atoms $\{1, 2\}$ and $\{3, 4, 5, 6\}$ and also 4 events. The trivial σ-algebra has one atom, $\Omega$, and $2^1 = 2$ events; the power set of the die has six atoms, the single faces, and $2^6 = 64$ events. The number of different σ-algebras on the die equals the number of ways to partition six faces, which is 203.

Suppose a third observer hears both reports. Faces 1 and 2 differ from each other (odd versus even) and from the rest (small versus large), faces 3 and 5 are both odd and large, and faces 4 and 6 are both even and large. The atoms are $\{1\}$, $\{2\}$, $\{3, 5\}$ and $\{4, 6\}$, giving $2^4 = 16$ events, among them every event of P and of S. More information means a finer partition and a larger σ-algebra.

Generated σ-algebras

In practice one rarely lists a whole σ-algebra. One names a few sets that must be events and asks for the smallest σ-algebra that contains them. Given a collection $\mathcal{C}$ of subsets of $\Omega$, the σ-algebra generated by $\mathcal{C}$, written $\sigma(\mathcal{C})$, is the smallest σ-algebra on $\Omega$ that contains every set of $\mathcal{C}$. In the language of observers, $\sigma(\mathcal{C})$ is everything that can be decided by someone who can decide exactly the questions in $\mathcal{C}$, and is therefore forced to decide everything built from them.

"Smallest" needs a definition that works also when $\Omega$ is infinite, where one cannot just keep adding complements and unions until nothing new appears. The definition is an intersection:

The family being intersected is not empty, since the power set contains $\mathcal{C}$. An intersection of σ-algebras is a σ-algebra: every member contains $\Omega$; if $A$ is in every member, so is $A^c$; and if each $A_n$ is in every member, so is their countable union. The result contains $\mathcal{C}$ and lies inside every other σ-algebra that contains $\mathcal{C}$, which is what smallest means.

On a finite $\Omega$ the atoms of $\sigma(\mathcal{C})$ can be found directly. Give every outcome a signature, its list of yes/no answers to the generating sets: "is it in the first set? is it in the second?". Outcomes with the same signature cannot be told apart by anything built from the generators, and outcomes with different signatures can. So the atoms of $\sigma(\mathcal{C})$ are the groups of outcomes with equal signatures, and the number of events is $2^k$ for $k$ groups.

The figure does this for the die. The faces on top are coloured and numbered by atom. Below are up to three rows, G1, G2 and G3, of cells: press a cell to put a face into that generating event, and a row with no pressed cell is ignored. The default, G1 $= \{1, 2\}$ and G2 $= \{2, 3, 4\}$, gives the atoms $\{1\}$, $\{2\}$, $\{3, 4\}$ and $\{5, 6\}$: $k = 4$ and 16 events. "Both observers" shows the atoms $\{1\}$, $\{2\}$, $\{3, 5\}$ and $\{4, 6\}$ of the previous section. "Every face" shows that three well-chosen questions already separate all six faces: 6 atoms and 64 events.

Borel sets

On the real line there are no atoms to list, so the σ-algebra is defined by its generators. The Borel σ-algebra $\mathcal{B}(\mathbb{R})$ is the σ-algebra generated by the open intervals $(a, b)$ with $a < b$, and its members are the Borel sets. This is the smallest σ-algebra that contains all intervals, so any measure of length must be defined on at least these sets.

The choice of generators is flexible. The same σ-algebra is generated by the half-open intervals $(a, b]$, by the half-lines $(-\infty, x]$, or by all open sets. Three derivations show why, each using only the three properties of a σ-algebra.

• From half-lines to half-open intervals: $(a, b] = (-\infty, b] \setminus (-\infty, a]$, a difference of two half-lines.
• From half-open intervals to open intervals: $(a, b) = \bigcup_{n \ge 1} (a, b - \tfrac1n]$, a countable union in which the terms with $b - \tfrac1n \le a$ are empty.
• From open intervals to every open set: let $U$ be open. Each point $x$ of $U$ has an interval around it that lies inside $U$, and the endpoints can be moved to rational numbers without leaving $U$ or losing $x$. There are only countably many intervals with rational endpoints, so $U$ is a countable union of them.

Hence every open set is Borel, and so is every closed set, as the complement of an open set. A single point is Borel as well, because $\{x\} = \bigcap_n (x - \tfrac1n, x]$ is a countable intersection of half-open intervals. Taking countable unions of points, every countable set is Borel, in particular the rational numbers $\mathbb{Q}$, and the irrational numbers are Borel as the complement of $\mathbb{Q}$. The Cantor set of the next lesson, "Lebesgue measure and null sets", is the intersection of countably many sets $C_n$, each a finite union of closed intervals, so it is Borel too.

Every set you can write down by a formula or a limiting construction is Borel. Starting from intervals and applying countable unions and complements, in any order and any number of times, stays inside the Borel sets.

Not every subset of the real line is Borel. A counting argument shows this without naming a set: there are as many Borel sets as real numbers, but far more subsets of the line. The next section gives a set that cannot get a length at all, and the next lesson shows that Borel sets can.

Sets without a length

Suppose length, $\lambda$, were defined for every subset of $[0, 1)$, with the three properties that any sensible length has: the interval $[0, 1)$ has length 1; length is countably additive; and shifting a set around the circle does not change its length. Here the circle means $[0, 1)$ with 1 glued to 0: for $r \in [0, 1)$ let $x \oplus r$ be $x + r$ if that is below 1 and $x + r - 1$ otherwise. For a set $V$ write $V_r = \{v \oplus r : v \in V\}$. Cut $V$ at the point $1 - r$: the part below it moves $r$ to the right, the part above it moves $1 - r$ to the left, and a plain shift changes no length, so $\lambda(V_r) = \lambda(V)$. Vitali's argument shows that these assumptions contradict each other.

1. Call two numbers $x, y \in [0, 1)$ equivalent when $x - y$ is a rational number. This splits $[0, 1)$ into classes; the class of $x$ consists of all numbers reachable from $x$ by adding a rational number and wrapping around. Each class is countable and lies densely in $[0, 1)$, and there are uncountably many classes.
2. Choose exactly one number from each class and collect the chosen numbers in a set $V$. This step uses the axiom of choice, because there is no formula that says which number to pick in each class.
3. For every rational $r \in [0, 1)$ form the shifted copy $V_r$. There are countably many such $r$.
4. The copies are pairwise disjoint. If $v \oplus r = w \oplus s$ for $v, w \in V$, then $v - w$ is rational, so $v$ and $w$ are equivalent. Only one number was chosen from a class, so $v = w$, and then $r = s$.
5. The copies cover $[0, 1)$. Take any $x$. It is equivalent to the chosen number $v$ of its class, so $x = v \oplus r$ for some rational $r$, which puts $x$ in $V_r$.
6. Countable additivity now gives $1 = \lambda([0, 1)) = \sum_r \lambda(V_r) = \lambda(V) + \lambda(V) + \lambda(V) + \cdots$, with every term equal to the same number $a = \lambda(V)$. If $a = 0$, the sum is 0. If $a > 0$, the sum is infinite. Neither equals 1.

The contradiction lies in the assumptions, not in $V$: no length can be assigned to every subset of $[0, 1)$. Vitali's set has no explicit description and cannot be built without the axiom of choice, so no calculation will meet it. But it exists in the framework that all of measure theory uses, so something has to be given up.

What to give up

The argument used four ingredients: length is defined on every set, it is countably additive, it is unchanged by shifts, and $[0, 1)$ has length 1. The last one cannot usefully be dropped: if $[0, 1)$ had length 0 or $\infty$, the contradiction would disappear, but so would any use of length. That leaves three possible repairs, one for each of the other ingredients.

• Give up countable additivity and keep only finite additivity. A finitely additive, shift-invariant length defined on all bounded subsets of the line does exist, by a theorem of Banach, but it behaves badly under limits: the unions of the first $n$ shifted copies $V_r$ of Vitali's set increase to $[0, 1)$, yet each union has length 0, because $n$ disjoint copies of equal length fit into $[0, 1)$ for every $n$. Almost every later theorem of this track depends on such limits.
• Give up shift invariance. A set could then have a different size at a different place, which is not what the word length means, and every set of positive size could be moved to change it.
• Give up measuring every set. Keep a countably additive, shift-invariant length, and define it only on a σ-algebra that is large enough to contain everything of interest but too small to contain Vitali's set.

Measure theory takes the third option. The cost is small: every set described by a formula or a limiting process is Borel, and the next lesson builds a length with all the desired properties on the Borel sets. The gain is what the rest of the track uses: limits of sets behave well, and the rules of "Measuring the size of sets", continuity included, hold on the whole domain.

Choosing the σ-algebra

Which σ-algebra to use depends on the space and the purpose. For a finite set such as the die, the usual choice is the power set: all $2^6 = 64$ subsets are events. For the real line, or an interval of it, the choice is the Borel σ-algebra; on $[0, 1]$ these are the Borel sets that lie inside $[0, 1]$. The next lesson adds all subsets of sets of length zero, which changes no size.

On one set, different σ-algebras describe different observers. The die has 203 of them, from the trivial one that knows nothing to the power set that knows everything, with the partial reports of P and S and their combinations in between. Choosing $\mathcal{F}$ is choosing what the model can talk about: too small a σ-algebra cannot express what an observer knows, and too large a one may demand sizes for sets that have none.

Summary

• An event is a set whose membership can be decided; a σ-algebra $\mathcal{F}$ is a collection of events containing $\Omega$ and closed under complements and countable unions, hence also under countable intersections and differences.
• A measurable space $(\Omega, \mathcal{F})$ says which sets may get a size; a measure space $(\Omega, \mathcal{F}, \mu)$ adds the sizes. The extremes are $\{\emptyset, \Omega\}$ and the power set.
• On a finite set a σ-algebra is a partition into atoms; $k$ atoms give $2^k$ events, and a finer partition means more information. The σ-algebra $\sigma(\mathcal{C})$ generated by $\mathcal{C}$ is the smallest one containing $\mathcal{C}$, the intersection of all σ-algebras that do.
• The Borel σ-algebra $\mathcal{B}(\mathbb{R})$ is generated by the intervals, the half-lines or the open sets. It contains points, countable sets, open and closed sets and the Cantor set, though not every subset of the line.
• Vitali's set, one representative per class of numbers differing by rationals, cannot get a length without breaking countable additivity or shift invariance, so measure theory measures only the sets of a σ-algebra.