Slides 📊
4.1. Basic Set Theory
We are now ready to delve into the mathematical framework of describing uncertainty—namely, probability theory. We begin by developing the basic vocabulary of set theory.
Road Map 🧭
Define experiments, sample spaces, and events as the building blocks of probability.
Explore set operations: complement, union, and intersection.
Visualize set relationships using Venn diagrams.
Understand the basic rules governing set operations.
4.1.1. Basic Terminology and Notation
Random Experiment
A Random experiment is a repeatable process with at least two possible outcomes, and where the result of any single run cannot be predicted with certainty.
Examples of random experiments include:
Rolling a die
Flipping a coin
Measuring the height of a randomly selected student
Observing whether a manufactured part is defective
Sample space
A sample space is the set of all possible outcomes in a random experiment.
A set is a mathematical object represnting a collection of objects. It is conventionally named with a capital letter. When listing its elements, we enclose them in a pair of curly brackets, \(\{\cdots\}\).
Because the sample space is a special set in probability, we set aside the letters \(S\) or \(\Omega\) (Omega) for it and rarely use them to name other sets. When referring to an arbitrary single outcome in a sample space, we use the lower case Greek letter \(\omega\) (omega).
To express that an outcome belongs to a set, we use the notation \(\in\). For example,
Trial
A trial refers to a single execution of a random experiment.
Event
An Event is a set of outcomes. An event can be
a simple event consisting of a single outcome,
a set as large as the whole sample space, or
an empty set (denoted by \(\emptyset\) or \(\{\}\)).
An empty set is a valid event representing the set of “impossible” outcomes in the experiment.
Events are denoted by capital letters other than the ones set aside for the sample space.
Example💡: Using Set Theory Terminology and Notation Correctly
1. Suppose a 20-sided die is being rolled. Identify the random experiment, trial and sample space.
The random experiment is the action of rolling a 20-sided die. A trial consists of rolling the die once then observing the outcome. Its sample space can be denoted as:
\[\Omega = \{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20\}\]
Name the events corresponding to
“rolling an even number”
“rolling a value of at least 21”
“rolling a perfect 20”
“rolling a number”
and list their elements using the correct set theory notation.
Denote the events described in parts (a)-(d) with capital letters \(A\) - \(D\), respectively.
\(A = \{2, 4, 6, 8, 10, 12, 14, 16, 18, 20\}\).
\(B = \{\}\) or \(B=\emptyset\) because there is no outcome in the sample space \(\Omega\) which fits the description. It is an “impossible” event.
\(C = \{20\}\). It is a simple event.
\(D = \Omega\) since any outcome in the sample space fits the description.
4.1.2. Visualizing Sets with Venn Diagrams
Fig. 4.1 A simple venn diagram
Venn diagrams provide a visual tool for understanding relationships between sets. A Venn diagram is constructed based on the following rules:
The sample space is represented with a rectangle.
Events are represented as circles inside the rectangle.
In general, two events are drawn to slightly overlap with each other to account for any outcomes that might belong to both.
All shapes must be labeled.
4.1.3. Core Set Operations
The power of set theory lies in the operations that allow us to construct new sets from existing ones. This section introduces some of the most fundamental of such operations.
Complement
Fig. 4.2 Complement of A
The complement of an event \(A\), denoted \(A'\) (read as “A prime” or “A complement”), consists of the outcomes in the sample space that are not in A.
Example💡: Complement
Find the complements of events \(A\) - \(D\) from the previous example.
\(A' = \{1, 3, 5, 7, 9, 11, 13, 15, 17, 19\}\).
\(B' = \Omega\) since all outcomes are not in event B.
\(C' = \{1, 2, \cdots, 19\}\).
\(D' = \emptyset\).
Union
Fig. 4.3 Union of A and B
The union of events \(A\) and \(B\), denoted \(A \cup B\), contains all outcomes that belong to either A or B or both.
Example💡: Union
Suppose a 20-sided die is being rolled. Continue using the events \(A\) - \(D\) defined in the first example.
Define a new event \(E\) consisting of all outcomes less than 6. Find the union of each of \(A\) - \(D\) with \(E\).
Begin by writing down the elements of \(E\) formally:
\[E = \{1,2,3,4,5\}.\]\(A \cup E = \{1,2,3,4,5,6,8,10,12,14,16,18,20\}\).
\(B \cup E = \emptyset \cup E = \{1,2,3,4,5\} = E\).
\(C \cup E = \{1,2,3,4,5,20\}\).
\(D \cup E = \Omega \cup E = \Omega\).
In general, what is the union of an event and its complement?
A set and its “everything else” make up a whole together. The union of an event with its complement is always the sample space.
Intersection
Fig. 4.4 Intersection of A and B
The intersection of events \(A\) and \(B\), denoted \(A \cap B\), contains the outcomes that belong to both A and B.
Example💡: Intersection
Suppose a 20-sided die is being rolled. Continue using the events \(A\) - \(E\) defined in the previous examples.
Find the intersection of each of \(A\) - \(D\) with \(E\).
\(A \cap E = \{2,4\}\)
\(B \cap E = \emptyset \cap E= \emptyset\) because the overlap of “nothing” with \(E\) is still “nothing”!
\(C \cap E = \emptyset\). The two events have no shared elements.
\(D \cap E = \Omega \cap E = \{1,2,3,4,5\} = E\). The entirety of \(E\) is an overlap between \(D\) and \(E\).
In general, what is the intersection of an event and its complement?
If an outcome belongs to an event, it cannot belong to the complement, and vice versa. Therfore, the intersection of an event and its complement is always an empty set.
Mutually Exclusive Events
Fig. 4.5 Mutually exclusive events
When two events cannot happen simultaneously, we call them mutually exclusive or disjoint. Since no outcome can belong to both sets at the same time, their intersection is always an empty set. In mathematical notation, if events \(A\) and \(B\) are mutually exclusive, we write
To express this special relationship graphically, we draw disjoint events as non-overlapping regions on a Venn diagram.
Example💡: Mutually Exclusive Sets
Among the previously defined events \(A,B, \cdots, E\), can you identify any pair of events that are mutually exclusive?
\(C \cap E = \emptyset\) because they do not have any common outcomes.
\(A,C,D,E\) are all disjoint with \(B=\emptyset\) because the pairwise intersections are an empty set.
Subsets
Fig. 4.6 C is a subset of A (C ⊆ A)
We say \(A\) is a subset of \(B\), and write \(A \subseteq B\), if every outcome in \(A\) is also in \(B\). In other words, the whole set A is a part of the set B.
On a Venn diagram, we express the relationship by drawing the smaller set as completely enclosed in the larger set.
Example💡: Subsets
Among the previously defined events \(A,B, \cdots, E\), can you identify an event that is a subset of another event?
\(C \subseteq A\) because the outcome 20 makes up the whole event \(C\) but also belongs to the event \(A\).
All events are a subet of \(D=\Omega\).
Each event is a subset of itself because every outcome in \(A\) is also in \(A\)!
\(B = \emptyset\) is a subset of any other event. (This one requires a more subtle argument which we will not go through now. It is included for the completeness of the example.)
Extending Operations to Multiple Events
The union and intersection operations can be extended to multiple events using indexing notation.
A union of \(n\) events \(A_1, A_2, \cdots, A_n\) contains the outcomes which belong to \(A_1, A_2, \cdots\), or \(A_n\). It is written as
An intersection of \(n\) events \(A_1, A_2, \cdots, A_n\) contains the outcomes which belong to all of \(A_1, A_2, \cdots\), and \(A_n\). It is denoted by
Important tip 🛑
Being able to move fluently between plain-language descriptions of complex events and their mathematical notation is a vital skill. Recall that the three core set operations—complement, union, and intersection—correspond directly to the key words “not”, “or”, and “and”, respectively. Keep these translations in mind when approaching word problems.
4.1.4. Algebra of Sets
Set operations follow specific algebraic laws that parallel those in ordinary arithmetic. Understanding these laws will allow us to manipulate complex set expressions more efficiently.
Commutative Laws
For a union or intersection of a pair of events, their order does not matter.
Associative Laws
When we have multiple operations of the same type (all unions or all intersections), the order of pairwise operations does not matter.
Parentheses indicate that any operations inside must be prioritized over the ones outside.
When dealing with a sequence of the same operation, this property allows us to place parentheses wherever we want without changing the result. For example, when taking the union of three sets, we could first unite A and B and then unite the result with C, or we could first unite B and C and then unite A with that result—the final set will be identical either way.
Remark: Justifying the Multiset Notation
Recall the \(n\)-event extensions of union and intersection from above.
We already accepted these as true, but they in fact require the commutative and associative laws to be well-defined. Without the associative property, we would need to specify the exact order of pairwise operations using multiple sets of parentheses. The commutative property allows us to index the events in any way without changing the result.
Distributive Laws
The distributive laws apply when when unions and intersections are used together.
They are called “distributive” because one operation distributes over the other, similar to how multiplication distributes over addition in algebra (\(a(b + c) = a b + a c\)).
Let us confirm these laws through a concrete example.
Example💡: Distributive laws
Suppose we are rolling a 6-sided die. Take the events A = {1, 2, 3}, B = {2, 3, 4}, and C = {3, 4, 5}. Compute \(A \cup (B \cap C)\) directly AND using the appropriate distributive law. Confirm that the two methods yield an identical outcome.
Computing \(A \cup (B \cap C)\) directly
\(B \cap C = \{3,4\}\). Then \(A \cup (B \cap C) = \{1, 2, 3\} \cup \{3,4\} = \{1,2,3,4\}\).
Using the distributive law
Let us compute the right hand side of the first law, \((A \cup B) \cap (A \cup C).\) First, \(A \cup B = \{1, 2, 3, 4\}\) and \(A \cup C = \{1, 2, 3, 4, 5\}\). Then
Yes, the two methods give the same answer.
The distributive laws extend to multiple sets as well:
De Morgan’s Laws
De Morgan’s laws are a tool for manipulating complements of unions and intersections.
De Morgan’s First Law:
In plain language, this means that for an outcome to be excluded from “A or B,” it must be excluded from both A and B.
De Morgan’s Second Law:
This means that for an outcome to be excluded from “A and B,” it is sufficient to be excluded from either A or B (or both).
Example💡: De Morgan’s Laws
Let us continue to consider the random experiment of rolling a six-sided die. Define new events:
\(D = \{5,6\}\) (the event of rolling a number greater than 4)
\(E = \{2, 4, 6\}\) (the event of rolling an even number)
1. Find \((D \cap E)'\) directly and using the appropriate De Margan’s law. Confirm that the two methods yield the same answer.
Finding \((D \cap E)'\) directly:
\((D \cap E)=\{6\}\). Then \((D \cap E)'=\{1,2,3,4,5\}\).
Using De Morgan’s second law:
\(D' = \{1,2,3,4\}\) and \(E' = \{1,3,5\}\). Therefore, \(D' \cup E' = \{1,2,3,4\} \cup \{1,3,5\} =\{1,2,3,4,5\}\).
Yes, the two approaches result in the same answer.
Try verifying De Morgan’s first law as an independent exercise.
The multi-event form of De Morgan’s first law is:
Fig. 4.7 Multi-event first De Morgan’s Law
This reads as “the complement of the union of \(n\) events equals the intersection of the complements of those \(n\) events.” In other words, for an outcome to be outside the union of all events, it must be outside each individual event.
The multi-event form of De Morgan’s second law is:
Fig. 4.8 Multi-event second De Morgan’s Law
This reads as “the complement of the intersection of \(n\) events equals the union of the complements of those \(n\) events.” This means an outcome is outside the intersection of all events if it’s outside at least one of the individual events.
4.1.5. Bringing It All Together
Key Takeaways 📝
Random experiments produce outcomes with uncertainty; the complete collection of possible outcomes forms the sample space.
Events are subsets of the sample space, representing collections of outcomes we’re interested in studying.
The fundamental set operations—complement, union, and intersection—allow us to create new events from existing ones.
Venn diagrams provide a visual representation of set relationships.
Set operations follow algebraic laws similar to those in ordinary arithmetic.
De Morgan’s laws provide tools for manipulating complex expressions by relating complements of unions and intersections.
In the next chapter, we’ll assign numerical measures to events, allowing us to quantify uncertainty with probability. The set operations we’ve learned will become the building blocks for the probability rules that govern statistical inference.
Exercises
Basics of random experiment. For each scenario below, identify the sample space and three events of interest:
The daily closing stock price of a company listed on Nasdaq
Testing whether manufactured products are defective
20-sided die. Let S = {1, 2, …, 20}, A = “even numbers”, and B = “numbers less than or equal to 10”. Verify De Morgan’s second law by showing that (A ∪ B)’ = A’ ∩ B’ for these specific sets.
Venn diagram sketch. Draw three overlapping circles labeled A, B, and C. Shade the region corresponding to (A ∩ C’) ∪ (B ∩ C).