Collections of distinct objects. Union, intersection, complement operations.
Deep-dive lesson - accessible entry point but dense material. Use worked examples and spaced repetition.
Sets are the language of “which things are we talking about?” In discrete math, computer science, and probability, you constantly build, compare, and combine collections—and sets give you precise tools to do that without ambiguity.
A set is a collection of distinct objects called elements. Use x ∈ A to mean “x is in A”, A ⊆ B to mean “A is a subset of B”. Core operations build new sets from old ones: union (A ∪ B), intersection (A ∩ B), and complement (Aᶜ, relative to a universe U).
In everyday language we often talk about groups of things:
But everyday language can be vague. Sets give a clean, mathematical way to specify exactly what belongs and what does not.
A big idea here is that sets are about membership—a yes/no question:
A set is a collection of distinct objects called elements.
If an object x is an element of set A, we write:
If x is not an element of A:
A set does not track multiplicity. So:
This is different from structures like lists/arrays (which can have repeats and order).
For sets, order is irrelevant:
1) Roster notation (explicit elements):
2) Set-builder notation (a rule):
Read “:” as “such that”.
3) By description (informal, but you should be able to translate it):
Many operations (especially complement) depend on what “all possible elements” are. We often declare a universe U.
Example:
Now the complement of A depends on U (we’ll define complement soon).
| Structure | Allows duplicates? | Order matters? | Typical use |
|---|---|---|---|
| Set | No | No | Membership queries, combining collections |
| List/Array | Yes | Yes | Sequences, indexing |
| Multiset/Bag | Yes | No | Counting items without order |
This node focuses on sets and their basic operations.
Before you combine sets, you need a way to:
1) Ask whether a specific element belongs (membership)
2) Compare whole sets (subset)
These are the backbone of definitions in later topics:
Membership is a statement like:
Notice the small but important point: you must know the intended meaning of ℕ, ℤ, ℚ, ℝ in your course or text.
We write:
and read it as:
Meaning:
Formally:
This definition is worth slowing down for. It says: take any x; if x is in A, then it must be in B.
Two sets are equal when they contain exactly the same elements:
This is a common proof pattern: to show sets are equal, prove two subset relations.
Sometimes we want “A is contained in B, but not equal.” This is a proper subset:
Meaning:
(Notation varies: some books use ⊊ for proper subset and reserve ⊂ for subset-or-equal. In this lesson, ⊆ is subset-or-equal as requested.)
The empty set has no elements:
A key fact:
Why? Use the definition:
But x ∈ ∅ is never true, so the implication “false ⇒ anything” is true. So the statement holds.
This can feel slippery at first, but it becomes very useful later.
| Symbol | Meaning | Example |
|---|---|---|
| ∈ | element of | 2 ∈ {1,2,3} |
| ∉ | not an element of | 4 ∉ {1,2,3} |
| ⊆ | subset or equal | {1,2} ⊆ {1,2,3} |
| ∅ | empty set | ∅ ⊆ A |
Sets and logic are tightly related. Notice how subset uses ⇒ and ∀. This is your first hint that discrete math is often “logic + structures”.
Once you can describe sets, you want to construct new ones:
Set operations are the math version of these moves.
We’ll assume a fixed universe U when talking about complements.
Union collects elements that are in A or in B (or both).
Definition:
Example:
Notice: 3 appears once (sets don’t duplicate).
Intersection collects elements that are in both A and B.
Definition:
Example:
If there is no overlap:
The complement means “everything in the universe that is not in A.”
Definition (relative complement in U):
Example:
This is why the universe matters: if U changes, Aᶜ changes.
Not required by the node description, but it’s a common companion.
Definition:
Example:
And note:
These are “algebra rules” for sets.
If you later study Boolean algebra, these will feel very familiar.
Even without drawing, it helps to imagine two overlapping circles:
Venn diagrams are great for intuition, but definitions using ∈, ∨, ∧ are what make arguments precise.
You may soon see sets whose elements are vectors like v ∈ ℝⁿ. The set ideas are identical:
Sets can feel abstract until you see them in the wild. This section shows how the same few ideas (∈, ⊆, ∪, ∩, Aᶜ) appear across fields.
Suppose:
Then:
If:
Then:
If:
Then valid inputs are:
A (simple) graph is often described as:
where:
In an undirected graph, edges can be represented as sets {u, v} with u, v ∈ V.
So you’ll write things like:
This is the set language of graphs.
A relation R between sets A and B is a subset of A × B.
Even before learning Cartesian products in detail, note the pattern:
Elements of R are typically ordered pairs (a, b). Membership means:
Properties like “reflexive” and “transitive” are built from membership statements about such pairs.
A vector space begins as a set V whose elements are vectors v, together with operations like addition and scalar multiplication.
The set part still matters:
And closure properties are set statements:
So sets are the container that later structure lives inside.
In probability, an event is a set of outcomes.
If Ω is the sample space (a universe of outcomes), then events are subsets:
Operations match intuitive language:
Measure theory will later formalize which sets are allowed to be events (σ-algebras), but the basic operations are the same.
Set operations are like logical operations on membership:
This “translate to logic” trick is one of the most powerful habits you can build early.
Let U = {1, 2, 3, 4, 5, 6}. Let A = {1, 2, 4, 6} and B = {2, 3, 6}. Find A ∪ B, A ∩ B, Aᶜ, and Bᶜ (all complements relative to U).
Union means “in A or in B”.
A ∪ B = {x : x ∈ A ∨ x ∈ B}
Start from A = {1,2,4,6} and add any elements from B not already included.
So A ∪ B = {1, 2, 3, 4, 6}.
Intersection means “in both”.
A ∩ B = {x : x ∈ A ∧ x ∈ B}
Check elements of B against A:
So A ∩ B = {2, 6}.
Complement means “in U but not in the set”.
Aᶜ = U \ A = {x ∈ U : x ∉ A}
U = {1,2,3,4,5,6} and A = {1,2,4,6}
Remove 1,2,4,6 from U ⇒ Aᶜ = {3, 5}.
Similarly,
Bᶜ = U \ B
Remove 2,3,6 from U ⇒ Bᶜ = {1, 4, 5}.
Insight: Always state (or infer) the universe U before taking complements. Union/intersection don’t need U, but complements do.
Let U be a universe, and let A, B ⊆ U. Prove that A \ B = A ∩ Bᶜ.
Why this proof style works:
To prove two sets are equal, show they have the same elements.
That is, show:
(1) A \ B ⊆ A ∩ Bᶜ
(2) A ∩ Bᶜ ⊆ A \ B
(1) Show A \ B ⊆ A ∩ Bᶜ.
Take an arbitrary element x.
Assume x ∈ A \ B.
By definition of set difference:
From (x ∉ B) and the definition of complement:
So we have (x ∈ A) ∧ (x ∈ Bᶜ), which means:
Therefore every x in A \ B is in A ∩ Bᶜ, so A \ B ⊆ A ∩ Bᶜ.
(2) Show A ∩ Bᶜ ⊆ A \ B.
Take an arbitrary element x.
Assume x ∈ A ∩ Bᶜ.
By definition of intersection:
By definition of complement:
So (x ∈ A) ∧ (x ∉ B), which is exactly the definition of x ∈ A \ B.
Therefore A ∩ Bᶜ ⊆ A \ B.
Since we proved both subset directions, we conclude:
A \ B = A ∩ Bᶜ.
Insight: Many set proofs are really logic proofs in disguise. Translate set membership into ∧, ∨, and ¬ statements and the result becomes straightforward.
Let A = {1, 2, 3} and B = {x ∈ ℕ : x ≤ 3}. Decide whether A = B, and justify using subset reasoning.
First interpret B.
B = {x ∈ ℕ : x ≤ 3} means “natural numbers less than or equal to 3”.
Assuming ℕ = {1,2,3,…}, this gives B = {1, 2, 3}.
Now show A ⊆ B.
Take any x ∈ A. Then x is one of {1,2,3}.
Each of these is a natural number and ≤ 3, so x ∈ B.
Therefore A ⊆ B.
Show B ⊆ A.
Take any x ∈ B. Then x ∈ ℕ and x ≤ 3.
So x must be 1, 2, or 3.
Hence x ∈ A.
Therefore B ⊆ A.
Conclude equality.
Since A ⊆ B and B ⊆ A, we have A = B.
Insight: Set-builder notation often defines a set indirectly. Converting it to a roster (when finite) makes comparisons easier, but the real justification still comes from subset logic.
A set is a collection of distinct elements; order and duplicates do not matter.
Membership is written x ∈ A (or x ∉ A) and is a yes/no statement.
Subset is written A ⊆ B and means ∀x (x ∈ A ⇒ x ∈ B).
Set equality can be proven via two inclusions: A = B ⇔ (A ⊆ B) ∧ (B ⊆ A).
Union and intersection are defined by logic: x ∈ A ∪ B ⇔ (x ∈ A) ∨ (x ∈ B), and x ∈ A ∩ B ⇔ (x ∈ A) ∧ (x ∈ B).
Complement Aᶜ depends on a universe U: Aᶜ = {x ∈ U : x ∉ A}.
Many set identities are best proven by “element-chasing”: assume x is in one set and show it must be in the other.
Forgetting to specify the universe U when taking complements, leading to ambiguous answers.
Treating sets like lists: thinking {1,2,2} is different from {1,2} or that {a,b} ≠ {b,a}.
Confusing ∈ (element-of) with ⊆ (subset-of), e.g., writing 2 ⊆ A instead of 2 ∈ A.
Assuming A ⊆ B means A is “smaller” in size; subset is about containment, not cardinality (though containment often implies size constraints for finite sets).
Let U = {a, b, c, d, e}. Let A = {a, c, e} and B = {b, c, d}. Compute A ∪ B, A ∩ B, Aᶜ, and (A ∩ B)ᶜ.
Hint: Union = in either set; intersection = in both; complements are relative to U.
A ∪ B = {a, b, c, d, e}.
A ∩ B = {c}.
Aᶜ = U \ A = {b, d}.
(A ∩ B)ᶜ = U \ {c} = {a, b, d, e}.
Prove using element-chasing that A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C).
Hint: Show both subset directions. Start with x ∈ A ∩ (B ∪ C) and translate membership into logic using ∧ and ∨.
Take arbitrary x.
(⊆) Assume x ∈ A ∩ (B ∪ C).
Then x ∈ A and x ∈ (B ∪ C).
So x ∈ A and (x ∈ B or x ∈ C).
Thus (x ∈ A and x ∈ B) or (x ∈ A and x ∈ C).
So x ∈ (A ∩ B) or x ∈ (A ∩ C).
Hence x ∈ (A ∩ B) ∪ (A ∩ C).
(⊇) Assume x ∈ (A ∩ B) ∪ (A ∩ C).
Then (x ∈ A and x ∈ B) or (x ∈ A and x ∈ C).
In either case x ∈ A, and also (x ∈ B or x ∈ C), meaning x ∈ (B ∪ C).
Therefore x ∈ A ∩ (B ∪ C).
So A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C).
Let A and B be sets. Is it always true that A ⊆ A ∪ B? Is it always true that A ∩ B ⊆ A? Prove your answers.
Hint: Use the definition of ⊆: pick an arbitrary x in the left-hand set and show it must be in the right-hand set.
Yes, both are always true.
1) A ⊆ A ∪ B:
Take x ∈ A. Then x ∈ A or x ∈ B is true (because x ∈ A). Hence x ∈ A ∪ B. So A ⊆ A ∪ B.
2) A ∩ B ⊆ A:
Take x ∈ A ∩ B. Then x ∈ A and x ∈ B, in particular x ∈ A. So A ∩ B ⊆ A.