Metadata Card

• Prerequisites: Chapter 2 — Set Theory, Chapter 4 — Recursion
• Estimated time: 50 minutes
• Core difficulty: Intermediate
• Completion marker: Master the properties of relations, distinguish different types of functions, understand equivalence relations and partial orders

Your Progress

Fifth floor. The Librarian hands you a reference table — on the left is "User ID," on the right is "User Name." Then another table — left column "Student," right column "Enrolled Courses." What common structure do these two tables share? And what differs?

Your Task

You work with "relations" every day — database tables are relations, variable assignments are relations, API calls are mappings. But mathematically, a relation is a subset of the Cartesian product of sets, and a function is a special kind of relation. This chapter clarifies the precise mathematical definitions of "relation" and "function."

Chapter Layers

• Required reading: Definition and properties of relations, equivalence relations, injective/surjective/bijective functions
• Optional reading: Partial orders and lattices, closures

Breakthrough · Origin Story

You're designing a database schema. A user can follow another user — that's a follows relation. A student belongs to a class — that's a belongs_to relation. You intuitively know the difference between "1-to-1," "1-to-many," and "many-to-many," but what exactly is the mathematical distinction?

A relation is a pairing of elements from two sets. The Cartesian product A×B of A and B is the set of all ordered pairs (a,b) where a∈A, b∈B. A relation R from A to B is a subset of A×B.

A = {1, 2, 3}, B = {a, b}
A×B = {(1,a), (1,b), (2,a), (2,b), (3,a), (3,b)}
Relation R = {(1,a), (2,a), (3,b)}  // Describes a pairing rule

Properties of relations determine what type of relation it is:

Property	Definition	Example
Reflexive	Every element relates to itself	"equals" is reflexive
Symmetric	aRb implies bRa	"is sibling of" is symmetric
Antisymmetric	aRb and bRa implies a=b	"less than or equal to" is antisymmetric
Transitive	aRb and bRc implies aRc	"greater than" is transitive

An equivalence relation satisfies reflexivity, symmetry, and transitivity. Equivalence relations partition a set into disjoint equivalence classes. "Congruent modulo 3" is a typical equivalence relation — all integers are divided into three equivalence classes: [0], [1], [2]. When you implement hashCode(), you're defining an equivalence relation: a.equals(b) → a and b must be in the same equivalence class.

A partial order satisfies reflexivity, antisymmetry, and transitivity. A typical example: set inclusion ⊆. File system directory structures, type system subtype relations, task dependencies — these are all partial orders.

A function is a special type of relation: each input corresponds to exactly one output.

f: A → B is read as "a function from A to B." A is the domain, B is the codomain.

Functions have three core properties:

• Injective (one-to-one): Different inputs map to different outputs. f(a₁) = f(a₂) → a₁ = a₂.
• Surjective (onto): Every element of the codomain is mapped to by at least one input.
• Bijective (one-to-one correspondence): Both injective and surjective — each input maps to a unique output, and each output has a unique input.

A unique index in a database is an injective constraint. Bijections are the foundation of cryptography: an encryption function (bijection) ensures you can decrypt back.

Types of functions are equally important in programming:

• Partial function: Not defined for all inputs. For example, "1/x" is undefined at x=0. In programming terms, this corresponds to a function that returns Optional or throws an exception.
• Total function: Defined for all inputs. Most functions in programming are total — at least syntactically.
• Recursive function: Defined in terms of itself, with a termination condition. Discussed in depth in the previous chapter.

Common Pitfalls

• Confusing relations and functions. All functions are relations, but not all relations are functions. A relation can map one input to multiple outputs; a function cannot.
• Misinterpreting "relation" in "relational databases" as mathematical relations. "Relation" in relational databases refers to a table (a subset of a Cartesian product). The concepts are historically connected but not identical.
• Confusing a function signature with its definition. f: int → int only tells you the input and output types, not the computation rule. f(x) = x² is the complete definition.

Challenge Questions

• Determine whether the relation R = {(a,b) | a and b were born in the same year} is reflexive, symmetric, and transitive.
• Given f: Z → Z, f(x) = 2x, determine whether it is injective or surjective (where Z is the set of integers).
• Implement a simple equivalence relation checker in Python — given a relation matrix, determine if it satisfies reflexivity, symmetry, and transitivity.

Traveler's Notes

Relations are pairings; functions are mappings. With additional constraints, relations become equivalence relations (classification), partial orders (ordering), and functions (deterministic mappings). This is one of the core perspectives of discrete mathematics.

→ Next stop: Discrete mathematics wraps up here. Next, you enter the world of combinatorics — "If I have 5 shirts and 3 pairs of pants, how many outfits can I make?" From logic to counting.