Week 1: Set Theory and the Axioms of Probability

Reading: Casella & Berger (C&B) §§1.1–1.2.2

Lecture	Date	Topics	C&B
1.1	Tue. Sep. 29	Sample spaces; events; set operations; infinite unions and intersections; disjoint sets and partitions	§1.1
1.2	Thu. Oct. 1	Sigma algebras; the Kolmogorov axioms; constructing probability functions; the calculus of probabilities; Bonferroni and Boole	§§1.2.1–1.2.2

Notation. $S$ is the sample space, $A, B, C, A_1, A_2, \dots$ are events (subsets of $S$), $\emptyset$ is the empty set, $A^c$ is the complement of $A$, and $\mathcal{B}$ is a sigma algebra.

Set Theory

Way of thinking. Always start from definitions

Probability theory is the foundation of statistics, and it is built on set theory. The first step in modeling any random experiment is to write down what can happen.

1. Sample spaces

Definition 1.1.1. The set $S$ of all possible outcomes of a particular experiment is called the sample space for the experiment.

Examples.

Experiment	Sample space	Type
Toss a coin once	$S = \lbrace H, T \rbrace$	finite
Toss a coin twice	$S = \lbrace HH, HT, TH, TT \rbrace$	finite
Roll a die	$S = \lbrace 1, 2, 3, 4, 5, 6 \rbrace$	finite
Reported SAT score (multiples of 10)	$S = \lbrace 200, 210, \dots, 800 \rbrace$	finite
Number of insect-damaged leaves on a plant	$S = \lbrace 0, 1, 2, \dots \rbrace$	countably infinite
Lifetime of a light bulb, in hours	$S = [0, \infty)$	uncountable
Reaction time to a stimulus	$S = (0, \infty)$	uncountable

Countable vs. uncountable. A sample space is countable if its elements can be put into one-to-one correspondence with a subset of the integers. Otherwise it is uncountable. Every finite set is countable.

$\lbrace 0, 1, 2, \dots \rbrace$ is countable. So is $\mathbb{Q}$, the set of rational numbers.
Any interval $(a, b)$ with $a < b$ is uncountable (Cantor’s diagonal argument).

Why it matters. Whether $S$ is countable determines how we can assign probabilities. On a countable $S$ we can assign a probability to each outcome and add them up. On an uncountable $S$ every single outcome typically has probability 0, and we need a different approach (densities, Week 3). If reaction time is recorded to the nearest second, $S = \lbrace 0, 1, 2, \dots \rbrace$ is countable. Continuous models are an idealization, but a very convenient one.

2. Events

Definition 1.1.2. An event is any collection of possible outcomes of an experiment, that is, any subset of $S$ (including $S$ itself).

We say the event $A$ occurs if the outcome of the experiment is in $A$.

Example (two coin tosses). With $S = \lbrace HH, HT, TH, TT \rbrace$:

$A$ = “at least one head” = $\lbrace HH, HT, TH \rbrace$
$B$ = “exactly one head” = $\lbrace HT, TH \rbrace$
$C$ = “two heads” = $\lbrace HH \rbrace$

Note that $B \subset A$ and $C \subset A$: whenever $B$ occurs, $A$ occurs.

Containment and equality.

\[A \subset B \iff (x \in A \Rightarrow x \in B), \qquad\qquad A = B \iff A \subset B \text{ and } B \subset A.\]

The second statement is the standard way to prove that two sets are equal: show each one is contained in the other.

3. Elementary set operations

For events $A$ and $B$ in $S$:

Union: $A \cup B = \lbrace x : x \in A \text{ or } x \in B \rbrace$ (“$A$ or $B$ or both occurs”).
Intersection: $A \cap B = \lbrace x : x \in A \text{ and } x \in B \rbrace$ (“both $A$ and $B$ occur”).
Complement: $A^c = \lbrace x \in S : x \notin A \rbrace$ (“$A$ does not occur”).
Difference: $A \setminus B = A \cap B^c$ (“$A$ occurs but $B$ does not”).
Empty set: $\emptyset$, the set with no elements. Note $S^c = \emptyset$ and $\emptyset^c = S$.

Example 1.1.3 (card suits). Draw a card and note its suit: $S = \lbrace C, D, H, S \rbrace$ (clubs, diamonds, hearts, spades). Let $A = \lbrace C, D \rbrace$ and $B = \lbrace D, H, S \rbrace$. Then

\[A \cup B = \lbrace C, D, H, S \rbrace = S, \qquad A \cap B = \lbrace D \rbrace, \qquad A^c = \lbrace H, S \rbrace, \qquad (A \cup B)^c = \emptyset.\]

Example (die). $S = \lbrace 1, \dots, 6 \rbrace$, $A = \lbrace 1, 3, 5 \rbrace$ (odd), $B = \lbrace 1, 2, 3 \rbrace$. Then $A \cup B = \lbrace 1, 2, 3, 5 \rbrace$, $A \cap B = \lbrace 1, 3 \rbrace$, $A^c = \lbrace 2, 4, 6 \rbrace$, and $A \setminus B = \lbrace 5 \rbrace$.

Basic facts (each follows directly from the definitions):

$A \cap B \subset A \subset A \cup B$ and $A \cap B \subset B \subset A \cup B$.
If $A \subset B$, then $A \cap B = A$ and $A \cup B = B$.
$A \cup A^c = S$, $A \cap A^c = \emptyset$, $(A^c)^c = A$.
$A \cup \emptyset = A$, $A \cap \emptyset = \emptyset$, $A \cup S = S$, $A \cap S = A$.

4. Algebra of set operations

Theorem 1.1.4. For any three events $A$, $B$, and $C$ defined on a sample space $S$:

Commutativity: $A \cup B = B \cup A$ and $A \cap B = B \cap A$.
Associativity: $A \cup (B \cup C) = (A \cup B) \cup C$ and $A \cap (B \cap C) = (A \cap B) \cap C$.
Distributive laws: $A \cap (B \cup C) = (A \cap B) \cup (A \cap C)$ and $A \cup (B \cap C) = (A \cup B) \cap (A \cup C)$.
DeMorgan’s laws: $(A \cup B)^c = A^c \cap B^c$ and $(A \cap B)^c = A^c \cup B^c$.

Venn diagrams are good for seeing why these hold, but a Venn diagram is not a proof. To prove two sets are equal, show each contains the other.

Proof of the first distributive law.

($\subset$) Let $x \in A \cap (B \cup C)$. Then $x \in A$ and $x \in B \cup C$, so $x \in B$ or $x \in C$.

If $x \in B$, then $x \in A \cap B$.
If $x \in C$, then $x \in A \cap C$.

Either way, $x \in (A \cap B) \cup (A \cap C)$.

($\supset$) Let $x \in (A \cap B) \cup (A \cap C)$.

If $x \in A \cap B$, then $x \in A$, and $x \in B \subset B \cup C$, so $x \in A \cap (B \cup C)$.
If $x \in A \cap C$, the same argument applies with $C$ in place of $B$.

Both containments hold, so the sets are equal. $\square$

Proof of the first DeMorgan law. For any $x \in S$,

\[x \in (A \cup B)^c \iff x \notin A \cup B \iff x \notin A \text{ and } x \notin B \iff x \in A^c \cap B^c. \qquad \square\]

Check (die example). With $A = \lbrace 1, 3, 5 \rbrace$ and $B = \lbrace 1, 2, 3 \rbrace$: $(A \cap B)^c = \lbrace 1, 3 \rbrace^c = \lbrace 2, 4, 5, 6 \rbrace$, and $A^c \cup B^c = \lbrace 2, 4, 6 \rbrace \cup \lbrace 4, 5, 6 \rbrace = \lbrace 2, 4, 5, 6 \rbrace$. ✓

The remaining parts are Exercise 1.3.

5. Countable and arbitrary unions and intersections

For a sequence of sets $A_1, A_2, A_3, \dots$ in $S$:

\[\bigcup_{i=1}^{\infty} A_i = \lbrace x \in S : x \in A_i \text{ for some } i \rbrace, \qquad \bigcap_{i=1}^{\infty} A_i = \lbrace x \in S : x \in A_i \text{ for all } i \rbrace.\]

Example. Let $S = (0, 1]$ and $A_i = [1/i, 1]$. The sets increase: $A_1 = \lbrace 1 \rbrace \subset A_2 = [1/2, 1] \subset \cdots$. Then

\[\bigcup_{i=1}^{\infty} [1/i, 1] = (0, 1], \qquad \bigcap_{i=1}^{\infty} [1/i, 1] = \lbrace 1 \rbrace.\]

Why the union is all of $(0, 1]$: for any $x \in (0, 1]$ we can choose an integer $i \ge 1/x$, so $1/i \le x$ and $x \in A_i$. Note that $0$ is never reached, even though $1/i \to 0$.

Example. Let $S = [0, \infty)$ and $A_i = [i, i+1)$ for $i = 0, 1, 2, \dots$. Then $\bigcup_{i=0}^{\infty} A_i = [0, \infty) = S$, while $A_0 \cap A_1 = [0, 1) \cap [1, 2) = \emptyset$, so $\bigcap_{i=0}^{\infty} A_i = \emptyset$.

Arbitrary index sets. If $\Gamma$ is any index set, possibly uncountable,

\[\bigcup_{a \in \Gamma} A_a = \lbrace x \in S : x \in A_a \text{ for some } a \in \Gamma \rbrace, \qquad \bigcap_{a \in \Gamma} A_a = \lbrace x \in S : x \in A_a \text{ for all } a \in \Gamma \rbrace.\]

For example, with $\Gamma = (0, \infty)$ and $A_a = (0, a]$, we get $\bigcup_{a \in \Gamma} A_a = (0, \infty)$.

General DeMorgan’s laws (Exercise 1.9):

\[\Big( \bigcup_{a \in \Gamma} A_a \Big)^c = \bigcap_{a \in \Gamma} A_a^c, \qquad \Big( \bigcap_{a \in \Gamma} A_a \Big)^c = \bigcup_{a \in \Gamma} A_a^c.\]

6. Disjoint sets and partitions

Definition 1.1.5. Two events $A$ and $B$ are disjoint (or mutually exclusive) if $A \cap B = \emptyset$. The events $A_1, A_2, \dots$ are pairwise disjoint if $A_i \cap A_j = \emptyset$ for all $i \ne j$.

Definition 1.1.6. If $A_1, A_2, \dots$ are pairwise disjoint and $\bigcup_{i=1}^{\infty} A_i = S$, then the collection $A_1, A_2, \dots$ forms a partition of $S$.

Examples.

$\lbrace A, A^c \rbrace$ is a partition of $S$ for any event $A$.
$A_i = [i, i+1)$, $i = 0, 1, 2, \dots$, is a partition of $[0, \infty)$.
For a die, $\lbrace 1, 2 \rbrace, \lbrace 3, 4 \rbrace, \lbrace 5, 6 \rbrace$ is a partition of $S$.

Partitions let us break a hard problem into small, non-overlapping pieces. This idea returns in Theorem 1.2.11 on Thursday and in the law of total probability in Week 2.

Check your understanding.

Is $\lbrace 1, 3 \rbrace, \lbrace 2, 3 \rbrace, \lbrace 4, 5, 6 \rbrace$ a partition of $\lbrace 1, \dots, 6 \rbrace$? Why or why not?
Show that for any $A$ and $B$, the sets $A \cap B$, $A \cap B^c$, $A^c \cap B$, and $A^c \cap B^c$ form a partition of $S$.
Compute $\bigcap_{n=1}^{\infty} (0, 1/n)$ and $\bigcap_{n=1}^{\infty} [0, 1/n)$.

Axiomatic Foundations and the Calculus of Probabilities

Way of thinking. Probability is a function on sets that obeys three rules, and everything else is derived from those rules.

1. Interpretations vs. axioms

What does $P(A) = 0.3$ mean?

Frequentist: in many repetitions of the experiment, $A$ occurs about 30% of the time.
Subjective (Bayesian): a degree of belief that $A$ will occur.
Symmetry / classical: for a finite $S$ with equally likely outcomes, $P(A) = N(A)/N(S)$, where $N(\cdot)$ counts outcomes.

The axiomatic approach sidesteps the question. A probability is any function that satisfies a small set of rules (axioms). Interpretation is a separate matter. Everything else we prove in this course follows from the axioms.

2. Sigma algebras

We want to define $P(A)$ for events $A$. The natural choice would be to allow every subset of $S$. For countable $S$ that works. For uncountable $S$ such as $\mathbb{R}$, it can be proved that no reasonable “length-like” probability can be defined on all subsets. So we restrict the domain of $P$ to a collection of subsets with good closure properties.

Definition 1.2.1. A collection $\mathcal{B}$ of subsets of $S$ is called a sigma algebra (or Borel field) if it satisfies:

$\emptyset \in \mathcal{B}$.
If $A \in \mathcal{B}$, then $A^c \in \mathcal{B}$ (closed under complementation).
If $A_1, A_2, \dots \in \mathcal{B}$, then $\bigcup_{i=1}^{\infty} A_i \in \mathcal{B}$ (closed under countable unions).

Consequences.

$S \in \mathcal{B}$: by (1) and (2), $S = \emptyset^c \in \mathcal{B}$.
Closed under countable intersections: if $A_1, A_2, \dots \in \mathcal{B}$, then $A_i^c \in \mathcal{B}$ by (2), so $\bigcup_i A_i^c \in \mathcal{B}$ by (3). By DeMorgan,
\[\bigcap_{i=1}^{\infty} A_i = \Big( \bigcup_{i=1}^{\infty} A_i^c \Big)^c \in \mathcal{B}.\]
Closed under finite unions and intersections: take $A_{n+1} = A_{n+2} = \cdots = \emptyset$ in (3).

Examples.

Trivial sigma algebra: $\mathcal{B} = \lbrace \emptyset, S \rbrace$.
Generated by one event: $\mathcal{B} = \lbrace \emptyset, A, A^c, S \rbrace$. For a coin, $\lbrace \emptyset, \lbrace H \rbrace, \lbrace T \rbrace, S \rbrace$.
Power set (Example 1.2.2): if $S$ is finite or countable, take $\mathcal{B} =$ all subsets of $S$. If $S$ has $n$ elements, $\mathcal{B}$ has $2^n$ sets (Exercise 1.14). For $S = \lbrace 1, 2, 3 \rbrace$:
\[\mathcal{B} = \big\lbrace \emptyset, \lbrace 1 \rbrace, \lbrace 2 \rbrace, \lbrace 3 \rbrace, \lbrace 1, 2 \rbrace, \lbrace 1, 3 \rbrace, \lbrace 2, 3 \rbrace, \lbrace 1, 2, 3 \rbrace \big\rbrace.\]
Borel sets on $\mathbb{R}$ (Example 1.2.3): for $S = (-\infty, \infty)$, take the smallest sigma algebra containing all intervals $[a, b]$, $(a, b]$, $(a, b)$, $[a, b)$. It contains every set you can build from intervals by countably many unions, intersections, and complements. It contains every set we will need in this course.

Non-example. For $S = \lbrace 1, 2, 3 \rbrace$, $\lbrace \emptyset, \lbrace 1 \rbrace, \lbrace 2 \rbrace, S \rbrace$ is not a sigma algebra: $\lbrace 1 \rbrace^c = \lbrace 2, 3 \rbrace$ is missing, and so is $\lbrace 1 \rbrace \cup \lbrace 2 \rbrace = \lbrace 1, 2 \rbrace$.

3. The axioms of probability

Definition 1.2.4 (Kolmogorov axioms). Given a sample space $S$ and an associated sigma algebra $\mathcal{B}$, a probability function is a function $P$ with domain $\mathcal{B}$ that satisfies

$P(A) \ge 0$ for all $A \in \mathcal{B}$;
$P(S) = 1$;
Countable additivity: if $A_1, A_2, \dots \in \mathcal{B}$ are pairwise disjoint, then
\[P\Big( \bigcup_{i=1}^{\infty} A_i \Big) = \sum_{i=1}^{\infty} P(A_i).\]

The triple $(S, \mathcal{B}, P)$ is called a probability space. The axioms say nothing about which $P$ is right for a given experiment. That is a modeling decision.

Example 1.2.5 (fair coin). $S = \lbrace H, T \rbrace$. “Fair” means $P(\lbrace H \rbrace) = P(\lbrace T \rbrace)$. This is a modeling assumption, not a consequence of the axioms. Since $\lbrace H \rbrace$ and $\lbrace T \rbrace$ are disjoint with union $S$, Axioms 2 and 3 give $P(\lbrace H \rbrace) + P(\lbrace T \rbrace) = 1$, so each equals $1/2$.

Any nonnegative values with $P(\lbrace H \rbrace) + P(\lbrace T \rbrace) = 1$ also define a legitimate probability function, for example $P(\lbrace H \rbrace) = 1/3$ and $P(\lbrace T \rbrace) = 2/3$.

Finite vs. countable additivity. Countable additivity implies finite additivity: if $A, B \in \mathcal{B}$ are disjoint, then $P(A \cup B) = P(A) + P(B)$ (Exercise 1.12(a); take $A_1 = A$, $A_2 = B$, $A_3 = A_4 = \cdots = \emptyset$). The converse fails. The de Finetti school accepts only finite additivity. We follow C&B and assume countable additivity, which is what makes limits of probabilities work.

4. Constructing probability functions

We do not want to check the axioms from scratch for every new model. The following theorem gives a general recipe for countable sample spaces.

Theorem 1.2.6. Let $S = \lbrace s_1, \dots, s_n \rbrace$ be a finite set, and let $\mathcal{B}$ be any sigma algebra of subsets of $S$. Let $p_1, \dots, p_n$ be nonnegative numbers that sum to 1. For any $A \in \mathcal{B}$, define

\[P(A) = \sum_{\lbrace i : s_i \in A \rbrace} p_i\]

(a sum over the empty set is 0). Then $P$ is a probability function on $\mathcal{B}$. The same holds for a countable $S = \lbrace s_1, s_2, \dots \rbrace$.

Proof (finite case).

Axiom 1: $P(A)$ is a sum of nonnegative numbers, so $P(A) \ge 0$.
Axiom 2: $P(S) = \sum_{i=1}^{n} p_i = 1$.
Axiom 3: nonempty pairwise disjoint sets are distinct, and $\mathcal{B}$ is finite, so only finitely many of the $A_i$ can be nonempty. It therefore suffices to consider pairwise disjoint $A_1, \dots, A_k$. Then

\[P\Big( \bigcup_{i=1}^{k} A_i \Big) = \sum_{\lbrace j : s_j \in \cup_{i} A_i \rbrace} p_j = \sum_{i=1}^{k} \; \sum_{\lbrace j : s_j \in A_i \rbrace} p_j = \sum_{i=1}^{k} P(A_i).\]

The middle equality holds because the $A_i$ are disjoint, so each $p_j$ appears exactly once on each side. $\square$

Special case: equally likely outcomes. If $p_i = 1/n$ for all $i$, then $P(A) = N(A)/n$, where $N(A)$ is the number of outcomes in $A$. This is why counting (Week 2) is so important.

Example (unfair coin tossed twice). A coin has $P(H) = 1/4$. Toss it twice, independently, so $S = \lbrace HH, HT, TH, TT \rbrace$ with

\[p_{HH} = \tfrac{1}{16}, \quad p_{HT} = \tfrac{3}{16}, \quad p_{TH} = \tfrac{3}{16}, \quad p_{TT} = \tfrac{9}{16}.\]

These are nonnegative and sum to 1, so Theorem 1.2.6 gives a probability function. Then $P(\text{at least one head}) = \frac{1}{16} + \frac{3}{16} + \frac{3}{16} = \frac{7}{16}$. The outcomes are not equally likely, so $N(A)/N(S) = 3/4$ would be wrong. (We make “independently” precise in Week 2.)

Example 1.2.7 (darts). A dart board of radius $r$ has 5 rings, each of width $r/5$. A novice who always hits the board lands in a region with probability proportional to its area:

\[P(\text{scoring } i \text{ points}) = \frac{\pi \big( (6-i) r / 5 \big)^2 - \pi \big( (5-i) r / 5 \big)^2}{\pi r^2} = \frac{(6-i)^2 - (5-i)^2}{5^2}, \qquad i = 1, \dots, 5.\]

The five values are nonnegative and sum to 1 (the sum telescopes), so this is a probability function by Theorem 1.2.6. Note the answer does not depend on $r$ or $\pi$. (See Exercises 1.7 and 1.8.)

5. The calculus of probabilities

Everything below is derived from the three axioms. These proofs are models for the kind of argument you will write all quarter.

Theorem 1.2.8. If $P$ is a probability function and $A \in \mathcal{B}$, then

(a) $P(\emptyset) = 0$;
(b) $P(A) \le 1$;
(c) $P(A^c) = 1 - P(A)$.

Proof. (c) first: $A$ and $A^c$ are disjoint with $A \cup A^c = S$, so by Axioms 2 and 3,

\[1 = P(S) = P(A \cup A^c) = P(A) + P(A^c).\]

(b) Since $P(A^c) \ge 0$ by Axiom 1, (c) gives $P(A) = 1 - P(A^c) \le 1$.

(a) $S$ and $\emptyset$ are disjoint and $S = S \cup \emptyset$, so $1 = P(S) = P(S) + P(\emptyset)$, hence $P(\emptyset) = 0$. $\square$

Theorem 1.2.9. If $P$ is a probability function and $A, B \in \mathcal{B}$, then

(a) $P(B \cap A^c) = P(B) - P(A \cap B)$;
(b) $P(A \cup B) = P(A) + P(B) - P(A \cap B)$;
(c) if $A \subset B$, then $P(A) \le P(B)$ (monotonicity).

Proof. (a) $B = (B \cap A) \cup (B \cap A^c)$ is a disjoint union, so $P(B) = P(B \cap A) + P(B \cap A^c)$. Rearrange.

(b) $A \cup B = A \cup (B \cap A^c)$ is a disjoint union (Exercise 1.2(d)), so by (a),

\[P(A \cup B) = P(A) + P(B \cap A^c) = P(A) + P(B) - P(A \cap B).\]

Part (b) is the two-set case of inclusion–exclusion. For three sets,

\[P(A \cup B \cup C) = P(A) + P(B) + P(C) - P(A \cap B) - P(A \cap C) - P(B \cap C) + P(A \cap B \cap C).\]

(Try proving it by applying (b) twice.)

6. Bonferroni’s inequality

From Theorem 1.2.9(b) and $P(A \cup B) \le 1$:

\[P(A \cap B) \ge P(A) + P(B) - 1. \tag{1.2.9}\]

This is a special case of Bonferroni’s inequality. It bounds the probability of a joint event using only the individual probabilities.

Example 1.2.10. If $P(A) = P(B) = 0.95$, then $P(A \cap B) \ge 0.95 + 0.95 - 1 = 0.90$. In particular, $A$ and $B$ cannot be disjoint. The bound is only useful when the individual probabilities are large. Otherwise it is a correct but useless negative number.

Example. If $P(A) = 0.8$ and $P(B) = 0.6$, can $A$ and $B$ be disjoint? No: $P(A \cap B) \ge 0.4 > 0$.

Example (Exercise 1.13). If $P(A) = 1/3$ and $P(B^c) = 1/4$, can $A$ and $B$ be disjoint? We have $P(B) = 3/4$, so $P(A) + P(B) = 13/12 > 1$. If they were disjoint, $P(A \cup B)$ would exceed 1. So no.

7. Partitions and Boole’s inequality

Theorem 1.2.11. If $P$ is a probability function, then

(a) $P(A) = \sum_{i=1}^{\infty} P(A \cap C_i)$ for any partition $C_1, C_2, \dots$ of $S$;
(b) Boole’s inequality: $P\big( \bigcup_{i=1}^{\infty} A_i \big) \le \sum_{i=1}^{\infty} P(A_i)$ for any sets $A_1, A_2, \dots$.

Proof of (a). Since the $C_i$ partition $S$, by the distributive law

\[A = A \cap S = A \cap \Big( \bigcup_{i=1}^{\infty} C_i \Big) = \bigcup_{i=1}^{\infty} (A \cap C_i).\]

The sets $A \cap C_i$ are pairwise disjoint because the $C_i$ are. Countable additivity then gives $P(A) = \sum_i P(A \cap C_i)$. $\square$

Proof of (b) — the disjointification trick. The $A_i$ may overlap, so we replace them with disjoint pieces that have the same union. Define

\[B_1 = A_1, \qquad B_i = A_i \setminus \Big( \bigcup_{j=1}^{i-1} A_j \Big) = A_i \cap A_1^c \cap \cdots \cap A_{i-1}^c, \quad i = 2, 3, \dots\]

so $B_i$ contains the points of $A_i$ that are not in any earlier $A_j$. Then:

The $B_i$ are pairwise disjoint. If $k < i$, then $B_i \subset A_k^c$ while $B_k \subset A_k$, so $B_i \cap B_k = \emptyset$.
Same union: $\bigcup_i B_i = \bigcup_i A_i$. ($\subset$) holds since $B_i \subset A_i$. For ($\supset$), if $x \in \bigcup_i A_i$, let $i$ be the first index with $x \in A_i$. Then $x \in B_i$.
Each $B_i$ is smaller: $B_i \subset A_i$, so $P(B_i) \le P(A_i)$ by monotonicity.

Therefore

\[P\Big( \bigcup_{i=1}^{\infty} A_i \Big) = P\Big( \bigcup_{i=1}^{\infty} B_i \Big) = \sum_{i=1}^{\infty} P(B_i) \le \sum_{i=1}^{\infty} P(A_i). \qquad \square\]

Remark. Disjointification is one of the most useful tricks in probability. It reappears, for example, in proving continuity of probability (Exercise 1.12(b)) and in constructing distribution functions.

Boole and Bonferroni are the same inequality. Apply Boole’s inequality to $A_1^c, \dots, A_n^c$ and use DeMorgan, $\bigcup_i A_i^c = \big( \bigcap_i A_i \big)^c$:

\[1 - P\Big( \bigcap_{i=1}^{n} A_i \Big) \le \sum_{i=1}^{n} \big( 1 - P(A_i) \big) \quad \Longrightarrow \quad P\Big( \bigcap_{i=1}^{n} A_i \Big) \ge \sum_{i=1}^{n} P(A_i) - (n - 1). \tag{1.2.10}\]

Application (multiple testing). Suppose you construct 10 confidence intervals, each covering its parameter with probability 0.99. Let $A_i$ be the event that interval $i$ covers. By (1.2.10), the probability that all 10 cover is at least $10(0.99) - 9 = 0.90$, whatever the dependence among the intervals. This is the basis of the Bonferroni correction.

Summary of Week 1

Objects: sample space $S$; events $A \subset S$; sigma algebra $\mathcal{B}$; probability function $P$ on $\mathcal{B}$.
Axioms: $P(A) \ge 0$; $P(S) = 1$; countable additivity for disjoint events.
Properties: $P(\emptyset) = 0$; $P(A^c) = 1 - P(A)$; monotonicity; $P(A \cup B) = P(A) + P(B) - P(A \cap B)$; the partition formula; Boole’s and Bonferroni’s inequalities.
Proof techniques: show set equality by double containment; split a set into disjoint pieces, then apply Axiom 3; disjointification.