Set Operations and Probability

Events as Sets

Events are subsets of the sample space. Set operations translate naturally into probability operations.

Union

The union $E \cup F$ is the event that $E$ or $F$ (or both) occurs.

$P(E \cup F) = P(E) + P(F) - P(E \cap F)$

The inclusion-exclusion formula corrects for double-counting outcomes in both events.

Multiple Unions

For $n$ events:

$P\left(\bigcup_{i=1}^{n} E_i\right) \leq \sum_{i=1}^{n} P(E_i)$

This upper bound is the union bound (Boole’s inequality): the probability of at least one occurring is at most the sum of individual probabilities.

Intersection

The intersection $E \cap F$ (or $EF$) is the event that both $E$ and $F$ occur.

For mutually exclusive events: $P(E \cap F) = 0$.

Complement

The complement $E^c$ is the event that $E$ does not occur.

$P(E^c) = 1 - P(E)$

This is useful when computing the probability of “at least one” by considering “none”:

$P(\text{at least one}) = 1 - P(\text{none})$

Example: Matching Problem

Three letters are randomly placed into three addressed envelopes. What is the probability at least one letter is in the correct envelope?

Direct approach: Inclusion-exclusion over three events.

Complement approach: Compute $P(\text{none correct}) = P(\text{derangement})$. There are 2 derangements out of $3! = 6$ permutations. So $P(\text{none}) = 2/6 = 1/3$.

$P(\text{at least one}) = 1 - \frac{1}{3} = \frac{2}{3}$

Difference

The set difference $E - F = E \setminus F$ is the event that $E$ occurs but $F$ does not.

$P(E - F) = P(E) - P(E \cap F)$

Proof: $E = (E - F) \cup (E \cap F)$ where these are disjoint. By additivity: $P(E) = P(E - F) + P(E \cap F)$, so $P(E - F) = P(E) - P(E \cap F)$.

Symmetric Difference

The symmetric difference $E \triangle F = (E - F) \cup (F - E)$ is the event that exactly one of $E$, $F$ occurs.

$P(E \triangle F) = P(E) + P(F) - 2P(E \cap F)$

De Morgan’s Laws

First Law

$(E \cup F)^c = E^c \cap F^c$

Probability interpretation: The event that neither $E$ nor $F$ occurs is the event that $E$ does not occur AND $F$ does not occur.

Second Law

$(E \cap F)^c = E^c \cup F^c$

Probability interpretation: The event that not both $E$ and $F$ occur is the event that $E$ does not occur OR $F$ does not occur.

Example

Roll a die. Let $E$ = “roll even” $\{2,4,6\}$ and $F$ = “roll at least 5” $\{5,6\}$.

• $E \cup F = \{2,4,5,6\}$, so $(E \cup F)^c = \{1,3\}$
• $E^c = \{1,3,5\}$, $F^c = \{1,2,3,4\}$
• $E^c \cap F^c = \{1,3\}$ (matches first law)

Distributive Laws

$E \cap (F \cup G) = (E \cap F) \cup (E \cap G)$ $E \cup (F \cap G) = (E \cup F) \cap (E \cup G)$

These allow us to expand or simplify probability expressions.

Associative and Commutative Laws

Union and intersection are associative and commutative:

$E \cup F = F \cup E, \quad E \cap F = F \cap E$ $E \cup (F \cup G) = (E \cup F) \cup G, \quad E \cap (F \cap G) = (E \cap F) \cap G$

This means we can rearrange events in unions and intersections without changing the result.

Summary Table

Operation	Set Notation	Probability Formula
Union	$E \cup F$	$P(E) + P(F) - P(E \cap F)$
Intersection	$E \cap F$	$P(E \cap F)$
Complement	$E^c$	$1 - P(E)$
Difference	$E - F$	$P(E) - P(E \cap F)$
De Morgan 1	$(E \cup F)^c$	$E^c \cap F^c$
De Morgan 2	$(E \cap F)^c$	$E^c \cup F^c$