55. Sigma-algebras and measurable spaces
§0 defined an event as "any subset of the sample space". For finite and countable spaces that works perfectly. On the real line it fails — and the repair is the foundation of rigorous probability.
Module 9 is optional, and this is the place to decide. What follows is graduate-level real analysis: it goes back and rebuilds §1's foundations rigorously rather than adding tools you will use elsewhere. Nothing in §10 (information theory) or §11 (Monte Carlo) depends on it, and §8's single forward reference — filtrations in the martingales lesson — is explained where it appears. Skip the module and you lose no working technique; read it and you learn why the machinery you have been using is allowed. Both are reasonable choices. It assumes comfort with limits, suprema and countability.
The problem
Try to define a uniform probability on [0,1] where every subset has a probability. Natural requirements:
- P([0,1]) = 1.
- Countable additivity for disjoint sets.
- Translation invariance — shifting a set (mod 1) shouldn't change its probability.
No such P exists.
The counterexample is the Vitali set. Partition [0,1) by the relation x \sim y iff x - y is rational, and use the axiom of choice to pick one representative from each class, forming a set V.
The translates V + q \pmod 1 over rational q \in [0,1) are disjoint and their union is all of [0,1). So
1 = P([0,1)) = \sum_{q \in \mathbb Q \cap [0,1)} P(V + q) = \sum_{q} P(V)
by translation invariance. But a countable sum of a single constant is either 0 (if P(V) = 0) or \infty (if P(V) > 0). Never 1. Contradiction.
The conclusion: we cannot assign probabilities to all subsets. We must restrict to a well-behaved collection — and that collection is a \sigma-algebra.
The definition
A collection \mathcal{F} of subsets of \Omega is a \sigma-algebra if:
- \Omega \in \mathcal{F}
- Closed under complement: A \in \mathcal{F} \implies A^c \in \mathcal{F}
- Closed under countable union: A_1, A_2, \dots \in \mathcal{F} \implies \bigcup_{i=1}^\infty A_i \in \mathcal{F}
From these, \varnothing \in \mathcal F (complement of \Omega) and closure under countable intersection follows by De Morgan.
The pair (\Omega, \mathcal F) is a measurable space, and members of \mathcal F are measurable sets — the events we're allowed to talk about.
Why countable and not finite? Because limits matter. "The sequence converges", "the event happens infinitely often", "the maximum over all time exceeds x" — all are countable combinations, and probability theory would be useless without them.
Why not uncountable? Because that's exactly what the Vitali set rules out. Countable is the largest closure that's consistent.
Examples
The trivial \sigma-algebra: \{\varnothing, \Omega\}. The smallest possible — you can only ask "did anything happen?"
The power set 2^\Omega: all subsets. Fine for countable \Omega; impossible for \mathbb R with translation invariance.
The Borel \sigma-algebra \mathcal B(\mathbb R): the smallest \sigma-algebra containing all open intervals. It contains every set you will ever construct explicitly — open, closed, countable, F_\sigma, G_\delta — and it is the default for the real line.
Non-Borel sets exist, but you cannot write one down without the axiom of choice.
Sigma-algebras as information
This is the interpretation that makes them useful rather than technical.
A \sigma-algebra encodes what you can distinguish.
Roll a die, \Omega = \{1,\dots,6\}:
- \{\varnothing, \Omega\}: you learn nothing.
- \sigma(\{2,4,6\}) = \{\varnothing, \{1,3,5\}, \{2,4,6\}, \Omega\}: you learn the parity, and nothing more. You can answer "was it even?" but not "was it a 4?"
- 2^\Omega: you observe the exact outcome.
A larger \sigma-algebra means more information. That is why a filtration — an increasing family \mathcal F_0 \subseteq \mathcal F_1 \subseteq \cdots — models information accumulating over time, and it is exactly what the martingale definition in §8 was conditioning on.
Random variables, properly defined
§1 said a random variable is a function X : \Omega \to \mathbb R. The full definition adds a condition:
X \text{ is measurable} \iff X^{-1}(B) \in \mathcal F \text{ for every Borel set } B
Equivalently, it suffices that \{\omega : X(\omega) \le x\} \in \mathcal F for every real x.
Why this is exactly the right requirement: to write P(X \le x) at all, the set \{X \le x\} must be an event. Measurability is precisely the condition that makes every probability statement about X meaningful.
The interpretation carries over too: X is measurable with respect to \mathcal F iff knowing the information in \mathcal F determines X. A random variable measurable w.r.t. the parity \sigma-algebra above can only be a function of the parity.
Worked example
Is \mathcal{A} = \{\varnothing, \{1\}, \{2,3\}, \{1,2,3\}\} a \sigma-algebra on \Omega = \{1,2,3\}?
Check each axiom:
- \Omega = \{1,2,3\} \in \mathcal A. ✓
- Complements: \{1\}^c = \{2,3\} \in \mathcal A ✓; \{2,3\}^c = \{1\} \in \mathcal A ✓; \varnothing^c = \Omega ✓.
- Unions: \{1\} \cup \{2,3\} = \Omega \in \mathcal A ✓, and all others are trivial.
Yes. It's the \sigma-algebra generated by \{1\} — the information "was the outcome 1 or not?" You cannot distinguish 2 from 3 with it.
Counterexample: \{\varnothing, \{1\}, \{2\}, \Omega\} is not a \sigma-algebra, because \{1\} \cup \{2\} = \{1,2\} \notin the collection. Adding \{1,2\} forces \{3\} (its complement), and so on, until you reach the full power set.
Doing it in Python
Checking the axioms directly on a finite space:
from itertools import combinations
def is_sigma_algebra(omega, collection):
"""Verify the three axioms on a finite space (countable unions reduce to
finite ones here)."""
sets = [frozenset(s) for s in collection]
omega = frozenset(omega)
if omega not in sets:
return False, "missing Omega"
for s in sets:
if (omega - s) not in sets:
return False, f"complement of {set(s) or '{}'} is missing"
for a, b in combinations(sets, 2):
if (a | b) not in sets:
return False, f"union {set(a) or '{}'} u {set(b) or '{}'} is missing"
return True, "valid"
omega = {1, 2, 3}
candidates = {
"trivial": [set(), {1, 2, 3}],
"generated by 1": [set(), {1}, {2, 3}, {1, 2, 3}],
"power set": [set(), {1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3}],
"broken": [set(), {1}, {2}, {1, 2, 3}],
}
for name, c in candidates.items():
ok, why = is_sigma_algebra(omega, c)
print(f"{name:>16}: {'yes' if ok else 'NO':>3} ({why})")
Generating a \sigma-algebra from a set of events — the closure operation:
from itertools import combinations
def generate(omega, seeds):
"""Smallest sigma-algebra containing `seeds` (finite space)."""
omega = frozenset(omega)
sets = {frozenset(), omega} | {frozenset(s) for s in seeds}
changed = True
while changed:
changed = False
for s in list(sets):
if (omega - s) not in sets:
sets.add(omega - s)
changed = True
for a, b in combinations(list(sets), 2):
if (a | b) not in sets:
sets.add(a | b)
changed = True
return sorted(sets, key=lambda s: (len(s), sorted(s)))
omega = {1, 2, 3, 4, 5, 6}
print("sigma({even}) -- knowing only the parity:")
for s in generate(omega, [{2, 4, 6}]):
print(" ", set(s) if s else "{}")
print("\nsigma({1}, {2}) -- knowing whether it was 1, and whether it was 2:")
gen = generate(omega, [{1}, {2}])
print(f" {len(gen)} sets, e.g.", [set(s) for s in gen[:5]])
Sigma-algebras as information, and measurability:
omega = [1, 2, 3, 4, 5, 6]
# The parity sigma-algebra can only distinguish odd from even
parity_blocks = [{1, 3, 5}, {2, 4, 6}]
def measurable_wrt(X, blocks):
"""X is measurable iff it is CONSTANT on each indistinguishable block."""
return all(len({X(w) for w in block}) == 1 for block in blocks)
candidates = {
"X = 1 if even else 0": lambda w: 1 if w % 2 == 0 else 0,
"X = the roll itself": lambda w: w,
"X = 0 always": lambda w: 0,
"X = 1 if w > 3 else 0": lambda w: 1 if w > 3 else 0,
}
for name, X in candidates.items():
print(f"{name:>24}: measurable w.r.t. parity? "
f"{measurable_wrt(X, parity_blocks)}")
print("\nOnly functions of the parity are measurable -- you cannot compute")
print("something you cannot observe.")
A filtration — information growing over time:
from itertools import product
# Two coin flips. What can you distinguish after each flip?
omega = list(product("HT", repeat=2))
def blocks_after(k):
"""Outcomes are indistinguishable if their first k flips agree."""
groups = {}
for w in omega:
groups.setdefault(w[:k], []).append("".join(w))
return list(groups.values())
for k in (0, 1, 2):
print(f"after {k} flip(s): {blocks_after(k)}")
print("\nThe partition gets finer -- F_0 ⊆ F_1 ⊆ F_2. That is a filtration,")
print("and it is what a martingale conditions on.")
Your turn
1. Is \{\varnothing, \{1,2\}, \{3,4\}, \{1,2,3,4\}\} a \sigma-algebra on \{1,2,3,4\}?
2. Why must a \sigma-algebra be closed under countable unions rather than just finite ones?
3. What does it mean for a random variable to be measurable with respect to the trivial \sigma-algebra \{\varnothing, \Omega\}?
Solutions
1. Yes.
- \Omega = \{1,2,3,4\} is present. ✓
- Complements: \{1,2\}^c = \{3,4\} ✓, \{3,4\}^c = \{1,2\} ✓, \varnothing^c = \Omega ✓.
- Unions: \{1,2\} \cup \{3,4\} = \Omega ✓; everything else is trivial.
It's the \sigma-algebra generated by the partition \{\{1,2\}, \{3,4\}\} — you can tell which pair the outcome fell in, but not which element of the pair.
2. Because probability theory is fundamentally about limits, and limits are countable operations.
Events like these are all countable combinations:
\{X_n \to X\}, \qquad \{A_n \text{ occurs infinitely often}\} = \bigcap_{n}\bigcup_{k \ge n}A_k, \qquad \left\{\sup_n X_n > c\right\} = \bigcup_n \{X_n > c\}
With only finite closure, none of these would be guaranteed to be events, and every limit theorem in §3 would be unstatable — you couldn't even write down "the sample mean converges".
Countable additivity is also what makes P(\varnothing) = 0 follow from continuity, and what forces the Vitali contradiction above. It is the exact strength needed: strong enough for analysis, weak enough to be consistent.
3. It means X is constant.
Measurability requires \{X \le x\} \in \{\varnothing, \Omega\} for every x — so for each x, either no outcome has X(\omega) \le x or every outcome does. There's no way to have some outcomes above a threshold and some below, which is only possible if X takes a single value.
The interpretation is exact: the trivial \sigma-algebra carries no information, and the only quantities you can compute from no information are constants.
This is the degenerate end of a general principle used constantly in §8: E[X \mid \mathcal F] is \mathcal F-measurable, so conditioning on the trivial \sigma-algebra gives E[X \mid \{\varnothing,\Omega\}] = E[X] — a constant, as it must be.
Check yourself in code
Write a checker for the \sigma-algebra axioms and use it to classify four candidate collections on \{1,2,3\}.
Print exactly this:
trivial: True
generated by 1: True
power set: True
broken: False
A collection is valid if it contains \Omega, is closed under complement, and is closed under pairwise union (which suffices on a finite space).
from itertools import combinations
def is_sigma_algebra(omega, collection):
sets = [frozenset(s) for s in collection]
omega = frozenset(omega)
if omega not in sets:
return False
# Check closure under complement and under pairwise union.
return True # replace this
omega = {1, 2, 3}
candidates = {
"trivial": [set(), {1, 2, 3}],
"generated by 1": [set(), {1}, {2, 3}, {1, 2, 3}],
"power set": [set(), {1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3}],
"broken": [set(), {1}, {2}, {1, 2, 3}],
}
for name, c in candidates.items():
print(f"{name}: {is_sigma_algebra(omega, c)}")
from itertools import combinations
def is_sigma_algebra(omega, collection):
sets = [frozenset(s) for s in collection]
omega = frozenset(omega)
if omega not in sets:
return False
if any((omega - s) not in sets for s in sets):
return False
if any((a | b) not in sets for a, b in combinations(sets, 2)):
return False
return True
omega = {1, 2, 3}
candidates = {
"trivial": [set(), {1, 2, 3}],
"generated by 1": [set(), {1}, {2, 3}, {1, 2, 3}],
"power set": [set(), {1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3}],
"broken": [set(), {1}, {2}, {1, 2, 3}],
}
for name, c in candidates.items():
print(f"{name}: {is_sigma_algebra(omega, c)}")
Not every subset of the real line can carry a probability — the Vitali set proves it. A \sigma-algebra is the well-behaved collection we restrict to: closed under complement and countable union, so that limits remain events. It doubles as a model of information, which is why filtrations describe knowledge accumulating over time and why measurability means "computable from what you can observe".
Next: what a probability measure actually is, once the events are pinned down.