Appendix B: Sets, Etc.

This appendix reviews notations, definitions, and elementary properties of sets, relations, functions, graphs, and trees used throughout CLRS.

---

B.1 Sets

A set is a collection of distinguishable objects, called its members or elements.

• If object x is a member of set S, we write x ∈ S
• If x is not a member, we write x ∉ S
• A set cannot contain the same object more than once (a multiset can)
• Elements are not ordered: {1, 2, 3} = {3, 2, 1}
• Two sets A and B are equal (A = B) if they contain the same elements

Special Sets

• ∅ — the empty set (no members)
• ℤ — the integers {..., −2, −1, 0, 1, 2, ...}
• ℝ — the real numbers
• ℕ — the natural numbers {0, 1, 2, ...}

Subsets

• A ⊆ B (subset): every element of A is also in B
• A ⊂ B (proper subset): A ⊆ B but A ≠ B
• For any set A: A ⊆ A and ∅ ⊆ A
• A = B if and only if A ⊆ B and B ⊆ A
• If A ⊆ B and B ⊆ C, then A ⊆ C (transitivity)

Set-Builder Notation

• Define a set by a property: {x : x ∈ ℤ and x/2 is an integer} (the even integers)
• The colon ":" is read "such that"

Set Operations

• Intersection: A ∩ B = {x : x ∈ A and x ∈ B}
• Union: A ∪ B = {x : x ∈ A or x ∈ B}
• Difference: A − B = {x : x ∈ A and x ∉ B}

Laws of Set Operations

1. Empty set laws: A ∩ ∅ = ∅ ; A ∪ ∅ = A
2. Idempotency laws: A ∩ A = A ; A ∪ A = A
3. Commutative laws: A ∩ B = B ∩ A ; A ∪ B = B ∪ A
4. Associative laws: A ∩ (B ∩ C) = (A ∩ B) ∩ C ; A ∪ (B ∪ C) = (A ∪ B) ∪ C
5. Distributive laws:
   • A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C)
   • A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C)
6. Absorption laws: A ∩ (A ∪ B) = A ; A ∪ (A ∩ B) = A
7. DeMorgan's laws:
   • A − (B ∩ C) = (A − B) ∪ (A − C)
   • A − (B ∪ C) = (A − B) ∩ (A − C)

Complement

Given a universe U (a larger set containing all sets under consideration), the complement of A is:

• Ā = U − A = {x : x ∈ U and x ∉ A}

Complement laws:

• Double complement: Ā̄ = A
• A ∩ Ā = ∅
• A ∪ Ā = U

DeMorgan's laws with complements (for B, C ⊆ U):

• B ∩ C (complement) = B̄ ∪ C̄
• B ∪ C (complement) = B̄ ∩ C̄

Disjoint Sets and Partitions

• Two sets are disjoint if A ∩ B = ∅
• A collection S = {Sᵢ} of nonempty sets forms a partition of S if:
  1. The sets are pairwise disjoint: i ≠ j implies Sᵢ ∩ Sⱼ = ∅
  2. Their union is S: S = ∪ Sᵢ
• Every element of S appears in exactly one Sᵢ

Cardinality

• The cardinality (or size) of a set S is denoted |S|
• |∅| = 0
• A set is finite if its cardinality is a natural number; otherwise it is infinite
• An infinite set in one-to-one correspondence with ℕ is countably infinite; otherwise it is uncountable
  • ℤ is countable; ℝ is uncountable

Key identity for finite sets:

• |A ∪ B| = |A| + |B| − |A ∩ B|
• Therefore |A ∪ B| ≤ |A| + |B|
• If A and B are disjoint: |A ∪ B| = |A| + |B|
• If A ⊆ B: |A| ≤ |B|

Terminology:

• An n-set is a finite set of n elements
• A 1-set is a singleton
• A k-subset is a subset of k elements

Power Set

• The power set 2^S is the set of all subsets of S (including ∅ and S itself)
• Example: 2^{a,b} = {∅, {a}, {b}, {a, b}}
• |2^S| = 2^|S| for finite S

Ordered Pairs and Cartesian Products

• An ordered pair (a, b) is defined formally as {a, {a, b}}

  • (a, b) ≠ (b, a) in general

• The Cartesian product A × B = {(a, b) : a ∈ A and b ∈ B}

  • |A × B| = |A| · |B| for finite sets

• The Cartesian product of n sets: A₁ × A₂ × ... × Aₙ = {(a₁, a₂, ..., aₙ) : aᵢ ∈ Aᵢ}

  • |A₁ × A₂ × ... × Aₙ| = |A₁| · |A₂| · ... · |Aₙ|

• An n-fold Cartesian product: Aⁿ = A × A × ... × A (n times)

  • |Aⁿ| = |A|ⁿ

---

B.2 Relations

A binary relation R on two sets A and B is a subset of the Cartesian product A × B.

• If (a, b) ∈ R, we write a R b
• An n-ary relation on sets A₁, A₂, ..., Aₙ is a subset of A₁ × A₂ × ... × Aₙ

Properties of Binary Relations (R ⊆ A × A)

• Reflexive: a R a for all a ∈ A
  • Example: "=" and "≤" are reflexive on ℕ; "<" is not
• Symmetric: a R b implies b R a for all a, b ∈ A
  • Example: "=" is symmetric; "<" and "≤" are not
• Transitive: a R b and b R c imply a R c for all a, b, c ∈ A
  • Example: "<", "≤", and "=" are all transitive
• Antisymmetric: a R b and b R a imply a = b
  • Example: "≤" is antisymmetric on ℕ

Equivalence Relations

A relation that is reflexive, symmetric, and transitive is an equivalence relation.

• The equivalence class of a is [a] = {b ∈ A : a R b}
• Example: R = {(a, b) : a, b ∈ ℕ and a + b is even}
  • [4] = {0, 2, 4, 6, ...} (even numbers)
  • [3] = {1, 3, 5, 7, ...} (odd numbers)

Theorem B.1: An equivalence relation is the same as a partition.

• The equivalence classes of any equivalence relation R on a set A form a partition of A
• Any partition of A determines an equivalence relation on A for which the sets in the partition are the equivalence classes

Partial Orders

A relation that is reflexive, antisymmetric, and transitive is a partial order.

• A set with a partial order defined on it is a partially ordered set
• A partially ordered set may have several maximal elements (no other element is "greater") but no single maximum

Total Orders and Preorders

• A total relation: for all a, b ∈ A, either a R b or b R a (or both)
• A total order (or linear order): a partial order that is also a total relation
  • Example: "≤" on ℕ is a total order
• A total preorder: a total relation that is transitive (not necessarily reflexive and antisymmetric)

---

B.3 Functions

A function f is a binary relation on A and B such that for every a ∈ A, there exists precisely one b ∈ B with (a, b) ∈ f.

• Domain: the set A
• Codomain: the set B
• We write f : A → B and b = f(a)

Key Concepts

• Argument: the input a
• Value: the output b = f(a)
• Two functions are equal if they have the same domain, codomain, and f(a) = g(a) for all a

Sequences

• A finite sequence of length n is a function with domain {0, 1, ..., n − 1}
  • Denoted ⟨f(0), f(1), ..., f(n − 1)⟩
• An infinite sequence is a function with domain ℕ
  • Example: Fibonacci sequence ⟨0, 1, 1, 2, 3, 5, 8, 13, 21, ...⟩

Image and Range

• The image of a set A′ ⊆ A under f: f(A′) = {b ∈ B : b = f(a) for some a ∈ A′}
• The range of f is the image of its entire domain: f(A)

Types of Functions

1. Surjection (onto): the range equals the codomain — every element of B is mapped to

   • Example: f(n) = ⌊n/2⌋ from ℕ to ℕ is surjective
   • f(n) = 2n from ℕ to ℕ is not surjective (3 is never a value)

2. Injection (one-to-one): distinct arguments produce distinct values — a ≠ a′ implies f(a) ≠ f(a′)

   • Example: f(n) = 2n is injective
   • f(n) = ⌊n/2⌋ is not injective (f(2) = f(3) = 1)

3. Bijection (one-to-one correspondence): both injective and surjective

   • Example: f(n) = (−1)ⁿ⌈n/2⌉ is a bijection from ℕ to ℤ
   • A bijection from a set to itself is a permutation

Inverse Functions

• When f is bijective, the inverse f⁻¹ is defined by: f⁻¹(b) = a if and only if f(a) = b

---

B.4 Graphs

Directed Graphs

A directed graph (or digraph) G = (V, E) where:

• V is a finite set of vertices
• E is a binary relation on V (set of edges)
• Self-loops (edges from a vertex to itself) are allowed

Undirected Graphs

An undirected graph G = (V, E) where:

• Each edge is an unordered pair {u, v} with u ≠ v
• (u, v) and (v, u) denote the same edge
• Self-loops are forbidden

Incidence and Adjacency

• Directed: edge (u, v) is incident from (leaves) u and incident to (enters) v
• Undirected: edge (u, v) is incident on both u and v
• Vertex v is adjacent to vertex u if (u, v) ∈ E
  • Adjacency is symmetric in undirected graphs, not necessarily in directed graphs

Degree

• Undirected graph: the degree of a vertex is the number of edges incident on it
  • A vertex with degree 0 is isolated
• Directed graph:
  • Out-degree: number of edges leaving the vertex
  • In-degree: number of edges entering the vertex
  • Degree = in-degree + out-degree

Paths and Cycles

• A path of length k from u to u′ is a sequence ⟨v₀, v₁, ..., vₖ⟩ where u = v₀, u′ = vₖ, and (vᵢ₋₁, vᵢ) ∈ E

• A simple path: all vertices are distinct

• A subpath: a contiguous subsequence of vertices in a path

• Cycle (directed): a path where v₀ = vₖ with at least one edge

  • Simple cycle: v₁, v₂, ..., vₖ are distinct
  • A self-loop is a cycle of length 1

• Cycle (undirected): a path where k > 0, v₀ = vₖ, and all edges are distinct

  • Simple cycle: v₁, v₂, ..., vₖ are distinct

• A graph with no simple cycles is acyclic

Connectivity

• An undirected graph is connected if every vertex is reachable from all others
• Connected components: equivalence classes of vertices under "is reachable from"
  • A graph is connected iff it has exactly one connected component
• A directed graph is strongly connected if every two vertices are mutually reachable
• Strongly connected components: equivalence classes under "are mutually reachable"

Graph Isomorphism

Two graphs G = (V, E) and G′ = (V′, E′) are isomorphic if there exists a bijection f : V → V′ such that (u, v) ∈ E if and only if (f(u), f(v)) ∈ E′.

Subgraphs

• G′ = (V′, E′) is a subgraph of G = (V, E) if V′ ⊆ V and E′ ⊆ E
• The subgraph induced by V′ ⊆ V: G′ = (V′, E′) where E′ = {(u, v) ∈ E : u, v ∈ V′}

Directed and Undirected Versions

• Directed version of an undirected graph: replace each edge (u, v) with two directed edges (u, v) and (v, u)
• Undirected version of a directed graph: remove directions and self-loops; collapse (u, v) and (v, u) into one edge
• A neighbor of u in a directed graph: any vertex adjacent to u in the undirected version

Special Graph Types

• Complete graph: undirected graph where every pair of vertices is adjacent
• Bipartite graph: vertices can be partitioned into V₁ and V₂ such that all edges go between V₁ and V₂
• Forest: acyclic, undirected graph
• Free tree: connected, acyclic, undirected graph
• DAG (directed acyclic graph): a directed graph with no cycles
• Multigraph: allows multiple edges between vertices and self-loops
• Hypergraph: each hyperedge connects an arbitrary subset of vertices

Graph Contraction

The contraction of G = (V, E) by edge e = (u, v):

• Merge u and v into a new vertex x
• Remove edge (u, v); reconnect all neighbors of u and v to x

---

B.5 Trees

B.5.1 Free Trees

A free tree is a connected, acyclic, undirected graph. A forest is an acyclic but possibly disconnected undirected graph.

Theorem B.2 (Properties of free trees): Let G = (V, E) be an undirected graph. The following are equivalent:

1. G is a free tree
2. Any two vertices are connected by a unique simple path
3. G is connected, but removing any edge disconnects it
4. G is connected, and |E| = |V| − 1
5. G is acyclic, and |E| = |V| − 1
6. G is acyclic, but adding any edge creates a cycle

B.5.2 Rooted and Ordered Trees

A rooted tree is a free tree with one distinguished vertex called the root.

Key terminology for a node x in a rooted tree T with root r:

• Ancestor of x: any node y on the unique simple path from r to x
• Descendant of x: any node for which x is an ancestor
• Proper ancestor/descendant: ancestor/descendant excluding the node itself
• Parent: the node y such that (y, x) is the last edge on the path from r to x
• Child: x is a child of y if y is the parent of x
• Siblings: nodes with the same parent
• Leaf (external node): a node with no children
• Internal node: a non-leaf node
• Subtree rooted at x: the tree induced by all descendants of x, rooted at x

Measurements:

• Degree of a node: number of children (not counting the parent)
• Depth of a node: length of the simple path from the root to the node
• Level: all nodes at the same depth
• Height of a node: number of edges on the longest downward path to a leaf
• Height of a tree: height of the root = largest depth of any node

An ordered tree is a rooted tree in which the children of each node are ordered (first child, second child, ..., kth child). Two trees can be identical as rooted trees but different as ordered trees if children appear in different order.

B.5.3 Binary and Positional Trees

A binary tree T is defined recursively as a structure that either:

• Contains no nodes (the empty tree or null tree, denoted NIL), or
• Is composed of a root node, a left subtree, and a right subtree (each a binary tree)

Key distinctions:

• A binary tree is NOT simply an ordered tree where each node has degree ≤ 2
• In a binary tree, the position (left vs. right) of a sole child matters
• In an ordered tree, a sole child has no left/right distinction

A full binary tree: every node is either a leaf or has exactly degree 2 (no degree-1 nodes). A binary tree can be represented by the internal nodes of a full binary tree, with missing children replaced by leaf nodes.

Positional and k-ary Trees

• A positional tree: children of a node are labeled with distinct positive integers; the ith child is absent if no child has label i
• A k-ary tree: a positional tree where all children with labels > k are missing
  • A binary tree is a k-ary tree with k = 2

Complete k-ary Trees

A complete k-ary tree: all leaves have the same depth and all internal nodes have degree k.

For a complete k-ary tree of height h:

• Number of leaves = kʰ
• Height with n leaves = logₖ n
• Number of internal nodes = (kʰ − 1) / (k − 1)
• For a complete binary tree: 2ʰ leaves and 2ʰ − 1 internal nodes