Relations

Relations formalize the concept of "connections" or "associations" between objects. They are essential for understanding databases, graph theory, ordering, and equivalence.

Binary Relations

A binary relation R from set A to set B is a subset of A × B.

R ⊆ A × B

If (a, b) ∈ R, we write aRb and say "a is related to b."

Example: Let A = {1, 2, 3}, B = {a, b}. Then R = {(1, a), (1, b), (3, a)} is a relation from A to B.

A relation on a set A means R ⊆ A × A.

Example: "less than" on ℤ: R = {(a, b) ∈ ℤ × ℤ | a < b}.

Representations

Set of pairs: R = {(1, 2), (2, 3), (1, 3)}

Matrix representation: For finite sets A = {a₁, ..., aₘ} and B = {b₁, ..., bₙ}, the relation matrix M is m × n where Mᵢⱼ = 1 if (aᵢ, bⱼ) ∈ R.

     a  b
1  [ 1  1 ]
2  [ 0  0 ]
3  [ 1  0 ]

Directed graph (digraph): Each element is a node, and (a, b) ∈ R is a directed edge from a to b.

Properties of Relations on a Set

Let R be a relation on set A.

Reflexive

∀a ∈ A, (a, a) ∈ R

Every element is related to itself.

≤ on ℤ is reflexive (a ≤ a for all a). ✓
< on ℤ is not reflexive (a < a is false). ✗
= on any set is reflexive. ✓

In the matrix: all diagonal entries are 1. In the digraph: every node has a self-loop.

Irreflexive: ∀a ∈ A, (a, a) ∉ R. (No element is related to itself.)

Symmetric

∀a, b ∈ A, (a, b) ∈ R → (b, a) ∈ R

If a is related to b, then b is related to a.

"is sibling of" is symmetric. ✓
≤ is not symmetric (1 ≤ 2 but 2 ≰ 1). ✗
= is symmetric. ✓

In the matrix: M = Mᵀ (symmetric matrix). In the digraph: every edge has a reverse edge.

Antisymmetric

∀a, b ∈ A, ((a, b) ∈ R ∧ (b, a) ∈ R) → a = b

If a is related to b and b is related to a, then a = b. (Different elements can be related one way, but not both.)

≤ is antisymmetric (a ≤ b and b ≤ a implies a = b). ✓
< is antisymmetric (vacuously — a < b and b < a never both hold). ✓
"is sibling of" is not antisymmetric. ✗

Note: A relation can be both symmetric and antisymmetric (e.g., the identity relation). A relation can be neither symmetric nor antisymmetric.

Transitive

∀a, b, c ∈ A, ((a, b) ∈ R ∧ (b, c) ∈ R) → (a, c) ∈ R

If a is related to b and b is related to c, then a is related to c.

≤ is transitive (a ≤ b and b ≤ c implies a ≤ c). ✓
"is parent of" is not transitive (parent of parent ≠ parent). ✗
= is transitive. ✓

| Relation | Reflexive | Symmetric | Antisymmetric | Transitive | |---|---|---|---|---| | = (equality) | ✓ | ✓ | ✓ | ✓ | | ≤ (less or equal) | ✓ | ✗ | ✓ | ✓ | | < (strict less) | ✗ | ✗ | ✓ | ✓ | | ≠ (not equal) | ✗ | ✓ | ✗ | ✗ | | ⊆ (subset) | ✓ | ✗ | ✓ | ✓ | | | (divides) | ✓ | ✗ | ✓* | ✓ |

(*on positive integers)

Equivalence Relations

A relation R on A is an equivalence relation if it is:

Reflexive: aRa for all a.
Symmetric: aRb implies bRa.
Transitive: aRb and bRc implies aRc.

An equivalence relation captures the idea of "sameness" or "interchangeability."

Examples

Equality (=) on any set.

Congruence modulo n: a ≡ b (mod n) iff n | (a - b).

Proof that ≡ (mod n) is an equivalence relation:

Reflexive: a - a = 0, and n | 0. ✓
Symmetric: if n | (a - b), then n | (-(a - b)) = (b - a). ✓
Transitive: if n | (a - b) and n | (b - c), then n | ((a - b) + (b - c)) = (a - c). ✓

Same length on strings: s₁ ~ s₂ iff |s₁| = |s₂|.

Same connected component in a graph: u ~ v iff there is a path from u to v.

Equivalence Classes

If R is an equivalence relation on A and a ∈ A, the equivalence class of a is:

[a] = {x ∈ A | xRa}

All elements equivalent to a.

Example: For ≡ (mod 3) on ℤ:

[0] = {..., -6, -3, 0, 3, 6, 9, ...}
[1] = {..., -5, -2, 1, 4, 7, 10, ...}
[2] = {..., -4, -1, 2, 5, 8, 11, ...}

Key properties:

Every element belongs to exactly one equivalence class.
Two equivalence classes are either identical or disjoint.
aRb if and only if [a] = [b].

Partitions

A partition of a set A is a collection of non-empty, pairwise disjoint subsets whose union is A.

Π = {A₁, A₂, ..., Aₖ} where:
  - Aᵢ ≠ ∅ for all i
  - Aᵢ ∩ Aⱼ = ∅ for i ≠ j
  - A₁ ∪ A₂ ∪ ... ∪ Aₖ = A

Fundamental Theorem

Every equivalence relation induces a partition (into equivalence classes), and every partition induces an equivalence relation (elements are related iff in the same block).

There is a bijection between equivalence relations on A and partitions of A.

Example: The partition {{evens}, {odds}} corresponds to the equivalence relation ≡ (mod 2).

Quotient Set

The set of all equivalence classes is called the quotient set:

A / R = {[a] | a ∈ A}

Example: ℤ / ≡₃ = {[0], [1], [2]} ≅ ℤ₃ (integers mod 3).

Partial Orders

A relation R on A is a partial order if it is:

Reflexive: aRa for all a.
Antisymmetric: aRb and bRa implies a = b.
Transitive: aRb and bRc implies aRc.

A set with a partial order is called a partially ordered set (poset), written (A, ≤).

Examples

(ℤ, ≤) — the usual "less than or equal"
(P(S), ⊆) — subsets ordered by inclusion
(ℤ⁺, |) — positive integers ordered by divisibility
(ℕ × ℕ, ≤ₗₑₓ) — lexicographic order

Comparable and Incomparable

In a poset (A, ≤):

a and b are comparable if a ≤ b or b ≤ a.
a and b are incomparable if neither a ≤ b nor b ≤ a.

In a partial order, some elements may be incomparable. For example, in (P({1,2,3}), ⊆), {1,2} and {2,3} are incomparable.

Total Orders

A partial order where every pair of elements is comparable:

∀a, b ∈ A, a ≤ b ∨ b ≤ a

Also called a linear order or chain.

Examples:

(ℤ, ≤) is a total order. ✓
(P(S), ⊆) is not a total order (for |S| ≥ 2). ✗

Strict Partial / Total Orders

A strict partial order is irreflexive, asymmetric, and transitive (e.g., <).

Given a partial order ≤, the strict order < is defined as: a < b iff a ≤ b and a ≠ b.

Well-Ordering

A total order ≤ on A is a well-ordering if every non-empty subset of A has a least element.

(ℕ, ≤) is well-ordered. ✓
(ℤ, ≤) is not well-ordered (no least integer). ✗

The Well-Ordering Theorem (equivalent to the Axiom of Choice): every set can be well-ordered.

Hasse Diagrams

A Hasse diagram is a visual representation of a finite poset:

Draw elements as dots, with smaller elements lower.
Draw an edge from a to b if a < b and there is no c with a < c < b (i.e., b covers a).
Omit self-loops and transitive edges (they are implied by the diagram).

Example: Divisibility on {1, 2, 3, 4, 6, 12}:

Special Elements in a Poset

Let (A, ≤) be a poset and S ⊆ A:

Maximum of S: element a ∈ S with a ≥ s for all s ∈ S. (May not exist.)
Minimum of S: element a ∈ S with a ≤ s for all s ∈ S. (May not exist.)
Maximal element: a ∈ S with no s ∈ S where a < s. (May have multiple.)
Minimal element: a ∈ S with no s ∈ S where s < a. (May have multiple.)
Upper bound of S in A: element u ∈ A with s ≤ u for all s ∈ S.
Lower bound of S in A: element l ∈ A with l ≤ s for all s ∈ S.
Least upper bound (supremum): the smallest upper bound. Written sup(S) or ∨S.
Greatest lower bound (infimum): the largest lower bound. Written inf(S) or ∧S.

Lattices

A poset (L, ≤) is a lattice if every pair of elements has both a least upper bound (join, ∨) and a greatest lower bound (meet, ∧).

A poset is a complete lattice if every subset (not just pairs) has both a supremum and an infimum.

Examples:

(P(S), ⊆) is a complete lattice with ∨ = ∪ and ∧ = ∩.
(ℤ⁺, |) with ∨ = lcm and ∧ = gcd is a lattice.
(ℕ, ≤) is a lattice (∨ = max, ∧ = min) but not complete (no supremum of ℕ itself).

Lattice Properties

Commutative: a ∨ b = b ∨ a, a ∧ b = b ∧ a
Associative: a ∨ (b ∨ c) = (a ∨ b) ∨ c
Absorption: a ∨ (a ∧ b) = a, a ∧ (a ∨ b) = a
Idempotent: a ∨ a = a, a ∧ a = a

A distributive lattice additionally satisfies:

a ∧ (b ∨ c) = (a ∧ b) ∨ (a ∧ c)
a ∨ (b ∧ c) = (a ∨ b) ∧ (a ∨ c)

A Boolean lattice (Boolean algebra) is a complemented distributive lattice.

Closures

Given a relation R on A, we can compute its closure — the smallest relation containing R that has a desired property.

Reflexive Closure

r(R) = R ∪ {(a, a) | a ∈ A} = R ∪ Δ

where Δ is the diagonal (identity) relation.

Symmetric Closure

s(R) = R ∪ R⁻¹ = R ∪ {(b, a) | (a, b) ∈ R}

Transitive Closure

t(R) = R ∪ R² ∪ R³ ∪ ... = ⋃ₖ₌₁^∞ Rᵏ

where Rᵏ = R composed with itself k times.

For a finite set with n elements: t(R) = R ∪ R² ∪ ... ∪ Rⁿ.

Warshall's algorithm computes the transitive closure in O(n³) time — this is essentially the same as Floyd-Warshall for reachability.

The transitive closure answers: "Can a reach b through a chain of relations?"

Composition of Relations

If R ⊆ A × B and S ⊆ B × C, then the composition S ∘ R ⊆ A × C:

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

In matrix form: M_{S∘R} = M_R · M_S (using Boolean multiplication).

Real-World Applications

Databases: Relations are literally the foundation of relational databases. Primary/foreign key relationships, joins, and normalization are all about relations.
Graph theory: A graph is a relation on a set of vertices. Directed graphs are binary relations; undirected graphs are symmetric relations.
Equivalence classes in compilers: Type equivalence, register allocation (interference), and optimization (congruence classes in value numbering).
Partial orders in scheduling: Task dependencies form a partial order. Topological sort linearizes it.
Lattices in static analysis: Abstract interpretation uses lattices to represent program states. The analysis computes fixpoints in the lattice.
Version control: Commit history forms a partial order (DAG). Merge is a join operation.
Sorting: Sorting algorithms operate on total orders. Partial orders arise in topological sorting.