2. Sets, Functions, and Relations

Sets, functions, and relations are the basic vocabulary of discrete mathematics. Almost every later object, including graphs, formal languages, probability spaces and database tables, is defined in terms of them. This chapter builds up sets and their operations, uses them to define functions and to compare the sizes of infinite sets, and then studies relations, including the equivalence relations and orders behind hashing, sorting, and dependency resolution. In code, the same ideas appear as set and dict, SQL joins, comparators, and the topological sort inside every build system.

<a id="21-set-theory"></a>

2.1 Set Theory

A set is an unordered collection of distinct objects. This subchapter covers how to describe sets, compare them, combine them, and reason about the results.

Set Notation and Builder Form

Why. "The small primes" and "the active users" are vague phrases. Mathematics and programs both need a precise way to say exactly which objects belong to a collection and which do not.

What. A set is a collection of distinct objects, called its elements or members. We write x ∈ A for "x is an element of A" and x ∉ A for "x is not an element of A". A set is determined completely by its members, which has two consequences:

• Order does not matter: {1, 2, 3} = {3, 1, 2}.
• Duplicates do not matter: {1, 1, 2} = {1, 2}.

There are two standard ways to describe a set:

Notation	Form	Example	Best for
Roster	List the elements	{2, 3, 5, 7}	Small, explicit sets
Roster with ellipsis	List enough elements to show a pattern	{1, 3, 5, 7, …}	Obvious patterns (use with care)
Set-builder	{x ∈ U | P(x)}	{x ∈ ℤ | x > 0 ∧ x is even}	Sets defined by a property
Set-builder (image form)	{f(x) | x ∈ U}	{n² | n ∈ ℕ}	Sets of computed values

Set-builder notation {x ∈ U | P(x)} reads "the set of all x in U such that P(x)". It is a predicate (1.2) turned into a collection: the set contains exactly the elements of U for which the predicate is true.

Standard sets.

Symbol	Set	Elements
ℕ	Natural numbers	{0, 1, 2, 3, …} (some texts start at 1; this guide includes 0)
ℤ	Integers	{…, −2, −1, 0, 1, 2, …}
ℤ⁺	Positive integers	{1, 2, 3, …}
ℚ	Rational numbers	{a/b | a, b ∈ ℤ, b ≠ 0}
ℝ	Real numbers	All points on the number line
∅ or {}	Empty set	No elements
U	Universal set	Everything under discussion in the current context

Sets of sets. Sets can contain other sets. The set {∅} is not empty: it has exactly one element, namely the empty set. Think of ∅ as an empty box and {∅} as a box that contains an empty box.

Analogy. A set is like a guest list checked by a doorman. The only question it answers is "is this person on the list?". The order of the names is irrelevant, and writing a name twice does not admit the person twice.

Why the domain U matters. Unrestricted set-builder notation leads to contradictions. Russell's paradox defines R = {x | x ∉ x} (the set of all sets that do not contain themselves) and asks whether R ∈ R. Either answer implies the other, the same self-reference as "This sentence is false" (1.1). Writing {x ∈ U | P(x)}, which only selects from an existing set U, avoids the problem.

primes_small = {2, 3, 5, 7}                        # roster notation
print({1, 2, 3} == {3, 1, 2, 2})                   # True: order and duplicates are ignored

# Set-builder {x ∈ U | P(x)} maps directly onto a set comprehension
U = range(1, 21)
evens = {x for x in U if x % 2 == 0}               # {x ∈ U | x is even}
squares = {n * n for n in range(1, 6)}             # {n² | n ∈ {1, …, 5}} = {1, 4, 9, 16, 25}

print(4 in evens, 5 in evens)                      # True False   (∈ and ∉)

empty = set()                                      # ∅  (note: {} is an empty dict in Python)
box_with_empty_box = {frozenset()}                 # {∅}: elements of a set must be hashable
print(len(empty), len(box_with_empty_box))         # 0 1

Key takeaways

• A set is determined only by which elements it contains. Order and repetition are irrelevant.
• Roster notation lists elements. Set-builder notation {x ∈ U | P(x)} selects elements by a predicate.
• ∅ has no elements, while {∅} has one element.
• Always build sets from a known domain U. Unrestricted comprehension leads to Russell's paradox.

Practice

1. (Beginner) Write in roster notation: {x ∈ ℤ | x² < 10} and {2n + 1 | n ∈ {0, 1, 2, 3}}.
2. (Intermediate) Write the set of positive integers that are multiples of 3 or of 5 in set-builder notation. How many elements does {∅, {∅}, {∅, {∅}}} have, and what are they?
3. (Interview) Python rejects {{1, 2}, {3}} but accepts {frozenset({1, 2}), frozenset({3})}. Why must the elements of a hash-based set be immutable? Hint: think about what happens to a hash table when an element changes after it has been inserted.

Subsets and Equality

Why. Many practical questions compare two collections. "Is every admin also a registered user?" is a subset question. "Do these two queries return the same rows?" is an equality question. Both need precise definitions, and equality of sets has its own standard proof technique.

What.

Concept	Notation	Definition
Subset	A ⊆ B	∀x (x ∈ A → x ∈ B): every element of A is in B
Proper subset	A ⊂ B (or A ⊊ B)	A ⊆ B and A ≠ B: B has at least one extra element
Superset	B ⊇ A	Same as A ⊆ B
Equality	A = B	A ⊆ B and B ⊆ A

Two facts follow immediately from the definition:

• A ⊆ A for every set A.
• ∅ ⊆ A for every set A. The condition x ∈ ∅ → x ∈ A has a false hypothesis for every x, so it is vacuously true (1.1).

Element-of vs subset-of. These are easy to confuse, especially when sets contain sets:

Statement	True?	Reason
1 ∈ {1, 2}	Yes	1 is one of the listed elements
{1} ⊆ {1, 2}	Yes	Every element of {1} is in {1, 2}
{1} ∈ {1, 2}	No	The elements are the numbers 1 and 2, not the set {1}
∅ ⊆ {1}	Yes	The empty set is a subset of every set
∅ ∈ {1}	No	The only element is 1
∅ ∈ {∅} and ∅ ⊆ {∅}	Both yes	∅ is listed as an element, and is also a subset of everything

How: proving A ⊆ B. Take an arbitrary element x ∈ A and show x ∈ B. This is a direct proof (1.4) of a universally quantified conditional.

Example. {x ∈ ℤ | 6 ∣ x} ⊆ {x ∈ ℤ | 2 ∣ x}. Let x be an integer with 6 ∣ x, so x = 6k for some integer k. Then x = 2(3k), so 2 ∣ x. ∎

How: proving A = B (double inclusion). Prove A ⊆ B and B ⊆ A separately.

Example. {n ∈ ℤ | n² is even} = {n ∈ ℤ | n is even}. (⊆) If n² is even, then n is even. This was proved by contrapositive in 1.4. (⊇) If n = 2k, then n² = 4k² = 2(2k²), which is even. ∎

  B
  ┌─────────────────────────────┐
  │  A                          │      A ⊂ B: every point of A lies inside B,
  │  ┌──────────────┐           │      and B has points outside A
  │  │   x ∈ A      │   y ∈ B   │
  │  └──────────────┘   y ∉ A   │
  └─────────────────────────────┘

admins = {"ana"}
users = {"ana", "ben", "cleo"}

print(admins <= users)          # True   A ⊆ B
print(admins < users)           # True   A ⊂ B (proper)
print(users <= users)           # True   every set is a subset of itself
print(users < users)            # False  but not a proper subset
print(set() <= admins)          # True   ∅ ⊆ A
print({"ana", "ana"} == admins) # True   equality ignores duplicates

Key takeaways

• A ⊆ B means every element of A is also in B. ∅ ⊆ A and A ⊆ A always hold.
• ∈ relates an element to a set. ⊆ relates two sets. Do not mix them up.
• Prove A ⊆ B by taking an arbitrary x ∈ A and showing x ∈ B.
• Prove A = B by double inclusion: A ⊆ B and B ⊆ A.

Practice

1. (Beginner) True or false: ∅ ∈ ∅, ∅ ⊆ ∅, {1} ∈ {{1}, 2}, {1} ⊆ {{1}, 2}, {{1}} ⊆ {{1}, 2}.
2. (Intermediate) Prove that ⊆ is transitive: if A ⊆ B and B ⊆ C, then A ⊆ C.
3. (Interview) You receive two unsorted lists of n user IDs each, possibly with duplicates. Decide whether they contain the same set of IDs. Compare a nested-loop approach, a sorting approach, and a hashing approach in time and memory. Hint: equality is double inclusion. What does a hash set make cheap?

Power Sets

Why. Many problems are "try every combination": every subset of features to enable, every selection of items for a knapsack, every set of servers that might fail together. The collection of all subsets of a set has a name and a predictable size.

What. The power set of A is the set of all subsets of A:

P(A) = { S | S ⊆ A }

For A = {a, b, c}:

P(A) = { ∅, {a}, {b}, {c}, {a,b}, {a,c}, {b,c}, {a,b,c} }

If |A| = n, then |P(A)| = 2ⁿ. To build a subset, you make an independent yes/no decision for each of the n elements, which gives 2 · 2 · … · 2 = 2ⁿ possibilities. Note that P(∅) = {∅} has one element, matching 2⁰ = 1.

Subsets as bit strings. List the elements in a fixed order. Then each subset corresponds to exactly one n-bit string, with bit i equal to 1 if and only if element i is included. This correspondence (a bijection, see 2.2) is how programs enumerate subsets:

Mask (decimal)	Bits c b a	Subset
0	000	∅
1	001	{a}
2	010	{b}
3	011	{a, b}
4	100	{c}
5	101	{a, c}
6	110	{b, c}
7	111	{a, b, c}

from itertools import chain, combinations

def power_set(items):
    """All subsets of items, enumerated with bitmasks."""
    items = list(items)
    n = len(items)
    result = []
    for mask in range(1 << n):                                    # 2^n masks: 0 … 2^n − 1
        subset = {items[i] for i in range(n) if mask & (1 << i)}  # bit i set -> include items[i]
        result.append(subset)
    return result

print(len(power_set("abc")))       # 8
print(len(power_set(range(10))))   # 1024: doubling with every extra element

# Equivalent standard-library recipe: all combinations of size 0, 1, …, n
def power_set_itertools(items):
    items = list(items)
    return chain.from_iterable(combinations(items, k) for k in range(len(items) + 1))

Cost. Because |P(A)| doubles with each added element, brute-force search over subsets works for about 20 to 25 elements and becomes infeasible soon after. This is the same exponential growth seen with truth tables (1.1).

Key takeaways

• P(A) is the set of all subsets of A, including ∅ and A itself.
• |P(A)| = 2^|A|, because each element is independently in or out.
• Subsets of an n-element set correspond one-to-one with n-bit strings, which makes them easy to enumerate with bitmasks.
• Algorithms that try every subset run in Ω(2ⁿ) time.

Practice

1. (Beginner) List all elements of P({1, 2}) and of P({∅}).
2. (Intermediate) Prove that A ⊆ B if and only if P(A) ⊆ P(B).
3. (Interview) Given n ≤ 20 integers and a target t, decide whether some subset sums to t. Describe a bitmask solution and its running time. Why does it become impractical near n = 40, and how could splitting the input in half help? Hint: each half has only 2^(n/2) subsets. Sort one list of sums and search it.

Cartesian Products

Why. Sets ignore order, but many objects are naturally ordered: a point (x, y), a cell (row, column), a database row (id, name, email). We need a construction in which position matters.

What. An ordered pair (a, b) has a first component and a second component, and

(a, b) = (c, d)   if and only if   a = c and b = d

So (1, 2) ≠ (2, 1), whereas {1, 2} = {2, 1}. The Cartesian product of A and B is the set of all ordered pairs with the first component from A and the second from B:

A × B = { (a, b) | a ∈ A and b ∈ B }

More generally, A₁ × A₂ × … × Aₙ is the set of n-tuples (a₁, …, aₙ), and Aⁿ means A × A × … × A (n times). For example, ℝ² is the plane and {0, 1}⁸ is the set of all bytes.

Properties:

• |A × B| = |A| · |B| for finite sets. This is the product rule of counting (Chapter 5).
• A × ∅ = ∅, because there is no second component to choose.
• A × B ≠ B × A in general. They are equal only if A = B or one of them is empty.

              B = {x, y, z}
             x        y        z
         ┌────────┬────────┬────────┐
A    1   │ (1,x)  │ (1,y)  │ (1,z)  │      |A × B| = 2 · 3 = 6
=        ├────────┼────────┼────────┤
{1,2} 2  │ (2,x)  │ (2,y)  │ (2,z)  │
         └────────┴────────┴────────┘

Pairs from sets. Ordered pairs do not need to be a new primitive. Kuratowski's definition (a, b) = {{a}, {a, b}} builds them from sets alone and satisfies the equality rule above. This is one reason set theory can serve as a foundation for the rest of mathematics.

In code. Nested loops over two collections iterate over their Cartesian product. In SQL, CROSS JOIN computes it.

from itertools import product

ranks = ["A", "K", "Q"]
suits = ["S", "H"]                               # spades, hearts

cards = list(product(ranks, suits))              # ranks × suits
print(cards)        # [('A', 'S'), ('A', 'H'), ('K', 'S'), ('K', 'H'), ('Q', 'S'), ('Q', 'H')]
print(len(cards))   # 6 = 3 · 2

# The same product as nested loops: the outer loop is the first component
same = [(r, s) for r in ranks for s in suits]
print(same == cards)                             # True

bytes_ = list(product([0, 1], repeat=8))         # {0, 1}^8
print(len(bytes_))                               # 256

Key takeaways

• In an ordered pair, position matters: (a, b) = (c, d) exactly when a = c and b = d.
• A × B is the set of all pairs (a, b) with a ∈ A and b ∈ B, and |A × B| = |A| · |B|.
• The Cartesian product is not commutative, and A × ∅ = ∅.
• Nested loops, itertools.product, and SQL CROSS JOIN all compute Cartesian products.

Practice

1. (Beginner) Let A = {0, 1} and B = {a, b, c}. List A × B and B × A. Are they equal?
2. (Intermediate) Prove that A × (B ∪ C) = (A × B) ∪ (A × C) by double inclusion.
3. (Interview) A test matrix covers 4 operating systems, 3 browsers, and 5 screen sizes. How many configurations are there? Many teams test far fewer. What property should a reduced test set keep? Hint: look up pairwise (all-pairs) testing. Every pair of values from any two factors should appear in at least one test.

Set Operations

Why. Most questions about collections combine them: who is enrolled in both courses, in either one, in only one, or in neither? Set operations answer these, and each one corresponds to a logical connective from Chapter 1.

What. Let A and B be subsets of a universal set U.

Operation	Notation	Definition	Logic	Python	SQL
Union	A ∪ B	{x | x ∈ A ∨ x ∈ B}	∨	A | B	UNION
Intersection	A ∩ B	{x | x ∈ A ∧ x ∈ B}	∧	A & B	INTERSECT
Difference	A − B (or A \ B)	{x | x ∈ A ∧ x ∉ B}	p ∧ ¬q	A - B	EXCEPT
Symmetric difference	A Δ B (or A ⊕ B)	(A − B) ∪ (B − A)	⊕	A ^ B	(no direct keyword)
Complement	Ā (or Aᶜ)	{x ∈ U | x ∉ A}	¬	U - A	NOT IN

Sets A and B are disjoint if A ∩ B = ∅. Operations extend to families of sets: ⋃ᵢ Aᵢ contains every element that belongs to at least one Aᵢ, and ⋂ᵢ Aᵢ contains every element that belongs to all of them.

Counting. For finite sets, adding |A| and |B| counts the elements of A ∩ B twice, so

|A ∪ B| = |A| + |B| − |A ∩ B|

This is the simplest case of inclusion–exclusion (Chapter 5).

python_students = {"ana", "ben", "cleo", "dev"}
java_students = {"cleo", "dev", "eli"}

print(sorted(python_students | java_students))   # ['ana', 'ben', 'cleo', 'dev', 'eli']   ∪
print(sorted(python_students & java_students))   # ['cleo', 'dev']                        ∩
print(sorted(python_students - java_students))   # ['ana', 'ben']                         −
print(sorted(python_students ^ java_students))   # ['ana', 'ben', 'eli']                  Δ

# Inclusion–exclusion check: 5 = 4 + 3 − 2
assert len(python_students | java_students) == \
       len(python_students) + len(java_students) - len(python_students & java_students)

# Sets over a small universe as bitmasks: element i is present iff bit i is set.
# Set operations become single CPU instructions.
U = 0b1111_1111            # universe {0, …, 7}
A = 0b0000_1111            # {0, 1, 2, 3}
B = 0b0011_1100            # {2, 3, 4, 5}
print(bin(A | B))          # 0b111111      {0, …, 5}        union
print(bin(A & B))          # 0b1100        {2, 3}           intersection
print(bin(A & ~B))         # 0b11          {0, 1}           difference
print(bin(A ^ B))          # 0b110011      {0, 1, 4, 5}     symmetric difference
print(bin(U & ~A))         # 0b11110000    {4, …, 7}        complement within U

Key takeaways

• Union, intersection, difference, symmetric difference, and complement correspond to ∨, ∧, p ∧ ¬q, ⊕, and ¬.
• The complement is always taken relative to a universal set U.
• |A ∪ B| = |A| + |B| − |A ∩ B| for finite sets.
• Over a small universe, bitmasks implement set operations with bitwise operators.

Practice

1. (Beginner) Let U = {1, …, 10}, A = {1, 2, 3, 4, 5}, B = {4, 5, 6, 7}. Compute A ∪ B, A ∩ B, A − B, B − A, A Δ B, and Ā.
2. (Intermediate) Prove A − B = A ∩ B̄ by double inclusion.
3. (Interview) Given two sorted arrays of distinct integers of lengths n and m, compute their intersection in O(n + m) time and O(1) extra space (not counting the output). Hint: use one pointer per array and always advance the pointer at the smaller value.

Set Identities

Why. Set expressions such as filters, permission rules, and query conditions can often be simplified or rearranged. Set identities are the algebraic laws that make this safe. Each one is a logical equivalence from 1.1 in disguise, because x ∈ A ∪ B means exactly x ∈ A ∨ x ∈ B.

What.

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 ∪ Ā = U	A ∩ Ā = ∅
Double complement	(Ā)‾ = A
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)‾ = Ā ∩ B̄	(A ∩ B)‾ = Ā ∪ B̄
Absorption	A ∪ (A ∩ B) = A	A ∩ (A ∪ B) = A

The table has a duality: swap ∪ ↔ ∩ and ∅ ↔ U in any identity and you get another identity.

How: three ways to prove an identity.

1. Double inclusion. Show each side is a subset of the other by following an arbitrary element.
2. Set-builder and logic. Rewrite each side as {x | …} and transform the condition with logical equivalences.
3. Membership table. Like a truth table: one row for each combination of "in / not in" for the sets involved. If the two final columns match, the identity holds.

Method 2, De Morgan:

(A ∩ B)‾ = { x | ¬(x ∈ A ∧ x ∈ B) }          definition of complement and ∩
         = { x | ¬(x ∈ A) ∨ ¬(x ∈ B) }        De Morgan's law for logic (1.1)
         = { x | x ∈ Ā ∨ x ∈ B̄ }              definition of complement
         = Ā ∪ B̄                               definition of ∪            ∎

Method 3, distributive law A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C) (1 = in, 0 = not in):

A	B	C	B ∪ C	A ∩ (B ∪ C)	A ∩ B	A ∩ C	(A ∩ B) ∪ (A ∩ C)
1	1	1	1	1	1	1	1
1	1	0	1	1	1	0	1
1	0	1	1	1	0	1	1
1	0	0	0	0	0	0	0
0	1	1	1	0	0	0	0
0	1	0	1	0	0	0	0
0	0	1	1	0	0	0	0
0	0	0	0	0	0	0	0

A membership table is a complete proof for any identity built from ∪, ∩, −, and complement. Each row describes one region of the Venn diagram, and every element of U falls into exactly one region.

from itertools import product

def membership_table_equal(lhs, rhs, k):
    """Check a k-set identity row by row: each row says whether x is in each set."""
    for row in product([True, False], repeat=k):
        if lhs(*row) != rhs(*row):
            return False, row                    # this region is a counterexample
    return True, None

# A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C)
print(membership_table_equal(lambda a, b, c: a and (b or c),
                             lambda a, b, c: (a and b) or (a and c), 3))
# (True, None)

# A tempting but false "identity": A − (B − C) = (A − B) − C
print(membership_table_equal(lambda a, b, c: a and not (b and not c),
                             lambda a, b, c: (a and not b) and not c, 3))
# (False, (True, True, True)): an x in all three sets is on the left side but not the right

Key takeaways

• Every set identity mirrors a logical equivalence. ∪, ∩, complement correspond to ∨, ∧, ¬.
• Prove identities by double inclusion, by set-builder notation plus logic, or with a membership table.
• Duality: swapping ∪ ↔ ∩ and ∅ ↔ U turns one identity into another.
• Set difference is neither commutative nor associative. Check before regrouping it.

Practice

1. (Beginner) Simplify (A ∪ B) ∩ (A ∪ B̄) using the laws in the table, naming each law you use.
2. (Intermediate) Prove the absorption law A ∪ (A ∩ B) = A by double inclusion, then again with a membership table.
3. (Interview) A query has the filter WHERE NOT (status IN ('archived', 'deleted') OR region = 'eu'). Rewrite it without the outer NOT so that each condition is a simple positive or negative test on one column. Which identity justifies the rewrite? Hint: the set of rows that pass a filter behaves like a set, and NOT is complement.

Venn Diagrams

Why. For two or three sets, a picture is often the fastest way to understand an expression, to see which elements it includes, or to solve a counting problem. Venn diagrams make set operations visual.

What. A rectangle represents the universal set U, and each set is a closed region inside it. With n sets drawn in general position, the diagram has 2ⁿ regions, one for each combination of "inside / outside" each set, including the region outside all of them. An expression is shown by shading the regions it contains.

U
┌───────────────────────────────────────────────┐
│                                               │
│   A ┌─────────────────────┐                   │
│     │                     │                   │
│     │   A − B    ┌────────┼───────────┐ B     │
│     │            │ A ∩ B  │   B − A   │       │
│     └────────────┼────────┘           │       │
│                  │                    │       │
│                  └────────────────────┘       │
│                                  (A ∪ B)‾     │
└───────────────────────────────────────────────┘

Three sets. Three overlapping circles create 8 regions, which the table below labels by membership (1 = inside). Shading an expression means selecting rows. For example, A ∩ (B ∪ C) is regions 1, 2, and 3.

Region	A	B	C	Description
1	1	1	1	A ∩ B ∩ C
2	1	1	0	in A and B only
3	1	0	1	in A and C only
4	1	0	0	only A
5	0	1	1	in B and C only
6	0	1	0	only B
7	0	0	1	only C
8	0	0	0	outside all three

The rows are exactly the rows of a membership table. A Venn diagram is a drawing of that table.

Counting with regions. 100 developers were surveyed. 60 use Python, 45 use Java, and 20 use both. Fill the regions from the inside out:

both          = 20
Python only   = 60 − 20 = 40
Java only     = 45 − 20 = 25
neither       = 100 − (40 + 20 + 25) = 15

Limitations. With four or more sets, circles can no longer produce all 2ⁿ regions, so more complicated shapes are needed. A diagram also shows only one configuration of the sets, so it can suggest an identity but cannot prove one. Use a membership table or an element argument for proofs.

def venn_regions(U, **sets):
    """Group each element of U by the exact combination of sets that contain it."""
    names = list(sets)
    regions = {}
    for x in U:
        key = tuple(name for name in names if x in sets[name]) or ("outside",)
        regions.setdefault(key, set()).add(x)
    return regions

U = range(1, 16)
regions = venn_regions(U,
                       even={x for x in U if x % 2 == 0},
                       mult3={x for x in U if x % 3 == 0},
                       mult5={x for x in U if x % 5 == 0})
for key, members in sorted(regions.items()):
    print(key, sorted(members))
# ('even',) [2, 4, 8, 14]
# ('even', 'mult3') [6, 12]
# ('even', 'mult5') [10]
# ('mult3',) [3, 9]
# ('mult3', 'mult5') [15]
# ('mult5',) [5]
# ('outside',) [1, 7, 11, 13]

Key takeaways

• A Venn diagram shows U as a rectangle and each set as a region. n sets give 2ⁿ regions.
• Each region corresponds to one row of a membership table.
• For counting problems, fill the innermost region first and work outward.
• Diagrams help intuition and checking. They are not proofs.

Practice

1. (Beginner) Sketch a two-set Venn diagram and shade (A − B) ∪ (B − A). Which operation from the table in Set Operations is this?
2. (Intermediate) In a class of 60 students, 30 take Math, 25 take CS, 18 take Physics, 10 take Math and CS, 8 take Math and Physics, 6 take CS and Physics, and 3 take all three. How many take none of the three? Fill all 8 regions.
3. (Interview) A colleague "proves" A − (B ∩ C) = (A − B) ∩ (A − C) by drawing a Venn diagram where the two shaded areas look the same. Is the identity true? Explain why the picture is not enough. Hint: check the region inside A and B but outside C.

Multisets

Why. Sets discard duplicates, but sometimes repetition carries information: the words in a document, the items in a shopping cart, or the prime factors of a number (12 = 2 · 2 · 3). A multiset keeps track of how many times each element occurs while still ignoring order.

What. A multiset over U is described by a multiplicity function m: U → ℕ, where m(x) is the number of copies of x. It can be written {a, a, b}, {a², b}, or {a: 2, b: 1}. Its cardinality is the sum of all multiplicities.

Collection	Order matters?	Duplicates matter?	Python type
Sequence (list, tuple)	Yes	Yes	list, tuple
Set	No	No	set, frozenset
Multiset (bag)	No	Yes	collections.Counter

Operations are defined element by element on multiplicities:

Operation	Multiplicity of x in the result	Counter
Union A ∪ B	max(m_A(x), m_B(x))	A | B
Intersection A ∩ B	min(m_A(x), m_B(x))	A & B
Sum A ⊎ B	m_A(x) + m_B(x)	A + B
Difference A − B	max(m_A(x) − m_B(x), 0)	A - B

When all multiplicities are 0 or 1, union, intersection, and difference reduce to the ordinary set operations.

Example: gcd and lcm. The prime factorization of a number is a multiset of primes. The gcd of two numbers is the product of the intersection of their factor multisets (minimum exponents), and the lcm is the product of the union (maximum exponents). Chapter 4 develops this further.

from collections import Counter
from math import prod

print(Counter("listen") == Counter("silent"))      # True: anagrams are equal as multisets
print(set("aab") == set("abb"))                    # True as sets...
print(Counter("aab") == Counter("abb"))            # False as multisets: multiplicities differ

def factor(n):
    """Prime factorization of n as a multiset {prime: exponent}."""
    f, p = Counter(), 2
    while p * p <= n:
        while n % p == 0:
            f[p] += 1
            n //= p
        p += 1
    if n > 1:
        f[n] += 1                                  # leftover factor is prime
    return f

a, b = factor(360), factor(84)                     # 360 = 2³·3²·5,  84 = 2²·3·7
gcd = prod(p ** k for p, k in (a & b).items())     # min exponents: 2²·3       = 12
lcm = prod(p ** k for p, k in (a | b).items())     # max exponents: 2³·3²·5·7  = 2520
print(gcd, lcm)                                    # 12 2520

Key takeaways

• A multiset ignores order but keeps multiplicities. Formally it is a function m: U → ℕ.
• Multiset union and intersection take the max and min of multiplicities, and the sum adds them.
• In Python, collections.Counter is a multiset.
• Prime factorizations, word counts, and anagram checks are all multiset problems.

Practice

1. (Beginner) Let A = {a, a, b, c} and B = {a, b, b, d}. Compute A ∪ B, A ∩ B, A ⊎ B, and A − B.
2. (Intermediate) List all multisets of size 2 whose elements come from {x, y, z}. How many are there, and how does this compare with the number of 2-element subsets?
3. (Interview) Given a string s and a pattern p, return every index where a substring of s is an anagram of p. Aim for O(|s|) time for a fixed alphabet. Hint: slide a window of length |p| across s and update a character-count multiset by one addition and one removal per step.

<a id="22-functions"></a>

2.2 Functions

A function assigns to each input exactly one output. Defining functions precisely, as special sets of pairs, makes properties like "lossless", "covers every output", and "invertible" exact. These properties matter for encodings, hashing, and comparing the sizes of sets.

Domain, Codomain, and Range

Why. In a program, a function signature such as int -> int promises which inputs are accepted and what kind of value comes back. Mathematics makes the same promise, and also separates the declared type of the outputs from the outputs the function actually produces.

What. A function f: A → B assigns to each element a ∈ A exactly one element f(a) ∈ B. Formally, f is a subset of A × B in which every a ∈ A appears as a first component exactly once.

Term	Notation	Meaning	Programming analogue
Domain	A	Allowed inputs	Parameter type
Codomain	B	Declared kind of output	Return type
Range (image)	f(A) = {f(a) | a ∈ A}	Outputs actually produced, f(A) ⊆ B	Values a call can really return
Image of a subset	f(S) = {f(a) | a ∈ S}	Outputs produced by inputs in S	{f(x) for x in S}
Preimage	f⁻¹(T) = {a ∈ A | f(a) ∈ T}	Inputs that land in T	"Which inputs give these results?"

There are two ways to fail to be a function:

• Not total: some input has no output (f(x) = 1/x on ℝ has no value at 0). A rule that is undefined on some inputs is called a partial function.
• Not well-defined: some input has two outputs (f(x) = ±√x).

   A = {1, 2, 3}          B = {a, b, c, d}

      1 ───────────────►  a
                          b      no arrow arrives: b is not in the range
      2 ──────────┐
                  ├────►  c      two arrows arrive: allowed for a function
      3 ──────────┘
                          d

   domain = {1, 2, 3}    codomain = {a, b, c, d}    range = {a, c}

Every element of the domain sends out exactly one arrow. Elements of the codomain may receive zero, one, or many arrows.

Example. f: ℤ → ℤ, f(x) = x². The domain and codomain are both ℤ, the range is {0, 1, 4, 9, …}, f⁻¹({4}) = {−2, 2}, and f⁻¹({3}) = ∅.

Equality. Two functions are equal when they have the same domain, the same codomain, and the same value on every input. The rule used to compute them does not matter: f(x) = (x + 1)² and g(x) = x² + 2x + 1 are the same function on ℝ.

def is_function(pairs, domain):
    """Is this set of (input, output) pairs a total, well-defined function on domain?"""
    outputs = {}
    for a, b in pairs:
        if a in outputs and outputs[a] != b:
            return False                       # a has two different outputs: not well-defined
        outputs[a] = b
    return set(outputs) == set(domain)         # every input needs an output: total

f = {1: "a", 2: "c", 3: "c"}                   # a dict is a finite function
print(is_function(f.items(), {1, 2, 3}))       # True
print(is_function({(1, "a"), (1, "b")}, {1}))  # False

image = set(f.values())                                   # range: {'a', 'c'}
preimage = lambda T: {a for a, b in f.items() if b in T}  # f⁻¹(T)
print(sorted(image), preimage({"c"}), preimage({"b"}))    # ['a', 'c'] {2, 3} set()

Key takeaways

• A function assigns every element of its domain exactly one output.
• The codomain is the declared target. The range is the set of values actually produced, and it is a subset of the codomain.
• The preimage f⁻¹(T) is defined for every function, whether or not f has an inverse.
• Functions are equal when they agree on domain, codomain, and every value.

Practice

1. (Beginner) For f: ℤ → ℤ with f(n) = |n| + 1, give the domain, codomain, and range, and compute f⁻¹({3}) and f⁻¹({0}).
2. (Intermediate) Which of these define a function ℝ → ℝ? f(x) = 1/x, f(x) = √x, f(x) = ±√(x² + 1), f(x) = ⌊x⌋. For each failure, say whether it fails totality or well-definedness.
3. (Interview) A function is annotated def parse(s: str) -> int, but it raises an exception on some inputs. In the mathematical sense, is it a function from str to int? How do Optional[int] or a Result type change the answer? Hint: think of it as a partial function, and consider what happens when you enlarge the codomain.

Injective Functions

Why. An injective function never sends two inputs to the same output, so no information is lost and the input can always be recovered from the output. Unique identifiers, database primary keys, and lossless encoders all rely on this property.

What. f: A → B is injective (one-to-one) if different inputs always give different outputs:

∀a₁, a₂ ∈ A   ( f(a₁) = f(a₂)  →  a₁ = a₂ )

The contrapositive form, a₁ ≠ a₂ → f(a₁) ≠ f(a₂), is often easier to read, but the form above is easier to prove.

  Injective                      Not injective
  1 ──────► a                    1 ──────► a
  2 ──────► b                    2 ───┐
  3 ──────► c                    3 ───┴──► b     two inputs collide
            d                              c

How.

• To prove injectivity: assume f(a₁) = f(a₂) and derive a₁ = a₂ with algebra.
• To disprove it: find two distinct inputs with the same output (a counterexample, 1.4).

Example. f: ℝ → ℝ, f(x) = 3x + 7 is injective. Assume 3a₁ + 7 = 3a₂ + 7. Subtracting 7 and dividing by 3 gives a₁ = a₂. ∎

Example. g(x) = x² is not injective on ℝ, because g(−1) = g(1). On ℕ it is injective. The same rule can be injective or not depending on the domain.

Any strictly increasing or strictly decreasing function is injective, since distinct inputs are ordered and their outputs keep that strict order.

Finite sets and collisions. If f: A → B is injective and both sets are finite, then |A| ≤ |B|. A function from a larger set to a smaller one must have collisions. This is the pigeonhole principle (Chapter 5), and it is why every hash function that maps arbitrarily long inputs to fixed-size digests has collisions.

def is_injective(f: dict) -> bool:
    return len(set(f.values())) == len(f)       # no output value is repeated

print(is_injective({x: 3 * x + 7 for x in range(-50, 50)}))   # True
print(is_injective({x: x * x for x in range(-50, 50)}))       # False: (-1)² = 1²

# Pigeonhole in practice: 9 keys into 8 buckets must collide
keys = ["k0", "k1", "k2", "k3", "k4", "k5", "k6", "k7", "k8"]
buckets = {k: hash(k) % 8 for k in keys}
print(is_injective(buckets))                                  # False, whatever the hash values

Key takeaways

• Injective means distinct inputs give distinct outputs: f(a₁) = f(a₂) → a₁ = a₂.
• Prove it by assuming equal outputs and deriving equal inputs. Disprove it with one collision.
• Restricting the domain can make a non-injective rule injective.
• For finite sets, an injection A → B requires |A| ≤ |B|, so compressing into a smaller set always causes collisions.

Practice

1. (Beginner) Is f: ℤ → ℤ, f(n) = n + 7 injective? Is g: ℤ → ℤ, g(n) = n mod 5? Justify each answer.
2. (Intermediate) Prove that f(x) = (3x − 1)/(x + 2) is injective on ℝ − {−2}.
3. (Interview) A URL shortener maps long URLs to 7-character codes over the 62 characters [A-Za-z0-9]. Can this mapping be injective? What design makes it injective in practice? Hint: compare 62⁷ with the number of URLs you will store, and compare hashing the URL with assigning codes from a counter.

Surjective Functions

Why. A surjective function reaches every possible output. You want this for a hash function that should be able to use every bucket, for a decoder that should be able to produce every message, and whenever every element of a target must be "covered".

What. f: A → B is surjective (onto) if every element of the codomain is the image of at least one input:

∀b ∈ B  ∃a ∈ A  ( f(a) = b )

Equivalently, the range equals the codomain: f(A) = B.

  Surjective                     Not surjective
  1 ──────► a                    1 ──────► a
  2 ───┐                         2 ──────► b
  3 ───┴──► b                              c     never hit

How.

• To prove surjectivity: take an arbitrary b ∈ B, solve f(a) = b for a, and check that the solution really lies in A.
• To disprove it: find a b that has no preimage.

Example. f: ℤ → ℤ, f(n) = n − 3 is onto. Given any integer b, take a = b + 3, which is an integer, and f(a) = b. ∎

Example. g: ℤ → ℤ, g(n) = 2n is not onto, because 2n = 1 has no integer solution. The same rule on ℝ → ℝ is onto, since a = b/2 is a real number. The check "is the solution in A?" decides the answer.

Example. x ↦ x² is not onto as a map ℝ → ℝ (−1 is never reached), but it is onto as a map ℝ → [0, ∞). Surjectivity depends on the codomain.

	Injective	Surjective
Informal	No collisions	No missed outputs
Logic	∀a₁ ∀a₂ (f(a₁) = f(a₂) → a₁ = a₂)	∀b ∃a (f(a) = b)
Arrows into each b ∈ B	At most one	At least one
Proof pattern	Assume equal outputs, derive equal inputs	Given b, construct a
Finite sets	|A| ≤ |B|	|A| ≥ |B|
Depends on	Mostly the domain	Mostly the codomain

def is_surjective(f: dict, codomain) -> bool:
    return set(f.values()) == set(codomain)     # the range must cover the codomain

m = 10
print(is_surjective({k: k % m for k in range(100)}, range(m)))         # True: every bucket used
print(is_surjective({k: (2 * k) % m for k in range(100)}, range(m)))   # False: odd buckets unused

Key takeaways

• Surjective means every element of the codomain is hit: ∀b ∃a f(a) = b.
• Prove it by solving f(a) = b and checking that a lies in the domain.
• Changing the codomain can make a function onto or stop it from being onto.
• For finite sets, a surjection A → B requires |A| ≥ |B|.

Practice

1. (Beginner) Is f: ℤ → ℤ, f(n) = 3n onto? Is g: ℝ → ℝ, g(x) = 3x onto?
2. (Intermediate) Prove that f: ℤ × ℤ → ℤ, f(m, n) = 2m + 3n is onto. Hint: first write 1 as 2m + 3n.
3. (Interview) A hash table uses h(k) = (a · k) mod m for integer keys. For which multipliers a does the map k ↦ (a · k) mod m on {0, …, m − 1} reach every bucket? Hint: the answer depends on gcd(a, m). Try m = 10 with a = 3 and with a = 4 (Chapter 4).

Bijective Functions

Why. A bijection pairs the elements of two sets perfectly, with nothing left over on either side. Bijections let you rename things without losing information, encode and decode losslessly, and count one set by counting another. They are also the basis for comparing the sizes of infinite sets (2.3).

What. f: A → B is bijective (a one-to-one correspondence) if it is both injective and surjective. Equivalently, every b ∈ B has exactly one preimage. For finite sets, a bijection exists exactly when |A| = |B|. A bijection from a set to itself is called a permutation.

Injective?	Surjective?	Name	Example on finite sets
No	No	(neither)	{1,2,3} → {a,b,c} with 1,2 ↦ a, 3 ↦ b
Yes	No	Injection only	{1,2} → {a,b,c} with 1 ↦ a, 2 ↦ b
No	Yes	Surjection only	{1,2,3} → {a,b} with 1,2 ↦ a, 3 ↦ b
Yes	Yes	Bijection	{1,2,3} → {a,b,c} with 1 ↦ a, 2 ↦ b, 3 ↦ c

Counting by bijection. To count a set, find a bijection to a set that is easier to count. Subsets of an n-element set correspond one-to-one with n-bit strings (2.1), so there are 2ⁿ of them.

Example: zig-zag encoding. The function z: ℤ → ℕ defined by

z(n) = 2n          if n ≥ 0
z(n) = −2n − 1     if n < 0

   n :  0  −1   1  −2   2  −3   3  …
 z(n):  0   1   2   3   4   5   6  …

is a bijection. Non-negative integers go to the even naturals and negative integers go to the odd naturals. Protocol Buffers uses exactly this encoding so that small negative numbers get short variable-length encodings. It also shows that ℤ and ℕ have the same cardinality (2.3).

def zigzag_encode(n: int) -> int:
    return 2 * n if n >= 0 else -2 * n - 1       # 0, -1, 1, -2, 2 -> 0, 1, 2, 3, 4

def zigzag_decode(m: int) -> int:
    return m // 2 if m % 2 == 0 else -(m + 1) // 2

# Injective and surjective on a test range: every code 0 … 999 is used exactly once
codes = [zigzag_encode(n) for n in range(-500, 500)]
assert sorted(codes) == list(range(1000))
# Decoding undoes encoding: the inverse function (next topic)
assert all(zigzag_decode(zigzag_encode(n)) == n for n in range(-10**4, 10**4))

Key takeaways

• A bijection is a function that is both injective and surjective. Each output has exactly one preimage.
• Finite sets have a bijection between them exactly when they have the same size.
• To count a set, find a bijection to a set you can already count.
• Lossless encodings such as zig-zag, Base64, and permutations of an array are bijections.

Practice

1. (Beginner) Which of these are bijections ℝ → ℝ? 2x − 5, x², x³, eˣ.
2. (Intermediate) Define φ: P({1, …, n}) → {0, 1}ⁿ by sending a subset S to the bit string with 1 in position i exactly when i ∈ S. Prove that φ is a bijection.
3. (Interview) Fisher–Yates shuffles an array of length n by choosing, for i from n − 1 down to 1, a random index j ∈ {0, …, i} and swapping. Why does it produce every permutation with equal probability? Hint: count the possible sequences of choices and show that the map from choice sequences to permutations is a bijection.

Inverse Functions

Why. Decoding, decrypting, undoing an edit, and converting back to the original units are all inverse operations. Knowing exactly when an inverse exists tells you when an operation can be undone without ambiguity.

What. If f: A → B is a bijection, its inverse f⁻¹: B → A sends each b to its unique preimage:

f⁻¹(b) = a   if and only if   f(a) = b

f⁻¹(f(a)) = a  for all a ∈ A        f(f⁻¹(b)) = b  for all b ∈ B

Reverse every arrow and see what goes wrong when f is not a bijection:

  f not injective                       f not surjective
  1 ───┐                                1 ──────► a
  2 ───┴──► a                                     b
                                       reversed: b has no arrow back,
  reversed: a would go to both 1        so f⁻¹(b) is undefined
  and 2, so f⁻¹(a) is not well-defined

So a function has an inverse function if and only if it is a bijection.

Notation warning. f⁻¹(T) applied to a set means the preimage, which exists for every function. f⁻¹(b) as a function exists only for bijections. Neither is 1/f(x).

How: computing an inverse. Write y = f(x) and solve for x.

Example. f: ℝ − {3} → ℝ − {2}, f(x) = (2x + 1)/(x − 3).

y(x − 3) = 2x + 1
yx − 3y  = 2x + 1
x(y − 2) = 3y + 1
x        = (3y + 1)/(y − 2)          so  f⁻¹(y) = (3y + 1)/(y − 2),  defined for y ≠ 2

The excluded value y = 2 is exactly the value the original function never reaches, which is why the codomain was chosen as ℝ − {2}.

One-sided inverses. An injective function has a left inverse g with g(f(a)) = a: it can be decoded, though some codes are unused. A surjective function has a right inverse h with f(h(b)) = b: you can always pick some preimage. Only a bijection has a two-sided inverse.

def invert(f: dict, codomain) -> dict:
    """Inverse of a finite function, or an explanation of why there is none."""
    inv = {}
    for a, b in f.items():
        if b in inv:
            raise ValueError(f"not injective: {inv[b]!r} and {a!r} both map to {b!r}")
        inv[b] = a
    missing = set(codomain) - set(inv)
    if missing:
        raise ValueError(f"not surjective: no preimage for {sorted(missing)}")
    return inv

# Caesar cipher: a bijection on the 26 letters, inverted by shifting back
letters = "abcdefghijklmnopqrstuvwxyz"
encrypt = {c: letters[(i + 3) % 26] for i, c in enumerate(letters)}
decrypt = invert(encrypt, letters)
secret = "".join(encrypt[c] for c in "hello")
print(secret, "".join(decrypt[c] for c in secret))   # khoor hello

Key takeaways

• A function has an inverse if and only if it is a bijection.
• f⁻¹ ∘ f is the identity on A, and f ∘ f⁻¹ is the identity on B.
• Compute an inverse by solving y = f(x) for x, keeping track of excluded values.
• The preimage f⁻¹(T) of a set always exists. The inverse function does not.

Practice

1. (Beginner) Find the inverse of f: ℝ → ℝ, f(x) = 5x − 2, and verify both f⁻¹(f(x)) = x and f(f⁻¹(y)) = y.
2. (Intermediate) f(x) = x² has no inverse as a map ℝ → ℝ. Restrict its domain and codomain so that it becomes a bijection, and give the inverse. Is there more than one way to do this?
3. (Interview) Password hashes are stored instead of passwords. Explain why a hash from all strings to 256-bit digests cannot have an inverse function, and why "no inverse exists" is not the same as "it is hard to find some preimage". Hint: compare the sizes of the domain and codomain, then think about right inverses.

Function Composition

Why. Programs are built by chaining steps: parse, validate, transform, serialize. Composition is the mathematical form of this chaining, and its laws explain which refactorings are safe.

What. For f: A → B and g: B → C, the composition g ∘ f: A → C is

(g ∘ f)(x) = g(f(x))

Read g ∘ f as "g after f": f is applied first even though it is written second. The composition is defined only when the outputs of f are valid inputs for g.

          f             g
   A ─────────► B ─────────► C
   │                         ▲
   └──────── g ∘ f ──────────┘

Property	Statement
Associative	h ∘ (g ∘ f) = (h ∘ g) ∘ f, so parentheses can be dropped
Not commutative	Usually g ∘ f ≠ f ∘ g
Identity	f ∘ id_A = f = id_B ∘ f, where id_A(x) = x
Inverses	f⁻¹ ∘ f = id_A and f ∘ f⁻¹ = id_B
Inverse of a composition	(g ∘ f)⁻¹ = f⁻¹ ∘ g⁻¹ (to undo "socks, then shoes", remove shoes first)

Example. f(x) = x + 1 and g(x) = 2x on ℝ. Then (g ∘ f)(x) = 2(x + 1) = 2x + 2, but (f ∘ g)(x) = 2x + 1.

Preserved properties. If f and g are both injective, so is g ∘ f. The same holds for surjective and bijective.

Proof (injective). Suppose g(f(a₁)) = g(f(a₂)). Since g is injective, f(a₁) = f(a₂). Since f is injective, a₁ = a₂. ∎

The partial converses are also useful: if g ∘ f is injective then f is injective, and if g ∘ f is surjective then g is surjective.

from functools import reduce

def compose(*fs):
    """compose(h, g, f)(x) == h(g(f(x))): applied right to left, like h ∘ g ∘ f."""
    return reduce(lambda g, f: lambda x: g(f(x)), fs, lambda x: x)   # start from the identity

f = lambda x: x + 1
g = lambda x: 2 * x
print(compose(g, f)(5), compose(f, g)(5))      # 12 11   g∘f ≠ f∘g

# A text-normalization pipeline: strip, then lowercase, then collapse internal spaces
normalize = compose(" ".join, str.split, str.lower, str.strip)
print(normalize("   Hello    WORLD  "))        # hello world

Key takeaways

• (g ∘ f)(x) = g(f(x)). The right-hand function is applied first.
• Composition is associative but not commutative.
• Composing injections, surjections, or bijections gives a function of the same kind.
• The inverse of a composition reverses the order: (g ∘ f)⁻¹ = f⁻¹ ∘ g⁻¹.

Practice

1. (Beginner) Let f(x) = x² and g(x) = x − 3 on ℝ. Compute (f ∘ g)(x), (g ∘ f)(x), and (f ∘ g)(5).
2. (Intermediate) Prove that if g ∘ f is surjective, then g is surjective. Give an example where g ∘ f is surjective but f is not.
3. (Interview) A web framework wraps a handler as app = logging(auth(cache(handler))). Which middleware sees the incoming request first, and which sees the outgoing response first? Why does associativity let you build the stack one layer at a time? Hint: each middleware is a function from handlers to handlers. Trace a request in and its response back out.

Floor and Ceiling Functions

Why. Discrete quantities often come from continuous formulas: the number of pages needed for n items, the middle index of an array, the number of bits in a number, the level of a node in a heap. Floor and ceiling turn real values into integers in a controlled way.

What.

• Floor ⌊x⌋: the greatest integer less than or equal to x (round down, toward −∞).
• Ceiling ⌈x⌉: the least integer greater than or equal to x (round up, toward +∞).

Both are functions ℝ → ℤ. They are surjective but not injective.

x	⌊x⌋	⌈x⌉	Truncation (round toward 0)
3.7	3	4	3
−3.7	−4	−3	−3
5	5	5	5
−0.5	−1	0	0

    ⌊−1.5⌋      ⌈−1.5⌉                   ⌊1.5⌋       ⌈1.5⌉
       │           │                       │           │
   ────●─────○─────●───────────●───────────●─────○─────●─────►
      −2   −1.5   −1           0           1    1.5    2

Properties (x real, n integer):

Property	Statement
Characterization	⌊x⌋ = n iff n ≤ x < n + 1, and ⌈x⌉ = n iff n − 1 < x ≤ n
Sandwich	x − 1 < ⌊x⌋ ≤ x ≤ ⌈x⌉ < x + 1
Negation	⌊−x⌋ = −⌈x⌉ and ⌈−x⌉ = −⌊x⌋
Integer shift	⌊x + n⌋ = ⌊x⌋ + n and ⌈x + n⌉ = ⌈x⌉ + n
Gap	⌈x⌉ − ⌊x⌋ is 0 if x is an integer and 1 otherwise
Ceiling by floor	⌈a/b⌉ = ⌊(a + b − 1)/b⌋ for integers a and b > 0
Not additive	⌊x + y⌋ can differ from ⌊x⌋ + ⌊y⌋ (try x = y = 0.5)

Common uses.

Quantity	Formula
Pages for n items, k per page	⌈n/k⌉
Middle index of lo … hi	⌊(lo + hi)/2⌋
Bits to write n ≥ 1 in binary	⌊log₂ n⌋ + 1
Parent of node i in a 0-indexed binary heap	⌊(i − 1)/2⌋

In code, watch the rounding direction. Python's // is floor division, while C, Java, and JavaScript's integer division and Python's int() truncate toward zero. The two agree for non-negative operands and differ for negative ones. Floating-point ceilings also lose precision for large integers, so use integer arithmetic.

import math

print(7 // 2, -7 // 2)                  # 3 -4     floor division
print(int(-3.5), math.floor(-3.5))      # -3 -4    truncation is not floor for negatives
print(-7 % 2)                           # 1        Python's % matches floor: a == b*(a//b) + a%b

def ceil_div(a, b):
    """⌈a/b⌉ for integers with b > 0, using only exact integer arithmetic."""
    return -(-a // b)                   # ⌈x⌉ = −⌊−x⌋

print(ceil_div(101, 20))                # 6 pages for 101 items at 20 per page

n = 10**17 + 1
print(math.ceil(n / 2))                 # 50000000000000000   wrong: n / 2 was rounded as a float
print(ceil_div(n, 2))                   # 50000000000000001   exact

print((1000).bit_length(), math.floor(math.log2(1000)) + 1)   # 10 10   bits needed for 1000

Key takeaways

• ⌊x⌋ rounds down and ⌈x⌉ rounds up. Both are integers within distance 1 of x.
• ⌊x⌋ = n exactly when n ≤ x < n + 1. Most proofs about floor start from this characterization.
• Integer shifts move through floor and ceiling, but sums of non-integers do not.
• In code, distinguish floor from truncation and avoid floats for exact ceilings of large integers.

Practice

1. (Beginner) Compute ⌊−2.01⌋, ⌈−2.01⌉, ⌊7/3⌋, ⌈7/3⌉, and ⌊log₂ 100⌋.
2. (Intermediate) Prove that ⌊n/2⌋ + ⌈n/2⌉ = n for every integer n. Hint: proof by cases on parity (1.4).
3. (Interview) The Java binary search line int mid = (lo + hi) / 2; contained a bug for years. What is it, and why does lo + (hi - lo) / 2 fix it? Does / in Java compute ⌊ ⌋ when lo + hi is negative? Hint: consider integer overflow, then compare truncation with floor.

<a id="23-cardinality"></a>

2.3 Cardinality

Cardinality is the size of a set. For finite sets it is ordinary counting. For infinite sets, bijections show that there are different sizes of infinity, and this has a direct consequence for computing: some problems cannot be solved by any program.

Finite and Infinite Sets

Why. "How many?" is easy to answer for a finite set: count the elements. For infinite sets, counting never ends, so we need a definition of "same size" that does not rely on finishing a count.

What. Matching elements is more basic than counting. Two piles of coins have the same size if you can pair them off one-to-one, even if you cannot count. This leads to the following definitions:

• |A| = |B| (same cardinality) if there is a bijection A → B.
• |A| ≤ |B| if there is an injection A → B.
• A is finite with |A| = n if there is a bijection {1, …, n} → A (and |∅| = 0). Otherwise A is infinite.

Infinite sets behave differently. In a finite set, a proper subset is always strictly smaller. An infinite set can have the same cardinality as a proper subset of itself. The map n ↦ 2n is a bijection from ℕ to the even naturals, so there are "as many" even numbers as natural numbers. Some definitions of "infinite" (Dedekind's) are based on exactly this property.

Analogy: Hilbert's hotel. A hotel has rooms 0, 1, 2, … and every room is occupied. A new guest arrives. Move the guest in room n to room n + 1. Everyone still has a room and room 0 is free. A full infinite hotel can still take another guest, which is impossible for a full finite hotel.

Property	Finite sets	Infinite sets
Proper subset can have the same size	Never	Always possible
Injection A → A is automatically surjective	Yes	No (n ↦ n + 1 on ℕ misses 0)
Adding one element changes the size	Yes	Not necessarily (|ℕ| = |ℕ ∪ {−1}|)
Size is a natural number	Yes	No, it is a cardinal such as ℵ₀

Familiar finite rules still hold for finite sets: |A × B| = |A| · |B|, |P(A)| = 2^|A|, and |A ∪ B| ≤ |A| + |B|. Every subset of a finite set is finite.

from itertools import count, islice

# ℕ is in bijection with its proper subset of even numbers
evens = (2 * n for n in count())
print(list(islice(evens, 6)))                 # [0, 2, 4, 6, 8, 10]

# Hilbert's hotel: n ↦ n + 1 is injective on ℕ but never produces 0
shift = lambda n: n + 1
print(0 in {shift(n) for n in range(1000)})   # False: room 0 is now free

# Finite case: an injection from a finite set to itself is automatically onto
n = 10
f = {x: (3 * x + 1) % n for x in range(n)}
print(len(set(f.values())) == n)              # True: injective, and therefore surjective

Key takeaways

• Two sets have the same cardinality when a bijection exists between them. This works for infinite sets too.
• |A| ≤ |B| means there is an injection from A to B.
• An infinite set can be the same size as a proper subset of itself. A finite set cannot.
• For finite sets, injective, surjective, and bijective coincide for maps from a set to itself.

Practice

1. (Beginner) Give an explicit bijection showing |ℕ| = |{n ∈ ℕ | n ≥ 5}|.
2. (Intermediate) Prove that if A is finite and f: A → A is injective, then f is surjective. Hint: compare |f(A)| with |A|.
3. (Interview) Hilbert's hotel is full. Infinitely many buses arrive, and each bus carries infinitely many passengers, numbered 0, 1, 2, …. Assign every current guest and every passenger a room so that no room is shared. Hint: send current guests to rooms 2ⁿ and passenger j of bus i to 3^(i+1) · 5^j. Why can no two people collide?

Countable Sets

Why. A set is countable if its elements can be listed one after another so that each element appears at some finite position. This is exactly the kind of set a program can enumerate given unlimited time, which makes countability the right notion of size for computing.

What. A set is countable if it is finite or has a bijection with ℕ. In the second case it is countably infinite, with cardinality ℵ₀ ("aleph-null"). The following conditions are equivalent for a non-empty set A:

• A is countable.
• There is an injection A → ℕ.
• There is a surjection ℕ → A, that is, a list a₀, a₁, a₂, … in which every element appears (repeats allowed).

Examples.

Set	Listing that reaches every element
ℤ	0, −1, 1, −2, 2, … (the zig-zag bijection from 2.2)
ℕ × ℕ	Walk the diagonals x + y = 0, 1, 2, …
ℚ	Each rational is p/q with (p, q) ∈ ℤ × ℤ⁺, a countable set. List those pairs and skip duplicates
Σ*, all finite strings over a finite alphabet	Shortlex: by length, then alphabetically within each length
All programs in any language	A program is a finite string, so this is a subset of Σ*
Countable union of countable sets	Interleave the lists (diagonally)

The diagonal walk. Listing ℕ × ℕ row by row, (0,0), (0,1), (0,2), …, never reaches (1, 0), because the first row is infinite. Walking the diagonals reaches every pair after finitely many steps:

          y=0      y=1      y=2      y=3
  x=0   (0,0)₀   (0,1)₂   (0,2)₅   (0,3)₉   …
  x=1   (1,0)₁   (1,1)₄   (1,2)₈     …
  x=2   (2,0)₃   (2,1)₇     …
  x=3   (3,0)₆     …
         subscript = position in the list

The position of (x, y) is given by the Cantor pairing function π(x, y) = (x + y)(x + y + 1)/2 + y, which is a bijection ℕ × ℕ → ℕ.

Pitfall. A listing must reach every element after finitely many steps. "First all the positive numbers, then the negative ones" is not a valid listing of ℤ, because the negative numbers never get a position.

from itertools import count, islice, product
from math import isqrt

def pairs():
    """Enumerate ℕ × ℕ diagonal by diagonal."""
    for d in count():                       # d = x + y, the index of the diagonal
        for y in range(d + 1):
            yield (d - y, y)

def cantor_pair(x, y):
    return (x + y) * (x + y + 1) // 2 + y

def cantor_unpair(z):
    w = (isqrt(8 * z + 1) - 1) // 2         # the diagonal: largest w with w(w+1)/2 <= z
    y = z - w * (w + 1) // 2
    return (w - y, y)

print(list(islice(pairs(), 6)))             # [(0, 0), (1, 0), (0, 1), (2, 0), (1, 1), (0, 2)]
assert all(cantor_unpair(cantor_pair(x, y)) == (x, y) for x in range(200) for y in range(200))

def all_strings(alphabet):
    """Shortlex enumeration of Σ*: every finite string appears at a finite position."""
    for length in count():
        for chars in product(alphabet, repeat=length):
            yield "".join(chars)

print(list(islice(all_strings("ab"), 7)))   # ['', 'a', 'b', 'aa', 'ab', 'ba', 'bb']

Key takeaways

• Countable means finite or listable as a₀, a₁, a₂, … with every element at a finite position.
• ℕ, ℤ, ℚ, ℕ × ℕ, and the set of finite strings all have cardinality ℵ₀.
• The listing order matters. Diagonal walks and shortlex order reach every element, while row-by-row walks may not.
• The set of all programs is countable because every program is a finite string.

Practice

1. (Beginner) Give an explicit listing of all odd integers, positive and negative, showing that the set is countable.
2. (Intermediate) Prove that the union of two countably infinite sets A and B is countable. Be careful if A and B overlap.
3. (Interview) Prove that the set of all valid Python programs is countable, without reference to how Python works beyond "a program is a text file". Hint: use the shortlex enumeration above and filter out the strings that are not valid programs. What does filtering do to countability?

Uncountable Sets

Why. Not every infinite set can be listed. Some are strictly larger than ℕ. Because programs are countable, this means there are more problems than programs, so some problems have no algorithm at all.

What. A set is uncountable if it is not countable. Standard examples:

• the real numbers ℝ, and any interval such as (0, 1)
• the power set P(ℕ)
• the set {0, 1}^ℕ of infinite bit sequences, equivalently the set of functions ℕ → {0, 1}

These all have the same cardinality, called the continuum 𝔠 = 2^ℵ₀.

Cantor's theorem. For every set A, |A| < |P(A)|. No function f: A → P(A) is surjective.

Proof. Let f: A → P(A) be any function and define

D = { a ∈ A | a ∉ f(a) }

Suppose D = f(d) for some d ∈ A. Then d ∈ D if and only if d ∉ f(d) = D, which is a contradiction. So D is not in the range of f, and f is not onto. ∎

Applied repeatedly, the theorem gives an endless hierarchy |ℕ| < |P(ℕ)| < |P(P(ℕ))| < …. There is no largest infinity.

Set	Countable?	Reason
ℕ, ℤ, ℚ, ℕ × ℕ	Yes	Explicit listings (previous topic)
Finite strings, programs	Yes	Shortlex enumeration
Finite subsets of ℕ	Yes	Each one is a finite bit string
Algebraic numbers	Yes	Each is a root of an integer polynomial, and those are finite lists of integers
P(ℕ), infinite bit sequences	No	Cantor's theorem / diagonal argument
ℝ, (0, 1)	No	Diagonal argument (next topic)
Irrational numbers	No	Otherwise ℝ = ℚ ∪ irrationals would be a union of two countable sets
Functions ℕ → ℕ	No	Contains a copy of the functions ℕ → {0, 1}

Consequence for computing. A decision problem can be viewed as a function Σ* → {0, 1} that answers yes or no for every input string. There are uncountably many such functions but only countably many programs, so most decision problems cannot be solved by any program. The halting problem (1.4, Chapter 13) is one explicit example.

from itertools import product

# Cantor's theorem, verified exhaustively for a 3-element set:
# for every f: A -> P(A), the diagonal set D is missed.
A = [0, 1, 2]
subsets = [frozenset(a for i, a in enumerate(A) if mask >> i & 1) for mask in range(2 ** len(A))]

checked = 0
for images in product(subsets, repeat=len(A)):     # all 8³ = 512 functions A -> P(A)
    f = dict(zip(A, images))
    D = frozenset(a for a in A if a not in f[a])   # the diagonal set
    assert D not in f.values()                     # D is never in the range
    checked += 1
print(f"No surjection among {checked} functions")  # No surjection among 512 functions

Key takeaways

• Uncountable sets cannot be listed. ℝ, P(ℕ), and infinite bit sequences are uncountable.
• Cantor's theorem: |A| < |P(A)| for every set, so there are infinitely many sizes of infinity.
• The proof builds the "diagonal" set D = {a | a ∉ f(a)}, which differs from every f(a).
• Countably many programs but uncountably many problems means most problems are unsolvable.

Practice

1. (Beginner) Classify as countable or uncountable: the set of finite subsets of ℕ, the set of all subsets of ℕ, the interval [0, 0.001], the set of real roots of polynomials with integer coefficients.
2. (Intermediate) Prove that the set of irrational numbers is uncountable, using the facts that ℝ is uncountable and ℚ is countable.
3. (Interview) A colleague claims: "For every function ℕ → {0, 1}, someone could in principle write a program that computes it." Refute this using only cardinality, without the halting problem. Hint: how many programs are there, and how many functions ℕ → {0, 1}?

Cantor's Diagonal Argument

Why. The diagonal argument is one of the most reused ideas in mathematics and computer science. It proves that ℝ is uncountable, and the same pattern of self-reference proves the undecidability of the halting problem and Gödel's incompleteness theorem. Learning the pattern once lets you recognize it in all of these.

What. Theorem. The interval (0, 1) is uncountable.

Proof. Suppose, for contradiction, that s₀, s₁, s₂, … is a list of every real number in (0, 1), each written as an infinite decimal. Build a new number d digit by digit: the n-th digit of d is chosen to differ from the n-th digit of sₙ. A safe rule is "use 5, unless that digit is 5, then use 4". Using only 4s and 5s avoids the double representation 0.4999… = 0.5000….

  s₀ = 0 . [5]  1   0   4   1  …
  s₁ = 0 .  4  [1]  4   1   5  …
  s₂ = 0 .  9   2  [6]  5   3  …
  s₃ = 0 .  0   0   0  [0]  0  …
   ⋮                         ⋱
  d  = 0 .  4   5   5   5   …      digit n of d ≠ digit n of sₙ

For every n, d differs from sₙ in the n-th digit, so d ≠ sₙ. But d ∈ (0, 1), so it should appear in the list. Contradiction. ∎

The general pattern. Arrange the objects in a table where row i describes the i-th object on input j. Then build a new object by flipping the diagonal. The new object disagrees with row i at position i, so it is not any row.

Result	Rows	Columns	Diagonal object
(0, 1) is uncountable	Listed reals sᵢ	Digit positions	d with digit n ≠ digit n of sₙ
Cantor's theorem	Subsets f(a)	Elements a	D = {a | a ∉ f(a)}
Russell's paradox	Sets x	Sets x	{x | x ∉ x}
Halting problem	Programs Pᵢ	Inputs j	A program that does the opposite of Pᵢ on input i

Common mistakes.

• "Just add d to the list." The argument applies to every list, including the new one. It shows that no list can be complete, not that one particular list is incomplete.
• "Apply it to ℚ." The constructed d need not be rational, so it does not have to be in the list of rationals and there is no contradiction.
• "Apply it to finite strings." The diagonal object is infinite, so it is not a finite string.

def diagonal(enumeration):
    """Given enumeration(n) = the n-th infinite bit sequence (a function k -> bit),
    return a sequence that differs from every listed sequence."""
    return lambda k: 1 - enumeration(k)(k)        # flip bit k of sequence k

# One attempted list of all infinite bit sequences: sequence n = binary digits of n, then 0s
def enumeration(n):
    return lambda k: (n >> k) & 1

d = diagonal(enumeration)
assert all(d(n) != enumeration(n)(n) for n in range(10_000))   # differs from each sequence
print([d(k) for k in range(10)])   # [1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
# The all-ones sequence is missing: every listed sequence eventually becomes all 0s.

Key takeaways

• Assume a complete list, build an object that differs from the n-th entry at position n, and conclude the list was incomplete.
• Choose replacement digits that avoid representation issues (such as trailing 9s).
• The same pattern proves Cantor's theorem, Russell's paradox, and the undecidability of the halting problem.
• The argument fails when the constructed object might lie outside the set, as with ℚ or finite strings.

Practice

1. (Beginner) A list begins s₀ = 0.1111…, s₁ = 0.2525…, s₂ = 0.5000…, s₃ = 0.3141…. Using the rule "5 unless the digit is 5, then 4", write the first four digits of the diagonal number d.
2. (Intermediate) Use a diagonal argument to prove that the set of all functions ℕ → ℕ is uncountable. Hint: given a list f₀, f₁, …, define g(n) = fₙ(n) + 1.
3. (Interview) Why does the diagonal argument fail to show that the rationals in (0, 1) are uncountable? Point to the exact step that breaks. Hint: is the constructed d guaranteed to be in the set being listed?

Schröder–Bernstein Theorem

Why. Proving |A| = |B| requires a bijection, and explicit bijections can be awkward to build, for example between (0, 1) and [0, 1]. Injections in each direction are usually easy. The Schröder–Bernstein theorem says that is enough.

What. Theorem (Schröder–Bernstein). If there are injections f: A → B and g: B → A, then there is a bijection A → B. In cardinality notation: |A| ≤ |B| and |B| ≤ |A| imply |A| = |B|. This makes ≤ on cardinalities antisymmetric, one of the properties of a partial order (2.5).

How. Find an injection each way. They do not need to be related or surjective.

Example 1. |(0, 1)| = |[0, 1]|.

• (0, 1) → [0, 1]: the inclusion x ↦ x.
• [0, 1] → (0, 1): x ↦ (x + 1)/3, whose values lie in [1/3, 2/3] ⊂ (0, 1). Both are injective, so the sets have the same cardinality. ∎

Example 2. |ℕ × ℕ| = |ℕ|.

• ℕ → ℕ × ℕ: n ↦ (n, 0).
• ℕ × ℕ → ℕ: (a, b) ↦ 2ᵃ · 3ᵇ, which is injective by unique prime factorization (Chapter 4). ∎

Example 3. |ℝ| = |P(ℕ)|.

• P(ℕ) → ℝ: send S to the decimal 0.d₀d₁d₂… with dₙ = 1 if n ∈ S and 0 otherwise. Decimals using only the digits 0 and 1 have unique representations, so this is injective.
• ℝ → P(ℚ): send x to {q ∈ ℚ | q < x}. Between two different reals there is a rational, so different reals give different sets. Since ℚ is countable, P(ℚ) has the same cardinality as P(ℕ). ∎

Proof idea. Start at any element and alternately apply f and g forward, and their inverses backward as far as possible. Each element lies on exactly one chain:

  … ──► a₀ ──f──► b₀ ──g──► a₁ ──f──► b₁ ──g──► a₂ ──► …

Going backward, a chain either stops at an element of A that is not in the range of g, stops at an element of B that is not in the range of f, or never stops. Define h: A → B by h(a) = f(a) on chains that stop in A or never stop, and h(a) = g⁻¹(a) on chains that stop in B. On every chain, h matches the A-elements with the B-elements one-to-one, so h is a bijection.

def schroder_bernstein(a):
    """Bijection h: ℤ⁺ → ℤ⁺ built from the injections f(n) = 2n (A → B) and g(n) = 3n (B → A)."""
    x, side = a, "A"
    while True:                              # trace a's chain backward
        if side == "A":
            if x % 3 != 0:                   # x has no g-preimage: chain stops in A
                return 2 * a                 # use f
            x, side = x // 3, "B"
        else:
            if x % 2 != 0:                   # x has no f-preimage: chain stops in B
                return a // 3                # use g⁻¹
            x, side = x // 2, "A"

h = {a: schroder_bernstein(a) for a in range(1, 30_001)}
print([h[a] for a in range(1, 10)])                       # [2, 4, 1, 8, 10, 12, 14, 16, 3]
assert len(set(h.values())) == len(h)                     # injective on the tested range
assert set(range(1, 10_001)) <= set(h.values())           # every small value is reached

Key takeaways

• Injections A → B and B → A together guarantee a bijection.
• It is usually far easier to find two injections than one explicit bijection.
• The proof splits both sets into chains and chooses f or g⁻¹ on each chain.
• The theorem makes ≤ on cardinalities antisymmetric.

Practice

1. (Beginner) Use Schröder–Bernstein to show |[0, 1]| = |[0, 2)|. Give both injections explicitly.
2. (Intermediate) Show |ℤ × ℤ| = |ℕ| by giving explicit injections in both directions and proving each is injective.
3. (Interview) A teammate claims the set of all JSON documents is "bigger" than ℕ because documents can nest without limit. Settle the question with Schröder–Bernstein. Hint: map n to the JSON number literal n. For the other direction, serialize the document to bytes and read the bytes as a number, adding a leading 1 byte so that leading zeros are not lost.

<a id="24-relations"></a>

2.4 Relations

A relation generalizes a function. It is any set of pairs, so an element may be related to none, one, or many others. Relations model "follows", "depends on", "is less than", "is in the same team as", and, in their n-ary form, every table in a relational database.

Binary Relations

Why. Many connections are not functions. A student takes several courses, a user follows many accounts, and a number is less than infinitely many others. These connections still need a precise mathematical form.

What. A binary relation R from A to B is any subset R ⊆ A × B. We write a R b when (a, b) ∈ R. A relation on A is a relation from A to A, that is, a subset of A × A.

	Function f: A → B	Relation R ⊆ A × B
Outputs per input	Exactly one	Any number, including zero
Formal object	Special subset of A × B	Any subset of A × B
Inverse	Exists only for bijections	R⁻¹ = {(b, a) | (a, b) ∈ R} always exists
Examples	x ↦ x², user_id ↦ email	<, "divides", "follows", "enrolled in"

Every function is a relation, but most relations are not functions. Since a relation on an n-element set is any subset of the n² pairs in A × A, there are 2^(n²) relations on it.

Examples.

• < on ℤ: {(a, b) | a < b}.
• Divisibility on ℤ⁺: a ∣ b iff b = ak for some integer k.
• Enrollment: E ⊆ Students × Courses, with (s, c) ∈ E when student s takes course c.
• Its inverse E⁻¹ ⊆ Courses × Students answers "who takes this course?".

A = range(1, 7)
divides = {(a, b) for a in A for b in A if b % a == 0}    # a R b  iff  a | b
print((2, 6) in divides, (6, 2) in divides)               # True False
print(len(divides))                                       # 14 of the 36 possible pairs

multiple_of = {(b, a) for (a, b) in divides}              # R⁻¹: "b is a multiple of a"
print((6, 2) in multiple_of)                              # True

def related_to(R, a):
    """All b with a R b. For a function this would always be exactly one element."""
    return {b for (x, b) in R if x == a}

print(sorted(related_to(divides, 2)))                     # [2, 4, 6]

Key takeaways

• A binary relation from A to B is any subset of A × B. Write a R b for (a, b) ∈ R.
• Functions are exactly the relations in which every input has exactly one partner.
• The inverse relation R⁻¹ swaps every pair and always exists.
• An n-element set has 2^(n²) relations on it.

Practice

1. (Beginner) List the pairs of R = {(a, b) ∈ {1, 2, 3, 4}² | a < b}. How many are there? Describe R⁻¹ in words.
2. (Intermediate) How many relations are there on a 3-element set A? How many of them are functions A → A?
3. (Interview) In a social network, "user a follows user b" is a relation F. Why is it not a function? Which product feature corresponds to F⁻¹? How would you store F so that both "whom does a follow?" and "who follows b?" are fast? Hint: one index per direction, at the cost of double writes.

Relation Representations (Matrices and Digraphs)

Why. The same relation can be stored and drawn in several ways, and each makes different questions easy. A matrix allows algebra and constant-time lookup, a directed graph shows structure at a glance, and an adjacency list is compact for sparse data. Directed graphs are also the link to graph theory (Chapter 8).

What. Let R be divisibility on A = {1, 2, 3, 4}:

R = {(1,1), (1,2), (1,3), (1,4), (2,2), (2,4), (3,3), (4,4)}

Zero-one matrix. Number the elements a₁, …, aₙ. The matrix M_R has mᵢⱼ = 1 if aᵢ R aⱼ and 0 otherwise. The row is the first component and the column is the second.

          1  2  3  4
     1 [  1  1  1  1 ]
M_R= 2 [  0  1  0  1 ]
     3 [  0  0  1  0 ]
     4 [  0  0  0  1 ]

Directed graph (digraph). Draw one vertex per element and an arrow a → b for each pair (a, b) ∈ R. A pair (a, a) is a loop, drawn here as ↺.

      ↺                ↺
      1 ─────────────► 2
      │ ╲              │
      │   ╲            │
      ▼     ╲          ▼
      3       ╲──────► 4
      ↺                ↺

Adjacency list. For each element, list the elements it is related to: 1: [1, 2, 3, 4], 2: [2, 4], 3: [3], 4: [4].

Representation	Space	Test a R b	List all b with a R b	Best for
Set of pairs (hash set)	O(|R|)	O(1) average	O(|R|)	Simple code, membership tests
Zero-one matrix	O(n²)	O(1)	O(n)	Dense relations, algebraic operations
Adjacency list	O(n + |R|)	O(deg a)	O(deg a)	Sparse relations, graph traversal

Operations as matrix algebra. For relations on the same set:

Relation operation	Matrix operation
R ∪ S	Element-wise OR
R ∩ S	Element-wise AND
R⁻¹	Transpose
Composition S ∘ R	Boolean matrix product M_R ⊙ M_S (next topics)

A = [1, 2, 3, 4]
R = {(a, b) for a in A for b in A if b % a == 0}

idx = {a: i for i, a in enumerate(A)}
M = [[0] * len(A) for _ in A]
for a, b in R:
    M[idx[a]][idx[b]] = 1                  # row = first component, column = second

for row in M:
    print(row)
# [1, 1, 1, 1]
# [0, 1, 0, 1]
# [0, 0, 1, 0]
# [0, 0, 0, 1]

adj = {a: sorted(b for (x, b) in R if x == a) for a in A}
print(adj)                                  # {1: [1, 2, 3, 4], 2: [2, 4], 3: [3], 4: [4]}

transpose = [list(col) for col in zip(*M)]  # matrix of R⁻¹

Key takeaways

• A relation can be stored as a set of pairs, a zero-one matrix, or an adjacency list, and drawn as a digraph.
• In the matrix, mᵢⱼ = 1 means aᵢ R aⱼ. In the digraph, it means an arrow from aᵢ to aⱼ.
• Union, intersection, and inverse correspond to OR, AND, and transpose.
• Matrices suit dense relations. Adjacency lists suit sparse ones.

Practice

1. (Beginner) Write the zero-one matrix and draw the digraph of R = {(a, b) | a + b is even} on {1, 2, 3, 4}.
2. (Intermediate) The matrix below represents a relation on {1, 2, 3}. List its pairs and describe the relation in words. Then give the matrix of its inverse.

   [ 0 1 1 ]
   [ 0 0 1 ]
   [ 0 0 0 ]
   

3. (Interview) A follow graph has 10⁷ users and an average of 200 follows per user. Estimate the memory needed for a bit matrix and for adjacency lists with 4-byte IDs. Which would you choose? Hint: n² bits versus about n + |R| integers.

Reflexive, Symmetric, Antisymmetric, Transitive Properties

Why. A handful of properties classify the most important relations. Equivalence relations and partial orders (2.5) are defined by them, and they decide which reasoning steps are valid. Transitivity, for example, is what lets a sorting algorithm conclude a < c from a < b and b < c without comparing a and c.

What. Let R be a relation on A.

Property	Definition	In the digraph	In the matrix	Example	Non-example
Reflexive	∀a (a R a)	Loop at every vertex	Diagonal all 1	≤, =, ⊆	<
Irreflexive	∀a ¬(a R a)	No loops	Diagonal all 0	<, ≠	≤
Symmetric	∀a ∀b (a R b → b R a)	Every arrow has a reverse arrow	M = Mᵀ	=, "is a sibling of"	≤
Antisymmetric	∀a ∀b (a R b ∧ b R a → a = b)	No two-way arrows between distinct vertices	No mᵢⱼ = mⱼᵢ = 1 with i ≠ j	≤, ⊆, ∣ on ℤ⁺	"is a sibling of"
Transitive	∀a ∀b ∀c (a R b ∧ b R c → a R c)	Every two-step path has a direct shortcut	M ⊙ M ≤ M element-wise	<, ⊆, "is an ancestor of"	"is the parent of"

Easily confused pairs.

• Symmetric and antisymmetric are not opposites. Equality is both. The relation {(1, 2), (2, 1), (1, 3)} is neither.
• Irreflexive is not the same as "not reflexive". {(1, 1)} on {1, 2} is neither reflexive (no (2, 2)) nor irreflexive (has (1, 1)).
• Vacuous truth applies. The empty relation is symmetric, antisymmetric, and transitive, because no pairs exist to break the conditions.

Worked example. Divisibility on ℤ⁺:

• Reflexive: a = a · 1, so a ∣ a.
• Antisymmetric: if b = ak and a = bj with a, b > 0, then a = ajk, so jk = 1 with positive integers, which forces j = k = 1 and a = b.
• Transitive: if b = ak and c = bj, then c = a(kj).
• Not symmetric: 1 ∣ 2 but 2 ∤ 1.

On all of ℤ, divisibility is not antisymmetric, since 2 ∣ −2 and −2 ∣ 2 but 2 ≠ −2. The domain matters.

def is_reflexive(R, A):   return all((a, a) in R for a in A)
def is_irreflexive(R, A): return all((a, a) not in R for a in A)
def is_symmetric(R):      return all((b, a) in R for (a, b) in R)
def is_antisymmetric(R):  return all(a == b or (b, a) not in R for (a, b) in R)

def is_transitive(R):
    succ = {}
    for a, b in R:
        succ.setdefault(a, set()).add(b)
    return all((a, c) in R for (a, b) in R for c in succ.get(b, ()))   # every a→b→c has a→c

A = range(1, 5)
relations = {
    "=":            {(a, b) for a in A for b in A if a == b},
    "<=":           {(a, b) for a in A for b in A if a <= b},
    "<":            {(a, b) for a in A for b in A if a < b},
    "divides":      {(a, b) for a in A for b in A if b % a == 0},
    "same parity":  {(a, b) for a in A for b in A if (a - b) % 2 == 0},
    "differ by 1":  {(a, b) for a in A for b in A if abs(a - b) == 1},
}
print(f"{'':13}" + "".join(f"{h:9}" for h in ["refl", "irrefl", "sym", "antisym", "trans"]).rstrip())
for name, R in relations.items():
    flags = [is_reflexive(R, A), is_irreflexive(R, A), is_symmetric(R),
             is_antisymmetric(R), is_transitive(R)]
    print(f"{name:13}" + "".join(f"{str(x):9}" for x in flags).rstrip())
#              refl     irrefl   sym      antisym  trans
# =            True     False    True     True     True
# <=           True     False    False    True     True
# <            False    True     False    True     True
# divides      True     False    False    True     True
# same parity  True     False    True     False    True
# differ by 1  False    True     True     False    False

Key takeaways

• Reflexive: everything is related to itself. Symmetric: every pair goes both ways. Antisymmetric: no two distinct elements are related both ways. Transitive: chains can be shortened.
• Symmetric and antisymmetric can both hold, or both fail.
• Each property has a simple picture in the digraph and in the matrix.
• Whether a property holds can depend on the underlying set, as with divisibility on ℤ⁺ versus ℤ.

Practice

1. (Beginner) Which of the five properties does R = {(1,1), (2,2), (3,3), (1,2), (2,1)} on {1, 2, 3} have?
2. (Intermediate) On ℤ, define a R b iff ab ≥ 0. Determine which properties hold and give a counterexample for each one that fails.
3. (Interview) A Java comparator (a, b) -> a.score > b.score ? 1 : -1 makes Collections.sort occasionally throw "Comparison method violates its general contract!". Which property of the underlying order is violated? Hint: compute compare(x, x) and compare compare(a, b) with compare(b, a) when two scores are equal.

Composition of Relations

Why. Many useful relations are chains of simpler ones: "grandparent" is "parent of a parent", "friend of a friend" is two friendship steps, and a database join links two tables through a shared column. Composition is the operation that builds these chains.

What. For R ⊆ A × B and S ⊆ B × C, the composition is

S ∘ R = { (a, c) | ∃b ∈ B  (a R b  ∧  b S c) }

R is applied first, matching the convention for functions in 2.2. Some texts write R ; S for the same relation.

      R           S
  a ──────► b ──────► c        (a, c) ∈ S ∘ R  because some middle element b links them

Powers. For a relation on A, define R¹ = R and Rⁿ⁺¹ = Rⁿ ∘ R. Then (a, b) ∈ Rⁿ exactly when there is a path of length n from a to b in the digraph.

Properties.

• Composition is associative: T ∘ (S ∘ R) = (T ∘ S) ∘ R.
• (S ∘ R)⁻¹ = R⁻¹ ∘ S⁻¹.
• R is transitive if and only if R² ⊆ R. Every two-step path must already be a one-step pair.

Example. Let the parent relation be P = {(ana, ben), (ben, cleo), (ben, dev), (cleo, eli)}. Then

P ∘ P = {(ana, cleo), (ana, dev), (ben, eli)}       the grandparent relation

Matrix form. M_{S∘R} = M_R ⊙ M_S, the Boolean product, which is matrix multiplication with AND in place of multiplication and OR in place of addition:

(M_R ⊙ M_S)ᵢⱼ = OR over k of ( (M_R)ᵢₖ AND (M_S)ₖⱼ )

In words, i reaches j if some middle element k is reachable from i by R and reaches j by S.

def compose(S, R):
    """S ∘ R = {(a, c) | ∃b: a R b and b S c}. R is applied first, as with functions."""
    S_from = {}
    for b, c in S:
        S_from.setdefault(b, set()).add(c)            # index S by its first component
    return {(a, c) for (a, b) in R for c in S_from.get(b, ())}

P = {("ana", "ben"), ("ben", "cleo"), ("ben", "dev"), ("cleo", "eli")}
print(sorted(compose(P, P)))     # [('ana', 'cleo'), ('ana', 'dev'), ('ben', 'eli')]

def bool_matmul(X, Y):
    """Boolean matrix product: entry (i, j) is 1 iff some k has X[i][k] = Y[k][j] = 1."""
    return [[int(any(X[i][k] and Y[k][j] for k in range(len(Y)))) for j in range(len(Y[0]))]
            for i in range(len(X))]

M = [[0, 1, 0],                  # R = {(1,2), (2,3)} on {1, 2, 3}
     [0, 0, 1],
     [0, 0, 0]]
print(bool_matmul(M, M))         # [[0, 0, 1], [0, 0, 0], [0, 0, 0]]   R² = {(1,3)}

In SQL, composition is a join on the middle column followed by a projection onto the outer columns:

-- grandparent = parent ∘ parent: join on the shared middle person
SELECT DISTINCT p1.parent AS grandparent, p2.child AS grandchild
FROM parent_of AS p1
JOIN parent_of AS p2 ON p1.child = p2.parent;

Key takeaways

• S ∘ R relates a to c when some middle element b has a R b and b S c.
• Rⁿ describes paths of length exactly n in the digraph.
• R is transitive if and only if R² ⊆ R.
• In matrix form, composition is a Boolean matrix product. In SQL, it is a join followed by a projection.

Practice

1. (Beginner) For R = {(1, 2), (2, 3), (3, 1)} on {1, 2, 3}, compute R² and R³. What is special about R³?
2. (Intermediate) Prove that a relation R is transitive if and only if R² ⊆ R.
3. (Interview) "People you may know" suggests friends of friends who are not already friends and are not the user. Write the suggestion relation using composition, difference, and the identity relation, and estimate the cost per user if the average degree is d. Hint: (F ∘ F) − F − {(a, a) | a ∈ A}. The intermediate result has up to d² pairs per user.

Closures of Relations

Why. A relation often lacks a property we need, and we want to add as few pairs as possible to get it. The most important case is reachability: "does module A depend on module B, directly or indirectly?" is asking whether (A, B) is in the transitive closure of the direct-dependency relation.

What. The closure of R with respect to a property is the smallest relation that contains R and has the property. "Smallest" means that it is contained in every relation that contains R and has the property.

Closure	Formula	Meaning in the digraph
Reflexive	R ∪ Δ, where Δ = {(a, a) | a ∈ A}	Add a loop at every vertex
Symmetric	R ∪ R⁻¹	Add the reverse of every arrow
Transitive	R⁺ = R ∪ R² ∪ R³ ∪ …	Add a → b whenever there is a path from a to b
Reflexive-transitive	R* = R⁺ ∪ Δ	"Reachable in zero or more steps"

On an n-element set, R⁺ = R ∪ R² ∪ … ∪ Rⁿ. A shortest path visits each vertex at most once, so it has at most n edges.

Not every property has a closure. Antisymmetry, for example, can only be gained by removing pairs, so there is no smallest antisymmetric relation containing a relation like {(1, 2), (2, 1)}.

Example. R = {(1, 2), (2, 3), (3, 4)} on {1, 2, 3, 4}.

  R:            1 ──► 2 ──► 3 ──► 4

  R⁺ adds:      (1, 3), (2, 4)              paths of length 2
                (1, 4)                      path of length 3
  R⁺ = {(1,2), (1,3), (1,4), (2,3), (2,4), (3,4)}

Warshall's algorithm computes the transitive closure in O(n³) time. It considers each vertex k in turn as a possible intermediate stop. After step k, W[i][j] = 1 exactly when there is a path from i to j whose intermediate vertices all come from the first k vertices.

W[i][j]  ←  W[i][j]  OR  ( W[i][k]  AND  W[k][j] )

def warshall(M):
    """Transitive closure of the relation with zero-one matrix M."""
    n = len(M)
    W = [row[:] for row in M]                # copy so the input is not modified
    for k in range(n):                       # allow vertex k as an intermediate stop
        for i in range(n):
            if W[i][k]:                      # i reaches k ...
                for j in range(n):
                    if W[k][j]:              # ... and k reaches j,
                        W[i][j] = 1          # so i reaches j
    return W

M = [[0, 1, 0, 0],                           # 1 → 2 → 3 → 4
     [0, 0, 1, 0],
     [0, 0, 0, 1],
     [0, 0, 0, 0]]
for row in warshall(M):
    print(row)
# [0, 1, 1, 1]
# [0, 0, 1, 1]
# [0, 0, 0, 1]
# [0, 0, 0, 0]

Key takeaways

• A closure is the smallest extension of R that has a given property.
• The reflexive closure adds Δ, the symmetric closure adds R⁻¹, and the transitive closure adds all paths.
• The transitive closure answers reachability questions. On n elements, paths of length up to n suffice.
• Warshall's algorithm computes the transitive closure in O(n³). Some properties, such as antisymmetry, have no closure.

Practice

1. (Beginner) For R = {(1, 2), (2, 1), (2, 3)} on {1, 2, 3}, find the reflexive, symmetric, and transitive closures.
2. (Intermediate) Find a relation R such that taking the symmetric closure and then the transitive closure gives a different result from taking the transitive closure and then the symmetric closure.
3. (Interview) A monorepo has 50,000 packages and their direct dependencies. Engineers want to know which packages must be rebuilt when package X changes. Would you precompute the full transitive closure, or answer each query with a graph search? Hint: the closure can contain Θ(n²) pairs, while a breadth-first search on the reversed dependency graph costs O(n + m) per query.

N-ary Relations and Databases

Why. Real records have more than two fields. A student has an ID, a name, and a major. A relational database stores exactly this kind of data, and the relational model introduced by E. F. Codd in 1970 is built directly on n-ary relations.

What. An n-ary relation on sets A₁, …, Aₙ is a subset of A₁ × A₂ × … × Aₙ. Its elements are n-tuples, and n is its degree.

Database term	Mathematical term
Table	n-ary relation
Row	n-tuple
Column	Position in the tuple, with its domain Aᵢ
Primary key	Columns whose values determine the whole tuple

A primary key makes the mapping from key values to rows a function: no two rows share a key. A key made of several columns is a composite key.

Relational algebra. Queries are built from a small set of operations on relations:

Operation	Symbol	Result	SQL
Selection	σ_P(R)	Tuples of R that satisfy P	WHERE
Projection	π_{cols}(R)	Only the listed columns, duplicates removed	SELECT DISTINCT cols
Join	R ⋈ S	Pairs of tuples that agree on the shared attributes, combined	JOIN … ON
Cartesian product	R × S	Every combination of tuples	CROSS JOIN
Union, intersection, difference	∪, ∩, −	Set operations on relations with the same columns	UNION, INTERSECT, EXCEPT
Rename	ρ	Same relation with new names	AS

Sets vs bags. In the mathematical model a relation is a set, so it has no duplicate rows and no order. SQL tables and query results are actually multisets (2.1): SELECT major FROM Students can return 'CS' twice. SELECT DISTINCT and UNION remove duplicates, while UNION ALL keeps them.

Example.

Students                       Enrolled
id | name | major              student_id | course
---+------+------              -----------+---------------
 1 | Ana  | CS                          1 | Discrete Math
 2 | Ben  | Math                        1 | Databases
 3 | Cleo | CS                          3 | Discrete Math

Names of students enrolled in Discrete Math:
π_name( σ_{course = 'Discrete Math'}( Students ⋈_{id = student_id} Enrolled ) )  =  {Ana, Cleo}

students = {            # Students(id, name, major)
    (1, "Ana", "CS"),
    (2, "Ben", "Math"),
    (3, "Cleo", "CS"),
}
enrolled = {            # Enrolled(student_id, course)
    (1, "Discrete Math"),
    (1, "Databases"),
    (3, "Discrete Math"),
}

def select(R, pred):                 # σ: keep tuples that satisfy pred
    return {t for t in R if pred(t)}

def project(R, *cols):               # π: keep chosen positions; the set removes duplicates
    return {tuple(t[i] for i in cols) for t in R}

def join(R, S, i, j):                # R ⋈ S on R[i] = S[j]: concatenate matching tuples
    return {r + s for r in R for s in S if r[i] == s[j]}

joined = join(students, enrolled, 0, 0)      # (id, name, major, student_id, course)
in_dm = select(joined, lambda t: t[4] == "Discrete Math")
print(sorted(project(in_dm, 1)))             # [('Ana',), ('Cleo',)]

print(sorted(project(enrolled, 1)))          # [('Databases',), ('Discrete Math',)]  no duplicates
print(sorted(project(students, 2)))          # [('CS',), ('Math',)]

SELECT DISTINCT s.name
FROM Students AS s
JOIN Enrolled AS e ON e.student_id = s.id
WHERE e.course = 'Discrete Math';

Key takeaways

• An n-ary relation is a subset of A₁ × … × Aₙ. A database table is an n-ary relation.
• Selection filters rows, projection keeps columns, and join combines tables on matching values.
• A primary key makes "key ↦ row" a function.
• The mathematical model uses sets. SQL uses multisets unless you ask for DISTINCT.

Practice

1. (Beginner) Using the tables above, compute π_course(Enrolled) and σ_{major = 'Math'}(Students).
2. (Intermediate) Write a relational-algebra expression for the IDs of students who are enrolled in no course, then translate it to SQL using EXCEPT.
3. (Interview) SELECT major FROM Students returns duplicates, but π_major(Students) does not. Give a query where this difference changes the answer, for example with COUNT or with UNION versus UNION ALL. Hint: SQL uses bag (multiset) semantics.

<a id="25-equivalence-relations-and-orders"></a>

2.5 Equivalence Relations and Orders

Two kinds of relations matter more than any others. Equivalence relations capture "the same in some respect", and orders capture "comes before". Equivalence relations underlie modular arithmetic, hashing, and union–find. Orders underlie sorting, scheduling, version control, and dependency resolution.

Equivalence Relations

Why. Programs constantly treat different values as "the same": strings that differ only in case, numbers with the same remainder, files with the same content, records that describe the same customer. An equivalence relation is the precise definition of a well-behaved "sameness".

What. A relation ~ on A is an equivalence relation if it is

• reflexive: a ~ a for every a,
• symmetric: a ~ b implies b ~ a, and
• transitive: a ~ b and b ~ c imply a ~ c.

Relation	Set	Equivalence?
a ≡ b (mod n), meaning n ∣ (a − b)	ℤ	Yes
Same length	Strings	Yes
Equal ignoring case	Strings	Yes
Same connected component	Vertices of an undirected graph	Yes
f(a) = f(b) for a fixed function f	Domain of f	Yes, always
|a − b| ≤ 1	ℝ	No: 0 ~ 1 and 1 ~ 2, but not 0 ~ 2
"Is a friend of"	People	No: not transitive, usually not reflexive
≤	ℤ	No: not symmetric

Equivalence via a key function. For any function f: A → B, the relation a ~ b ⟺ f(a) = f(b) is an equivalence relation, because it inherits reflexivity, symmetry, and transitivity from =. In fact every equivalence relation has this form: take f(a) to be the class of a (next topic). In practice, the cleanest way to define "sameness" is to compute a canonical form (lowercase the string, reduce the number mod n, sort the letters) and compare canonical forms.

Proof: congruence mod n is an equivalence relation.

• Reflexive: a − a = 0 = n · 0, so n ∣ (a − a).
• Symmetric: if a − b = nk, then b − a = n(−k).
• Transitive: if a − b = nk and b − c = nj, then a − c = n(k + j). ∎

In code. Python's __eq__ must be an equivalence relation, and it must agree with __hash__: if a == b then hash(a) == hash(b). Sets and dicts rely on both. Defining equality from a canonical key satisfies both requirements automatically.

class Tag:
    """Tags compare case-insensitively: equality is the kernel of casefold()."""
    def __init__(self, name):
        self.name = name

    def _key(self):
        return self.name.casefold()            # canonical form

    def __eq__(self, other):
        return isinstance(other, Tag) and self._key() == other._key()

    def __hash__(self):
        return hash(self._key())               # equal objects must have equal hashes

tags = {Tag("Python"), Tag("python"), Tag("PYTHON"), Tag("Rust")}
print(len(tags))                               # 2

# A "tolerance" equality is NOT an equivalence relation: transitivity fails
close = lambda x, y: abs(x - y) <= 0.1
print(close(0.0, 0.08), close(0.08, 0.16), close(0.0, 0.16))   # True True False

Key takeaways

• An equivalence relation is reflexive, symmetric, and transitive.
• "Same value under a key function" is always an equivalence relation, and every equivalence relation can be written this way.
• Congruence mod n is the standard example and the basis of modular arithmetic (Chapter 4).
• Tolerance-based "approximately equal" relations are not transitive and must not be used as __eq__.

Practice

1. (Beginner) Which of these are equivalence relations on ℤ? a R b iff a + b is even; a R b iff a − b is odd; a R b iff |a| = |b|.
2. (Intermediate) Prove that for any function f: A → B, the relation a ~ b ⟺ f(a) = f(b) is an equivalence relation on A.
3. (Interview) A Point class defines __eq__ as "the distance between the points is less than 1e-9" and is then used as a dictionary key. What can go wrong? Hint: check transitivity, and ask what __hash__ could possibly return.

Equivalence Classes

Why. An equivalence relation sorts elements into groups of mutually equivalent elements. It is often simpler to work with the groups than with individual elements. The residue classes mod n, for example, are the "numbers" of modular arithmetic, and grouping anagrams is grouping by a class.

What. The equivalence class of a is

[a] = { x ∈ A | x ~ a }

Any element of a class is a representative of it. The set of all classes is the quotient set A/~.

Theorem. For a, b ∈ A, the following are equivalent:

1. a ~ b
2. [a] = [b]
3. [a] ∩ [b] ≠ ∅

So two classes are either identical or disjoint. They never partially overlap.

Proof of 3 ⇒ 1. Let c ∈ [a] ∩ [b]. Then c ~ a and c ~ b. By symmetry a ~ c, and by transitivity a ~ b. ∎

Example: congruence mod 3.

[0] = { …, −6, −3, 0, 3, 6, … }
[1] = { …, −5, −2, 1, 4, 7, … }        ℤ/3ℤ = { [0], [1], [2] }
[2] = { …, −4, −1, 2, 5, 8, … }

Infinitely many integers collapse into just three classes. [1] = [4] = [−2], because these are three names for the same class.

Canonical representatives. To compute with classes, pick one standard representative per class: the remainder in {0, …, n − 1}, the lowercase spelling, the sorted letters. Grouping by that representative computes the classes.

from collections import defaultdict

def classes(items, key):
    """Equivalence classes of x ~ y  ⟺  key(x) == key(y)."""
    groups = defaultdict(list)
    for x in items:
        groups[key(x)].append(x)        # key(x) is the canonical representative of [x]
    return list(groups.values())

print(classes(range(-4, 6), lambda n: n % 3))
# [[-4, -1, 2, 5], [-3, 0, 3], [-2, 1, 4]]

words = ["listen", "google", "silent", "enlist", "gogole"]
print(classes(words, lambda w: "".join(sorted(w))))
# [['listen', 'silent', 'enlist'], ['google', 'gogole']]

When there is no key function. Sometimes the relation is given only as a list of "same as" pairs, for example duplicate-record pairs reported by a matcher. The smallest equivalence relation containing these pairs is their reflexive, symmetric, and transitive closure (2.4). The union–find (disjoint-set) structure computes its classes efficiently:

from collections import defaultdict

def find(parent, x):
    while parent[x] != x:
        parent[x] = parent[parent[x]]     # path halving keeps the trees shallow
        x = parent[x]
    return x

def union(parent, a, b):
    parent[find(parent, a)] = find(parent, b)

parent = {x: x for x in "abcdef"}
for a, b in [("a", "b"), ("c", "d"), ("b", "d"), ("e", "f")]:   # known "same as" pairs
    union(parent, a, b)

groups = defaultdict(set)
for x in parent:
    groups[find(parent, x)].add(x)
print(sorted(sorted(g) for g in groups.values()))   # [['a', 'b', 'c', 'd'], ['e', 'f']]

Key takeaways

• [a] is the set of everything equivalent to a. The classes form the quotient set A/~.
• Two classes are either equal or disjoint, and [a] = [b] exactly when a ~ b.
• Compute classes by grouping on a canonical representative.
• If the relation is given as pairs, union–find computes the classes of its closure.

Practice

1. (Beginner) List the equivalence classes of congruence mod 4 on {0, 1, …, 11}.
2. (Intermediate) On ℤ × (ℤ − {0}), define (a, b) ~ (c, d) iff ad = bc. Prove that ~ is an equivalence relation (transitivity needs care) and describe its classes. Which familiar number system is the quotient set?
3. (Interview) A deduplication model outputs pairs of record IDs it believes refer to the same customer. Produce groups of records that refer to the same customer, in near-linear time. Hint: the pairs generate an equivalence relation. Which data structure merges classes cheaply?

Partitions

Why. Splitting a set into non-overlapping groups is common: shards of a database, clusters of data points, the input classes of a test plan. Partitions turn out to be exactly the same thing as equivalence relations, viewed from a different angle.

What. A partition of A is a collection of subsets A₁, A₂, … (called blocks) such that

1. every block is non-empty,
2. the blocks are pairwise disjoint, and
3. their union is A.

A = {1, 2, 3, 4, 5, 6}
┌───────────────────────────────────┐
│  ┌────────┐ ┌────────┐ ┌────────┐ │
│  │ 3   6  │ │ 1   4  │ │ 2   5  │ │     blocks of congruence mod 3
│  └────────┘ └────────┘ └────────┘ │
└───────────────────────────────────┘

Collection (subsets of {1, …, 6})	Partition?	Reason
{1, 4}, {2, 5}, {3, 6}	Yes	Non-empty, disjoint, covers everything
{1, 2}, {2, 3}, {4, 5, 6}	No	2 appears in two blocks
{1, 2, 3}, {4, 5}	No	6 is not covered
{1, 2, 3}, {4, 5, 6}, ∅	No	Empty block

Theorem (equivalence relations ↔ partitions). The equivalence classes of an equivalence relation on A form a partition of A. Conversely, every partition defines an equivalence relation: a ~ b iff a and b are in the same block. These two constructions are inverse to each other, so equivalence relations on A and partitions of A are in one-to-one correspondence.

Counting. The number of partitions of an n-element set is the Bell number Bₙ: 1, 1, 2, 5, 15, 52, 203, … for n = 0, 1, 2, …. By the theorem, a 3-element set has exactly 5 equivalence relations.

Refinement. Partition P refines Q if every block of P lies inside some block of Q. Congruence mod 6 refines congruence mod 3, because each class mod 6 lies inside one class mod 3. Refinement is a partial order on partitions (next topics).

Equivalence partitioning in testing. Inputs that the specification treats the same way form one class. Testing one representative per class, plus values at the class boundaries, gives good coverage with few tests.

def is_partition(blocks, A):
    seen = set()
    for block in blocks:
        if not block or seen & block:          # empty block, or overlap with an earlier block
            return False
        seen |= block
    return seen == set(A)                      # the blocks must cover A

def relation_from_partition(blocks):
    """a ~ b iff a and b are in the same block."""
    return {(a, b) for block in blocks for a in block for b in block}

A = range(1, 7)
print(is_partition([{1, 4}, {2, 5}, {3, 6}], A))       # True
print(is_partition([{1, 2}, {2, 3}, {4, 5, 6}], A))    # False: overlap
print(is_partition([{1, 2, 3}, {4, 5}], A))            # False: 6 missing

R = relation_from_partition([{1, 4}, {2, 5}, {3, 6}])
print(R == {(a, b) for a in A for b in A if (a - b) % 3 == 0})   # True: congruence mod 3

Key takeaways

• A partition splits a set into non-empty, pairwise disjoint blocks that cover it.
• Equivalence relations and partitions are the same information: classes are blocks, and blocks define "same block" relations.
• The number of partitions of an n-element set is the Bell number Bₙ.
• One representative per block plus boundary values is the basis of equivalence-partition testing.

Practice

1. (Beginner) Which are partitions of {1, …, 6}? {{1, 2}, {3, 4}, {5, 6}}, {{1, 2, 3, 4, 5, 6}}, {{1}, {2, 3}, {3, 4, 5, 6}}.
2. (Intermediate) List all 5 partitions of {a, b, c}. For each, write the corresponding equivalence relation as a set of pairs.
3. (Interview) A validation function treats ages below 0 as invalid, 0–17 as minor, 18–64 as adult, 65–150 as senior, and above 150 as invalid. Design a minimal test set using equivalence partitioning and boundary-value analysis. Hint: one representative per block, plus the values on each side of every boundary.

Partial Orders

Why. Many "comes before" relations leave some pairs unordered. Two tasks may both depend on a third without depending on each other. Two Git branches may both descend from a commit without either containing the other. Partial orders describe exactly this: order where it exists, and no forced comparison where it does not.

What. A relation ≼ on S is a partial order if it is reflexive, antisymmetric, and transitive. The pair (S, ≼) is a partially ordered set (poset).

• a and b are comparable if a ≼ b or b ≼ a, and incomparable otherwise.
• A strict partial order ≺ is irreflexive and transitive, like < or ⊂. Convert between the two with a ≺ b ⟺ a ≼ b ∧ a ≠ b.

Poset	Comparable pair	Incomparable pair
(ℤ, ≤)	Every pair	None (it is a total order)
(P({a, b}), ⊆)	{a} ⊆ {a, b}	{a} and {b}
(ℤ⁺, ∣)	2 ∣ 6	2 and 3
Commits ordered by "is an ancestor of or equal to"	A commit and its descendant	Tips of two diverged branches
ℕ² with (a, b) ≼ (c, d) iff a ≤ c and b ≤ d	(1, 2) ≼ (3, 4)	(1, 2) and (2, 1)

Special elements.

Term	Meaning
Minimal element	Nothing is strictly below it
Least element	It is below everything (at most one exists)
Maximal element	Nothing is strictly above it
Greatest element	It is above everything (at most one exists)
Upper bound of X	An element above every element of X
Least upper bound (lub, supremum)	The least of the upper bounds, if there is one
Lower bound / greatest lower bound (glb, infimum)	Defined symmetrically

Maximal is not the same as greatest. In ({2, 3, 4, 6}, ∣), both 4 and 6 are maximal (nothing in the set is a proper multiple of them), but neither is greatest, because 4 ∤ 6 and 6 ∤ 4. Similarly, 2 and 3 are minimal, and there is no least element.

In distributed systems. Vector clocks order events by the component-wise order above. If neither clock is ≼ the other, the events are concurrent: neither could have influenced the other.

def leq(u, v):
    """Component-wise order: u ≼ v iff u[i] <= v[i] for every i."""
    return all(a <= b for a, b in zip(u, v))

def compare(u, v):
    if leq(u, v) and leq(v, u):
        return "equal"
    if leq(u, v):
        return "before"
    if leq(v, u):
        return "after"
    return "concurrent"                   # incomparable: neither happened before the other

print(compare((1, 0, 2), (2, 1, 2)))      # before
print(compare((2, 0, 0), (1, 3, 0)))      # concurrent

Key takeaways

• A partial order is reflexive, antisymmetric, and transitive. Some pairs may be incomparable.
• Strict partial orders (<, ⊂) are irreflexive and transitive.
• Maximal and minimal elements can be many. Greatest and least elements are unique if they exist.
• Subsets, divisibility, Git ancestry, and vector clocks are all partial orders that are not total.

Practice

1. (Beginner) In the poset ({1, 2, 3, 4, 6, 12}, ∣), find two incomparable elements, and the least and greatest elements if they exist.
2. (Intermediate) Prove that the component-wise order on ℕ² is a partial order but not a total order.
3. (Interview) A replicated key-value store uses vector clocks. Two replicas hold versions of the same key with clocks (3, 1, 0) and (2, 2, 0). Which version should win? Hint: check whether either clock is ≼ the other. If they are incomparable, what must the system do instead of picking a winner?

Hasse Diagrams

Why. The digraph of a partial order is cluttered. Every element has a loop, and every chain a ≼ b ≼ c forces an extra arrow a → c. A Hasse diagram keeps only the edges that carry information, which makes the structure of a poset visible at a glance.

What. Say b covers a if a ≺ b and there is no c with a ≺ c ≺ b. In other words, b is directly above a. The Hasse diagram draws only the covering pairs:

1. Remove all loops, since reflexivity is implied.
2. Remove every edge implied by transitivity, keeping only covering pairs.
3. Draw every edge pointing upward and drop the arrowheads, so that "higher" means "greater".

a ≼ b holds exactly when there is an upward path from a to b.

Example: (P({a, b, c}), ⊆).

                 {a,b,c}
               /    |    \
          {a,b}   {a,c}   {b,c}
            | \   /   \   / |
            |  \ /     \ /  |
            |   X       X   |
            |  / \     / \  |
            | /   \   /   \ |
           {a}     {b}     {c}
               \    |    /
                    ∅

The full digraph would have 27 arrows (19 non-loop pairs plus 8 loops). The Hasse diagram has 12 edges.

Example: divisors of 12 under divisibility.

         12
        /  \
      4      6
      |     /|
      |   /  |
      | /    |
      2      3
       \    /
         1

Reading the diagram: 1 is the least element and 12 is the greatest. 4 and 6 are incomparable, and so are 2 and 3, and 4 and 3. 2 ∣ 12 holds because there is an upward path 2 → 4 → 12.

def hasse_edges(S, leq):
    """Covering pairs (a, b): a < b with nothing strictly between them."""
    lt = lambda a, b: a != b and leq(a, b)
    return sorted((a, b) for a in S for b in S
                  if lt(a, b) and not any(lt(a, c) and lt(c, b) for c in S))

divisors = [1, 2, 3, 4, 6, 12]
print(hasse_edges(divisors, lambda a, b: b % a == 0))
# [(1, 2), (1, 3), (2, 4), (2, 6), (3, 6), (4, 12), (6, 12)]

Key takeaways

• A Hasse diagram draws only covering pairs, with greater elements placed higher.
• Loops and transitive edges are omitted because they can be recovered.
• a ≼ b exactly when there is an upward path from a to b.
• Minimal, maximal, least, and greatest elements are easy to read off the diagram.

Practice

1. (Beginner) Draw the Hasse diagram of ({1, 2, 3, 5, 6, 10, 15, 30}, ∣). Compare its shape with the diagram of P({a, b, c}). Why are they the same?
2. (Intermediate) How many edges does the Hasse diagram of (P(S), ⊆) have when |S| = n? Hint: each edge adds exactly one element to a subset.
3. (Interview) Is the graph shown by git log --graph always the Hasse diagram of the "is an ancestor of" order? Hint: consider a --no-ff merge of a feature branch when main has not moved since the branch was created. Is the edge from the merge commit to its first parent a covering pair?

Total Orders

Why. Sorting needs every pair of elements to be comparable, otherwise there is no single correct position for each one. A total order is a partial order with no incomparable pairs: everything lines up.

What. A partial order ≼ on S is a total order (linear order) if every two elements are comparable:

∀a ∀b  (a ≼ b  ∨  b ≼ a)

The corresponding strict order satisfies trichotomy: exactly one of a ≺ b, a = b, b ≺ a holds.

Related terms:

• A chain in a poset is a subset that is totally ordered. An antichain is a subset in which no two elements are comparable.
• A well-order is a total order in which every non-empty subset has a least element. (ℕ, ≤) is well-ordered, while (ℤ, ≤) and (ℚ≥0, ≤) are not. This is the basis of induction (Chapter 3).

	Partial order	Total order	Well-order
Every pair comparable	Not required	Yes	Yes
Every non-empty subset has a least element	Not required	Not required	Yes
Example	(P(S), ⊆)	(ℤ, ≤)	(ℕ, ≤)

Lexicographic order. Given total orders on A and B, order pairs by the first component and break ties with the second:

(a₁, b₁) ≺ (a₂, b₂)   iff   a₁ ≺ a₂   or   (a₁ = a₂ and b₁ ≺ b₂)

This is how dictionaries order words and how multi-key sorts work. Lexicographic order on strings is total, but it is not a well-order: b ≻ ab ≻ aab ≻ aaab ≻ … descends forever. That is why the enumeration of all strings in 2.3 used shortlex order (by length first), which is a well-order.

people = [("ana", 30), ("ben", 25), ("cleo", 30), ("dev", 25)]

# Lexicographic order on the key (age descending, name ascending)
print(sorted(people, key=lambda p: (-p[1], p[0])))
# [('ana', 30), ('cleo', 30), ('ben', 25), ('dev', 25)]

words = ["b", "ab", "aab", "a"]
print(sorted(words))                                   # ['a', 'aab', 'ab', 'b']   lexicographic
print(sorted(words, key=lambda s: (len(s), s)))        # ['a', 'b', 'ab', 'aab']   shortlex

# Version strings need lexicographic order on integer tuples, not on characters
versions = ["1.10.0", "1.2.3", "1.2.10"]
print(sorted(versions))                                            # ['1.10.0', '1.2.10', '1.2.3']
print(sorted(versions, key=lambda v: tuple(map(int, v.split(".")))))  # ['1.2.3', '1.2.10', '1.10.0']

Key takeaways

• A total order is a partial order in which every pair is comparable. Sorting requires one.
• Chains are totally ordered subsets. Antichains have no comparable pairs.
• Lexicographic order on tuples is total when each component order is total. Tuple keys in sorted use it.
• A well-order also requires every non-empty subset to have a least element. ℕ has one, ℤ does not.

Practice

1. (Beginner) Which of these are total orders? (ℤ, ≤), (P({1, 2}), ⊆), (ℤ⁺, ∣), strings under lexicographic order.
2. (Intermediate) Prove that lexicographic order on ℕ × ℕ is a total order. Is it a well-order?
3. (Interview) In the poset (P({1, …, n}), ⊆), what is the length of the longest chain? Find an antichain with more than n elements for n = 4. Hint: a chain can grow one element at a time. For the antichain, consider all subsets of one fixed size.

Lattices

Why. In many posets, any two elements have a best common upper bound and a best common lower bound. Sets have union and intersection, numbers under divisibility have lcm and gcd, and security levels can always be combined. This structure, a lattice, appears in program analysis, access control, and replicated data types that must merge without conflicts.

What. A lattice is a poset in which every pair of elements a, b has

• a least upper bound, called the join a ∨ b, and
• a greatest lower bound, called the meet a ∧ b.

Lattice	Order	Join a ∨ b	Meet a ∧ b
P(S)	⊆	A ∪ B	A ∩ B
ℤ⁺	∣	lcm(a, b)	gcd(a, b)
Any total order	≤	max(a, b)	min(a, b)
ℕᵏ	Component-wise ≤	Component-wise max	Component-wise min

A poset that is not a lattice. Below, a and b have two upper bounds, c and d, but c and d are incomparable, so there is no least upper bound.

     c     d
     | \ / |
     |  X  |
     | / \ |
     a     b

Divisibility on {1, 2, 3} also fails, because 2 and 3 have no upper bound in the set at all.

Laws. Join and meet are commutative, associative, and idempotent (a ∨ a = a), and they satisfy absorption (a ∨ (a ∧ b) = a). These are the same laws as the set identities of 2.1, which is no accident: (P(S), ⊆) is a lattice. A lattice with a top ⊤ and a bottom ⊥ is bounded, and every finite lattice is bounded. Boolean algebra (Chapter 11) is a lattice with extra structure.

Applications.

Area	Lattice	How join is used
Access control	Security levels (Public ≤ Internal ≤ Secret)	Combining data from two sources gets the join of their levels
Static analysis	Abstract values of variables	At a branch merge point, the analysis takes the join of both paths
CRDTs (replicated data)	Replica states	Replicas merge states with the join, so they converge in any order

Why join works for replication. Because join is commutative, associative, and idempotent, replicas can receive updates in any order, grouped in any way, and even more than once, and still end in the same state.

import math

def merge(u, v):
    """Join in the component-wise lattice: the least upper bound of two vectors."""
    return tuple(max(a, b) for a, b in zip(u, v))

# Grow-only counter CRDT: each replica counts its own increments in its own slot
r1, r2, r3 = (3, 0, 1), (1, 2, 1), (0, 0, 4)
a = merge(merge(r1, r2), r3)
b = merge(r3, merge(r2, r1))
print(a, a == b, merge(a, a) == a)    # (3, 2, 4) True True   order and duplicates do not matter
print(sum(a))                         # 9: the counter's value

print(math.lcm(12, 18), math.gcd(12, 18))   # 36 6   join and meet in (ℤ⁺, |)

Key takeaways

• A lattice is a poset in which every pair has a join (least upper bound) and a meet (greatest lower bound).
• (P(S), ⊆) with ∪, ∩, (ℤ⁺, ∣) with lcm and gcd, and every total order with max and min are lattices.
• Join and meet are commutative, associative, idempotent, and absorptive.
• These laws let replicated systems merge states safely in any order.

Practice

1. (Beginner) In (ℤ⁺, ∣), compute 12 ∨ 18 and 12 ∧ 18. In (P({1, 2, 3}), ⊆), compute {1, 2} ∨ {2, 3} and {1, 2} ∧ {2, 3}.
2. (Intermediate) Is ({1, 2, 3, 4, 6, 12}, ∣) a lattice? Is ({1, 2, 3, 12, 18}, ∣)? Justify each answer by checking joins and meets.
3. (Interview) Why must the merge function of a state-based CRDT be commutative, associative, and idempotent? How does defining it as a lattice join guarantee all three? Hint: in a real network, messages arrive out of order, are batched differently on different replicas, and are sometimes delivered twice.

Topological Sorting

Why. Build systems, package managers, course schedules, spreadsheet recalculation, and database migrations all face the same problem: given "X must happen before Y" constraints, find one order that satisfies all of them. Topological sorting solves it.

What. A linear extension of a partial order ≼ is a total order ≤_T that respects it: a ≺ b implies a <_T b. Every finite poset has at least one linear extension, and finding one is called topological sorting.

In graph terms, a directed graph has a topological order if and only if it has no directed cycle (it is a DAG). Its reachability relation is then a partial order. A cycle such as A → B → A makes the problem unsolvable.

Key lemma. Every finite non-empty poset has a minimal element. Start anywhere and keep stepping to a strictly smaller element. This cannot go on forever in a finite set without repeating, and a repeat would contradict antisymmetry.

Kahn's algorithm repeatedly removes a minimal element:

1. Compute the in-degree (number of prerequisites) of every vertex.
2. Put every vertex with in-degree 0 into a queue. These are the minimal elements.
3. Repeatedly remove a vertex from the queue, output it, and decrement the in-degree of its successors. Any successor that reaches 0 joins the queue.
4. If some vertices are never output, the graph has a cycle.

It runs in O(V + E) time. The order is usually not unique: whenever the queue holds several vertices, any of them can go next.

Example: course prerequisites.

 Intro Programming ──► Data Structures ──┐
                                         ▼
 Discrete Math ────────────────────► Algorithms ──► Compilers
       │                                                ▲
       └──────────► Theory of Computation ──────────────┘

Valid orders include Intro, Discrete, Data Structures, Theory, Algorithms, Compilers and Discrete, Theory, Intro, Data Structures, Algorithms, Compilers.

from collections import deque

def topological_sort(nodes, edges):
    """Kahn's algorithm. Each edge (a, b) means a must come before b."""
    succ = {v: [] for v in nodes}
    indeg = {v: 0 for v in nodes}
    for a, b in edges:
        succ[a].append(b)
        indeg[b] += 1
    ready = deque(v for v in nodes if indeg[v] == 0)    # minimal elements: no prerequisites
    order = []
    while ready:
        v = ready.popleft()
        order.append(v)
        for w in succ[v]:                               # removing v may make w minimal
            indeg[w] -= 1
            if indeg[w] == 0:
                ready.append(w)
    if len(order) != len(nodes):
        raise ValueError("cycle detected: no topological order exists")
    return order

courses = ["Intro", "Discrete", "DataStructures", "Algorithms", "Theory", "Compilers"]
prereqs = [("Intro", "DataStructures"), ("DataStructures", "Algorithms"),
           ("Discrete", "Algorithms"), ("Discrete", "Theory"),
           ("Algorithms", "Compilers"), ("Theory", "Compilers")]
print(topological_sort(courses, prereqs))
# ['Intro', 'Discrete', 'DataStructures', 'Theory', 'Algorithms', 'Compilers']

try:
    topological_sort(["A", "B"], [("A", "B"), ("B", "A")])
except ValueError as e:
    print(e)                                            # cycle detected: no topological order exists

Python's standard library also provides graphlib.TopologicalSorter, which implements the same idea and supports parallel processing through its get_ready() and done() methods.

Key takeaways

• A topological sort is a linear extension: a total order consistent with all the "before" constraints.
• One exists exactly when the dependency graph has no directed cycle.
• Kahn's algorithm repeatedly outputs a minimal element and runs in O(V + E).
• Topological orders are usually not unique, and any vertex in the ready queue can be processed next.

Practice

1. (Beginner) Give two topological orders of the course graph above that differ from the two listed.
2. (Intermediate) Prove that a finite directed graph has a topological order if and only if it has no directed cycle. Hint: for one direction, show that a cycle makes an order impossible. For the other, show that a DAG always has a vertex with in-degree 0, then use induction on the number of vertices.
3. (Interview) A build tool must compile targets on k parallel workers while respecting dependencies. How would you adapt Kahn's algorithm, and what limits the speedup no matter how large k is? Hint: everything in the ready queue can run at the same time. Think about the longest dependency path, the critical path.

<a id="3-induction-and-recursion"></a>