Relations and Functions

Definition: A relation defines associations between elements of sets as a set of ordered pairs; a function is a special relation assigning exactly one output to each input element.

How It Works

A relation R from set A to set B is any subset of the Cartesian product A × B, a collection of ordered pairs (a, b)
A relation can be represented as a matrix, a directed graph, or a table of ordered pairs, three equivalent representations chosen based on which is most convenient for the task at hand
A function f: A → B is a relation where every element of A (the domain) maps to exactly one element of B (the codomain), no input maps to two different outputs
The range (or image) is the actual subset of the codomain that gets hit by the function, which can be smaller than the full codomain
An equivalence class groups every element related to a given one under an equivalence relation, and the full set of equivalence classes always partitions the original set into disjoint, exhaustive groups
Reflexive: every element relates to itself, ∀a, (a,a) ∈ R. Symmetric: (a,b) ∈ R implies (b,a) ∈ R. Transitive: (a,b) ∈ R and (b,c) ∈ R implies (a,c) ∈ R
An Equivalence Relation satisfies all three, reflexive, symmetric, and transitive, and partitions its underlying set into disjoint equivalence classes
A Partial Order satisfies reflexive, antisymmetric ((a,b) ∈ R and (b,a) ∈ R implies a = b), and transitive, modeling relationships like “divides” or “is a subset of” where not every pair is comparable
Injective (one-to-one): distinct inputs always map to distinct outputs, f(x1) = f(x2) implies x1 = x2. Surjective (onto): every element of the codomain is hit by at least one input. Bijective: both injective and surjective at once
Only a bijective function has a true inverse function, since inverting requires both that no output is missed (surjective) and that no output is produced by more than one input (injective)
Function composition (g ∘ f)(x) = g(f(x)) chains two functions together, and composing two bijections always produces another bijection
An identity function id(x) = x acts as the composition identity, f ∘ id = id ∘ f = f for any function f, mirroring how 0 behaves under addition

Relation Properties Reference

Property	Requirement	Example relation
Reflexive	`(a,a) ∈ R` for all `a`	“is equal to”
Symmetric	`(a,b) ∈ R ⟹ (b,a) ∈ R`	“is a sibling of”
Antisymmetric	`(a,b), (b,a) ∈ R ⟹ a = b`	“is less than or equal to”
Transitive	`(a,b), (b,c) ∈ R ⟹ (a,c) ∈ R`	“is an ancestor of”
Equivalence	Reflexive + Symmetric + Transitive	“has the same birthday month as”
Partial Order	Reflexive + Antisymmetric + Transitive	“divides” on the positive integers

Under the Hood

This function f maps 1 → a, 2 → a, 3 → b, 4 → c. Every domain element has exactly one outgoing arrow, confirming it’s a valid function, no input is left unmapped or mapped twice. It is not injective, since both 1 and 2 map to a, two distinct inputs sharing one output. It is surjective onto {a, b, c}, since every codomain element receives at least one arrow, c from 4, b from 3, and a from both 1 and 2. Because it’s surjective but not injective, it is not bijective, and has no true inverse function, a alone can’t be mapped back to a single unambiguous input.

Checking each property is mechanical once the diagram is drawn: injective fails the moment two domain arrows converge on the same codomain element, surjective fails the moment any codomain element has zero incoming arrows, and a function itself fails the moment any domain element has zero or more than one outgoing arrow.

The same diagram style, drawn without restricting each domain element to a single outgoing arrow, represents a general relation rather than a function. Relations allow one input to connect to several outputs simultaneously, which is exactly the flexibility a many-to-many database relationship or a general graph edge set needs.

Worked Example 1

Given: Determine whether f: ℤ → ℤ defined by f(x) = x² is injective.
Step: Check f(2) = 4 and f(-2) = 4. Two distinct inputs, 2 and -2, produce the same output, 4.
Answer: f(x) = x² is not injective over the integers, since f(2) = f(-2) but 2 ≠ -2.

Worked Example 2

Given: Determine whether f: ℝ → ℝ defined by f(x) = 2x + 3 is bijective.
Step: Injective: if 2x1 + 3 = 2x2 + 3, then x1 = x2, so it’s injective. Surjective: for any target y, solving y = 2x + 3 gives x = (y-3)/2, a valid real number for every real y, so it’s surjective.
Answer: f(x) = 2x + 3 is bijective, and its inverse is f⁻¹(y) = (y-3)/2.

Worked Example 3

Given: Verify that “congruence mod 3” (a ~ b if a ≡ b (mod 3)) is an equivalence relation on the integers.
Step: Reflexive: a ≡ a (mod 3) always, since a - a = 0 is divisible by 3. Symmetric: if a ≡ b (mod 3), then a - b is divisible by 3, so is b - a = -(a-b), so b ≡ a (mod 3). Transitive: if a ≡ b and b ≡ c, then a-b and b-c are both divisible by 3, so a-c = (a-b)+(b-c) is too.
Answer: All three properties hold, so congruence mod 3 is a valid equivalence relation, partitioning the integers into exactly 3 equivalence classes: {...,-3,0,3,6,...}, {...,-2,1,4,7,...}, {...,-1,2,5,8,...}.

Worked Example 4

Given: Verify whether “divides” (a | b, meaning a divides b evenly) is a partial order on the positive integers.
Step: Reflexive: every a divides itself (a | a). Antisymmetric: if a | b and b | a, then a = b (two positive integers that divide each other must be equal). Transitive: if a | b and b | c, then a | c (if b = ka and c = mb, then c = mka, so a | c).
Answer: All three hold, so “divides” is a valid partial order, though not a total order, since neither 2 | 3 nor 3 | 2 holds, making 2 and 3 incomparable under this relation.

Why It Matters

Provides formal mathematical definitions underlying database foreign keys (relations), type systems, and functional programming’s function-as-value model
Directly informs hashing and indexing design, a hash function needs to be well-defined (a true function) but doesn’t need to be injective, collisions are expected and handled separately
Justifies grouping and deduplication logic in software, “group by” operations and deduplication both implicitly rely on an equivalence relation defining what counts as “the same”
Clarifies API design, a function’s declared input and output types are exactly its domain and codomain, and a well-designed API keeps that mapping total and predictable
Underlies data modeling correctness, choosing whether a real-world relationship is one-to-one, one-to-many, or many-to-many determines the entire database schema design
Gives functional programming its theoretical foundation, pure functions map inputs to outputs with no side effects, mirroring the mathematical definition exactly, which is what makes them composable and testable in isolation

Common Pitfalls

Assuming a function is invertible without first proving it’s bijective, a function that’s only injective or only surjective doesn’t have a true two-sided inverse
Confusing the codomain (everything a function is declared to map into) with the range (what actually gets hit), a function can have a codomain much larger than its actual range
Treating a merely reflexive and symmetric relation as an equivalence relation without checking transitivity, all three properties are required, not just two
Forgetting that a relation isn’t automatically a function, a relation can map one input to multiple outputs, a function specifically cannot
Assuming antisymmetric means “not symmetric,” they’re independent properties, a relation can be neither, both (only for the identity relation), or just one
Treating a partial order as though every pair of elements must be comparable, unlike a total order, a partial order explicitly allows incomparable pairs

Comparison

	Function	Injective	Surjective	Bijective
Every input maps somewhere	Yes, exactly once	Yes	Yes	Yes
Distinct inputs, distinct outputs	Not required	Yes	Not required	Yes
Every codomain element is hit	Not required	Not required	Yes	Yes
Has a true inverse function	No, in general	No, in general	No, in general	Yes, always
Codomain size vs domain size	Unrestricted	Codomain ≥ domain (finite case)	Codomain ≤ domain (finite case)	Codomain = domain (finite case)
Common example	Any lookup table	`f(x) = x + 1` over integers	`f(x) = x mod 5`	`f(x) = x + 1`, restricted to a matching finite domain and codomain

Example

Hash functions map arbitrary key inputs to fixed-size bucket index outputs, a valid function (every key maps to exactly one bucket) that’s deliberately not injective, since the input space (all possible strings) vastly exceeds the output space (a fixed number of buckets), collisions between different keys are mathematically unavoidable and handled by the hash table’s collision-resolution strategy.

Database foreign keys formalize a relation between two tables directly: a Book.author_id column referencing Author.id defines exactly the kind of ordered-pair relation this term describes, and whether that relationship is modeled as one-to-many or many-to-many determines whether a join table is needed at all.

Referenced by

Dig deeper

Spot an error in this note?