Your phone's contact list, the students registered for a course, the keywords of C, the vertices of a graph, the rows returned by a SQL query: each of these is a collection of distinct things. Mathematics calls such a collection a set, and almost every other topic in discrete mathematics (functions, relations, graphs, counting, probability) is built on top of sets.
In this chapter we define sets precisely, learn the notation, study the operations (union, intersection, difference, complement, symmetric difference, Cartesian product, power set), prove set identities with the techniques from the Proof Techniques chapter, and see how programs represent sets. Along the way you will notice that set algebra is propositional logic in disguise, which is why the Logical Equivalences & Normal Forms chapter will feel very familiar here.
What Is a Set?
A set is an unordered collection of distinct objects, called its elements or members. We write x ∈ A if x is an element of A, and x ∉ A if it is not.
Two facts follow from "unordered" and "distinct":
Order does not matter: {1, 2, 3} = {3, 1, 2}.
Repetition does not matter: {1, 1, 2} = {1, 2}. Writing an element twice does not add it twice.
Sets are equal exactly when they have the same elements (the axiom of extensionality):
A = B ⟺ ∀x ( x ∈ A ↔ x ∈ B )
Describing a set
Method | Example | When to use |
|---|---|---|
Roster (listing) | V = {a, e, i, o, u} | Small finite sets, or obvious patterns like {2, 4, 6, …} |
Set-builder | E = { x ∈ ℤ | x = 2k for some k ∈ ℤ } | Sets defined by a property; read "|" as "such that" |
Interval notation (for reals) | [0, 1) = { x ∈ ℝ | 0 ≤ x < 1 } | Ranges of real numbers |
Standard number sets
Symbol | Set |
|---|---|
ℕ | Natural numbers {0, 1, 2, 3, …}. (Some books start at 1; always check the convention. In this tutorial ℕ includes 0.) |
ℤ | Integers {…, −2, −1, 0, 1, 2, …} |
ℤ+ | Positive integers {1, 2, 3, …} |
ℚ | Rational numbers { p/q | p, q ∈ ℤ, q ≠ 0 } |
ℝ | Real numbers |
Special sets
Empty set ∅ (also written { }): the set with no elements. There is only one empty set.
Singleton: a set with exactly one element, like {7}.
Universal set U: the set of all objects under discussion in a particular problem (for example, all students of a college). It changes from problem to problem.
Watch out: ∅ and {∅} are different. ∅ has no elements; {∅} has one element (which happens to be the empty set). Think of an empty box versus a box containing an empty box.
Subsets
A is a subset of B, written A ⊆ B, if every element of A is also an element of B: ∀x (x ∈ A → x ∈ B). A is a proper subset of B, written A ⊂ B (or A ⊊ B), if A ⊆ B and A ≠ B.
Two facts that every exam asks about:
∅ ⊆ A for every set A. Proof: we must show ∀x (x ∈ ∅ → x ∈ A). The hypothesis x ∈ ∅ is always false, so the implication is always true. This is a vacuous proof (Proof Techniques chapter).
A ⊆ A for every set A, since x ∈ A → x ∈ A is a tautology.
The standard way to prove two sets are equal is to prove two subset relations:
A = B ⟺ A ⊆ B and B ⊆ A
∈ versus ⊆
This is the most common source of errors. ∈ relates an element to a set; ⊆ relates a set to a set. Let A = {1, {2}, {1, 2}}.
Statement | True? | Reason |
|---|---|---|
1 ∈ A | Yes | 1 is listed |
2 ∈ A | No | 2 alone is not listed; {2} is |
{2} ∈ A | Yes | {2} is listed |
{1} ⊆ A | Yes | its only element, 1, is in A |
{2} ⊆ A | No | it would need 2 ∈ A |
{1, 2} ∈ A | Yes | {1, 2} is listed |
{{2}} ⊆ A | Yes | its only element, {2}, is in A |
∅ ⊆ A | Yes | always |
∅ ∈ A | No | ∅ is not listed as an element |
Cardinality
If A has exactly n distinct elements, where n ∈ ℕ, A is finite and its cardinality is |A| = n. Otherwise A is infinite.
|∅| = 0, |{∅}| = 1, |{a, b, a}| = 2, |{1, {1}, {1, {1}}}| = 3.
|{ x ∈ ℤ | x² < 10 }| = |{−3, −2, −1, 0, 1, 2, 3}| = 7.
Comparing the sizes of infinite sets (is ℤ "bigger" than ℕ? is ℝ?) needs functions, so it is done in the Functions chapter.
Power Set
The power set P(A) (also written 2A) is the set of all subsets of A.
For A = {a, b, c}:
P(A) = { ∅, {a}, {b}, {c}, {a,b}, {a,c}, {b,c}, {a,b,c} } |P(A)| = 8
Theorem. If |A| = n, then |P(A)| = 2n.
Proof. List the elements a1, …, an. Building a subset means making n independent yes/no choices: include a1 or not, include a2 or not, and so on. Different choice sequences give different subsets, and every subset arises from one sequence. So there are 2 · 2 ⋯ 2 = 2n subsets. ∎
This is also the link to binary numbers: each subset of an n-element set corresponds to an n-bit string (bit i = 1 if ai is included). The 8 subsets of {a, b, c} are the 8 strings 000 to 111.
Some standard values:
P(∅) = {∅}, which has 20 = 1 element.
P({∅}) = {∅, {∅}}, with 2 elements.
P(P({∅})) has 22 = 4 elements.
Cartesian Product
An ordered pair (a, b) is different from the set {a, b}: order matters, so (1, 2) ≠ (2, 1), and repetition is allowed, as in (3, 3). Two ordered pairs are equal exactly when (a, b) = (c, d) ⟺ a = c and b = d.
The Cartesian product of A and B is A × B = { (a, b) | a ∈ A and b ∈ B }.
Example: A = {1, 2}, B = {x, y, z}.
A × B = { (1,x), (1,y), (1,z), (2,x), (2,y), (2,z) } |A × B| = 2 × 3 = 6
B × A = { (x,1), (y,1), (z,1), (x,2), (y,2), (z,2) }
|A × B| = |A| · |B|.
A × B ≠ B × A in general (they are equal only when A = B or one of them is empty).
A × ∅ = ∅ × A = ∅.
More generally A1 × A2 × ⋯ × An is the set of n-tuples (a1, …, an). An means A × A × ⋯ × A (n times). For example, {0, 1}8 is the set of all bytes, with 28 = 256 elements.
Cartesian products are where relations live (a relation is a subset of A × B; see the Relations chapter) and where database tables come from (a table row is a tuple).
Set Operations
Let U be the universal set and A, B ⊆ U.
Operation | Notation | Definition | Logic counterpart |
|---|---|---|---|
Union | A ∪ B | { x | x ∈ A ∨ x ∈ B } | OR (∨) |
Intersection | A ∩ B | { x | x ∈ A ∧ x ∈ B } | AND (∧) |
Difference | A − B (or A \ B) | { x | x ∈ A ∧ x ∉ B } | p ∧ ¬q |
Complement | A′ (or Ā, Ac) | { x ∈ U | x ∉ A } = U − A | NOT (¬) |
Symmetric difference | A ⊕ B (or A Δ B) | (A − B) ∪ (B − A) | XOR (⊕) |
A and B are disjoint if A ∩ B = ∅.
Worked example
Let U = {1, 2, …, 10}, A = {1, 2, 3, 4, 5}, B = {4, 5, 6, 7}.
A ∪ B = {1, 2, 3, 4, 5, 6, 7}
A ∩ B = {4, 5}
A − B = {1, 2, 3}
B − A = {6, 7}
A ⊕ B = {1, 2, 3, 6, 7} (in exactly one of A, B)
A′ = {6, 7, 8, 9, 10}
Venn diagram view
Two sets split the universe into four regions. Every operation is just a choice of regions:
+-------------------------------- U -------+
| A B |
| +----------+------+----------+ |
| | | | | |
| | A − B | A∩B | B − A | |
| | {1,2,3} |{4,5} | {6,7} | |
| +----------+------+----------+ |
| |
| outside both: (A ∪ B)′ = {8, 9, 10} |
+------------------------------------------+
A ∪ B = all three inner regions
A ⊕ B = the two outer pieces, A − B and B − A
Generalised union and intersection
For sets A1, A2, …, An:
A1 ∪ A2 ∪ … ∪ An = { x | x ∈ Ai for at least one i }
A1 ∩ A2 ∩ … ∩ An = { x | x ∈ Ai for every i }
Example: if Ai = {1, 2, …, i}, then A1 ∪ ⋯ ∪ An = An = {1, …, n} and A1 ∩ ⋯ ∩ An = A1 = {1}.
Set Identities
Each identity below matches a logical equivalence, with ∪ ↔ ∨, ∩ ↔ ∧, complement ↔ ¬, U ↔ T and ∅ ↔ F.
Law | Union form | Intersection form |
|---|---|---|
Identity | A ∪ ∅ = A | A ∩ U = A |
Domination | A ∪ U = U | A ∩ ∅ = ∅ |
Idempotent | A ∪ A = A | A ∩ A = A |
Complement | A ∪ A′ = U | A ∩ A′ = ∅ |
Double complement | (A′)′ = A | (same law; it has no dual pair) |
Commutative | A ∪ B = B ∪ A | A ∩ B = B ∩ A |
Associative | A ∪ (B ∪ C) = (A ∪ B) ∪ C | A ∩ (B ∩ C) = (A ∩ B) ∩ C |
Distributive | A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C) | A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C) |
De Morgan | (A ∪ B)′ = A′ ∩ B′ | (A ∩ B)′ = A′ ∪ B′ |
Absorption | A ∪ (A ∩ B) = A | A ∩ (A ∪ B) = A |
Other useful facts: A − B = A ∩ B′; A ⊆ B ⟺ A ∪ B = B ⟺ A ∩ B = A ⟺ A ∩ B′ = ∅.
Duality: swap ∪ with ∩ and U with ∅ in any identity, and you get another valid identity. That is why the table has two columns.
Proving Set Identities
There are three standard methods. We will use each on a real identity.
Method 1: element argument (show both inclusions)
Claim. A − (B ∪ C) = (A − B) ∩ (A − C).
(⊆) Let x ∈ A − (B ∪ C). Then x ∈ A and x ∉ B ∪ C. Since x ∉ B ∪ C, x is in neither B nor C, so x ∉ B and x ∉ C. Hence x ∈ A − B and x ∈ A − C, so x ∈ (A − B) ∩ (A − C).
(⊇) Let x ∈ (A − B) ∩ (A − C). Then x ∈ A, x ∉ B and x ∉ C. So x is not in B ∪ C, and x ∈ A − (B ∪ C).
Both inclusions hold, so the sets are equal. ∎
Method 2: membership table
Like a truth table: 1 means "x is in the set", 0 means "not in". If two columns are identical in every row, the sets are equal. Here is De Morgan's law (A ∪ B)′ = A′ ∩ B′:
A | B | A ∪ B | (A ∪ B)′ | A′ | B′ | A′ ∩ B′ |
|---|---|---|---|---|---|---|
1 | 1 | 1 | 0 | 0 | 0 | 0 |
1 | 0 | 1 | 0 | 0 | 1 | 0 |
0 | 1 | 1 | 0 | 1 | 0 | 0 |
0 | 0 | 0 | 1 | 1 | 1 | 1 |
The two bold columns agree, so the identity holds. With k sets the table has 2k rows.
Method 3: algebra with known laws
Claim. (A ∩ B) ∪ (A ∩ B′) = A.
(A ∩ B) ∪ (A ∩ B′) = A ∩ (B ∪ B′) distributive
= A ∩ U complement
= A identity ∎
Disproving a set "identity"
To show a claimed identity is false, give a counterexample with small sets.
"(A − B) − C = A − (B − C)." False: take A = B = C = {1}. Left: ({1} − {1}) − {1} = ∅. Right: {1} − ∅ = {1}. So set difference is not associative.
"A ∪ B = A ∪ C implies B = C." False: A = {1}, B = {1}, C = ∅. Both unions are {1}, but B ≠ C. You cannot "cancel" A from a union (or an intersection).
Two cancellation laws that do hold (both checked by brute force over all subsets of a 5-element set):
If A ∪ B = A ∪ C and A ∩ B = A ∩ C, then B = C.
If A ⊕ B = A ⊕ C, then B = C (apply A ⊕ to both sides, since A ⊕ A = ∅ and ⊕ is associative).
Counting Elements of a Union
If we simply add |A| and |B|, the elements of A ∩ B are counted twice. Subtracting them once fixes it:
|A ∪ B| = |A| + |B| − |A ∩ B|
Example. In a class of 100 students, 60 know C++, 45 know Python and 25 know both.
Know at least one: 60 + 45 − 25 = 80.
Know neither: 100 − 80 = 20.
Know only C++: 60 − 25 = 35. Only Python: 45 − 25 = 20.
The general version for three or more sets is the subject of the Inclusion-Exclusion Principle chapter.
Sets in Programs
Python has a built-in set type whose operators mirror the mathematics:
from itertools import combinations, product
U = set(range(1, 11)) # universal set {1, ..., 10}
A = {1, 2, 3, 4, 5}
B = {4, 5, 6, 7}
print("A union B =", sorted(A | B))
print("A intersect B =", sorted(A & B))
print("A - B =", sorted(A - B))
print("B - A =", sorted(B - A))
print("A sym-diff B =", sorted(A ^ B))
print("complement of A =", sorted(U - A))
print("{1, 2} subset A? ", {1, 2} <= A)
def power_set(s):
items = sorted(s)
return [list(c) for r in range(len(items) + 1) for c in combinations(items, r)]
print("P({a,b,c}) =", power_set({'a', 'b', 'c'}))
print("|A x B| =", len(list(product(A, B))))
# De Morgan's law checked on every pair of subsets of a 4-element universe
U4 = {1, 2, 3, 4}
subsets = [set(s) for s in power_set(U4)]
ok = all(U4 - (X | Y) == (U4 - X) & (U4 - Y) for X in subsets for Y in subsets)
print("De Morgan holds for all", len(subsets) ** 2, "pairs:", ok)
Output:
A union B = [1, 2, 3, 4, 5, 6, 7]
A intersect B = [4, 5]
A - B = [1, 2, 3]
B - A = [6, 7]
A sym-diff B = [1, 2, 3, 6, 7]
complement of A = [6, 7, 8, 9, 10]
{1, 2} subset A? True
P({a,b,c}) = [[], ['a'], ['b'], ['c'], ['a', 'b'], ['a', 'c'], ['b', 'c'], ['a', 'b', 'c']]
|A x B| = 20
De Morgan holds for all 256 pairs: True
The last line is an exhaustive proof of De Morgan's law for a 4-element universe (16 × 16 = 256 pairs). The membership table is what proves it for every universe.
Bit-vector representation
When the universe is small, such as {0, 1, …, 63}, a set fits in one machine word: bit i is 1 exactly when i is in the set. Then set operations become single CPU instructions: ∪ is bitwise OR, ∩ is AND, complement is NOT, difference is AND NOT, and ⊕ is XOR. This trick is used in compilers (live-variable analysis), chess engines (bitboards) and the "bitmask DP" technique in competitive programming.
# Sets of small integers as bit masks: bit i is 1 when i is in the set
def to_mask(s):
m = 0
for x in s:
m |= 1 << x
return m
def to_set(m):
return {i for i in range(m.bit_length()) if m >> i & 1}
A = to_mask({1, 2, 3, 4, 5})
B = to_mask({4, 5, 6, 7})
print(f"A = {A:010b}")
print(f"B = {B:010b}")
print(f"A | B = {A | B:010b} ->", sorted(to_set(A | B)))
print(f"A & B = {A & B:010b} ->", sorted(to_set(A & B)))
print(f"A & ~B= {A & ~B:010b} ->", sorted(to_set(A & ~B)))
print(f"A ^ B = {A ^ B:010b} ->", sorted(to_set(A ^ B)))
Output:
A = 0000111110
B = 0011110000
A | B = 0011111110 -> [1, 2, 3, 4, 5, 6, 7]
A & B = 0000110000 -> [4, 5]
A & ~B= 0000001110 -> [1, 2, 3]
A ^ B = 0011001110 -> [1, 2, 3, 6, 7]
Read the bit strings from the right: bit 0 is the rightmost. The results match the worked example exactly.
A Warning from History: Russell's Paradox
Can any property define a set? Consider R = { S | S ∉ S }, the set of all sets that are not members of themselves. Is R ∈ R?
If R ∈ R, then R satisfies the defining property, so R ∉ R.
If R ∉ R, then R satisfies the property, so R ∈ R.
Both cases contradict themselves. Bertrand Russell found this in 1901, and it showed that "any collection is a set" leads to contradictions. Modern set theory (Zermelo–Fraenkel, ZFC) replaces "any property defines a set" with the separation axiom: a property P can only carve out a subset { x ∈ A | P(x) } of a set A that is already known to exist. That blocks the paradox. In everyday discrete mathematics we always work inside a fixed universe U, so the problem never arises. The same self-reference idea reappears in the proof that the halting problem is undecidable.
Multisets (Briefly)
Sometimes repetitions matter, for example the letters of the word "BANANA": {A, A, A, B, N, N}. Such a collection is a multiset (or bag). Each element has a multiplicity. Multisets appear in counting problems (combinations with repetition) and in databases (SQL tables can contain duplicate rows unless you use DISTINCT). Ordinary sets are multisets in which every multiplicity is 0 or 1.
Common Mistakes
Confusing ∈ and ⊆. 2 ∈ {1, 2} but {2} ⊆ {1, 2}; writing 2 ⊆ {1, 2} is meaningless.
Treating ∅ and {∅} as the same. |∅| = 0, |{∅}| = 1.
Counting repeated elements: |{1, 1, 2}| = 2, not 3.
Assuming A × B = B × A, or forgetting that pairs are ordered.
Cancelling in unions or intersections: A ∪ B = A ∪ C does not give B = C.
Assuming set difference is associative or commutative. It is neither.
Proving an identity with one Venn diagram drawing. A picture is a good guide, but a proof needs an element argument, a membership table or valid algebra.
Interview and GATE-Style Questions
Q1. Let A = {∅, {∅}}. Which are true: (a) ∅ ∈ A (b) ∅ ⊆ A (c) {∅} ∈ A (d) {∅} ⊆ A (e) {{∅}} ⊆ A?
All five are true. (a) and (c): both are listed elements. (b): ∅ is a subset of every set. (d): the only element of {∅} is ∅, which is in A. (e): the only element of {{∅}} is {∅}, which is in A.
Q2. What are |P(∅)|, |P(P(∅))| and |P(P(P(∅)))|?
1, 2 and 4. Since |P(A)| = 2|A|, each step raises 2 to the previous size: |∅| = 0 gives 20 = 1, then 21 = 2, then 22 = 4. (One more step would give 24 = 16.)
Q3. How many subsets of {1, 2, …, 10} contain 1 but not 2?
Elements 1 and 2 are fixed; each of the remaining 8 elements is free. 28 = 256.
Q4. If |A| = 3 and |B| = 4, how many elements does A × B have, and how many subsets does A × B have?
|A × B| = 12, so it has 212 = 4096 subsets. (Each such subset is a relation from A to B; see the Relations chapter.)
Q5. Simplify (A ∪ B) ∩ (A ∪ B′).
By the distributive law it equals A ∪ (B ∩ B′) = A ∪ ∅ = A. (It is the dual of the Method 3 example.)
Q6. Express A ⊕ B using only ∪, ∩ and complement, in two different ways.
A ⊕ B = (A ∩ B′) ∪ (A′ ∩ B) = (A ∪ B) ∩ (A ∩ B)′. Both say "in at least one, but not in both".
Q7. In a survey of 200 people, 120 use UPI, 90 use cards and 40 use both. How many use neither?
|UPI ∪ Card| = 120 + 90 − 40 = 170, so 200 − 170 = 30 use neither.
Summary
A set is an unordered collection of distinct elements; equality means same elements.
∅ ⊆ A always; A = B ⟺ A ⊆ B and B ⊆ A. Keep ∈ and ⊆ separate.
|P(A)| = 2|A|; |A × B| = |A| · |B|; ordered pairs care about order.
Union, intersection, complement, difference and symmetric difference correspond to OR, AND, NOT, "and not" and XOR.
Set identities mirror logical equivalences; prove them by element arguments, membership tables or algebra; disprove them with small counterexamples.
|A ∪ B| = |A| + |B| − |A ∩ B|.
Programs represent sets with hash sets or, for small universes, bit masks.
Sets are the alphabet of discrete mathematics. With them in hand, the next chapter, Functions, describes how elements of one set are assigned to elements of another.