5.3 Functions and Mappings: Domain, Image, Injectivity, and Surjectivity

The Archive City sends over a table showing the relationship between users and email addresses, and the Observation Tower requests that we precisely describe those constraints using functions, injective mappings, and surjective mappings.

A user-to-email table might allow multiple users to share the same email, or it might enforce email uniqueness. It might also include users without any email address at all. Mathematical functions break these constraints down into three key questions: "Does every input have an output?", "Is the output unique for each input?", and "Can different inputs map to the same output?"

Functions Are a Constrained Kind of Relation

Function:

f:A→B

It requires that for every a∈A, there exists a unique b∈B such that (a,b)∈f:

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

Thus, ordinary mathematical functions also require:

• Totality: Every input from the domain must have an output;
• Uniqueness: A single input must map to only one output.

Relations may be many-to-one, one-to-many, or omit some inputs; functions can only be many-to-one or one-to-one. They cannot be one-to-many, nor can they skip any element from the declared domain.

Domain, Codomain, and Image

For f:A→B:

• A: domain;
• B: codomain;
• f(A)={f(a)|a∈A}: image.

The image is always a subset of the codomain, but need not equal it.

f:ℤ→ℤ
f(n)=2n

The codomain is all integers, but the image consists only of even numbers. Chinese sources sometimes use "range" to refer to either the codomain or the image, leading to ambiguity; precise writing should clearly distinguish between "codomain" and "image."

The same computational rule can yield different surjectivity properties depending on the codomain:

f:ℤ→ℤ,   f(n)=2n      // not surjective
g:ℤ→2ℤ,  g(n)=2n      // surjective

A function is not solely defined by its formula, its domain and codomain are integral parts of its identity.

Injective, Surjective, Bijective

Injective

Different inputs produce different outputs:

f(a₁) = f(a₂) → a₁ = a₂

Equivalently: a₁≠a₂ → f(a₁)≠f(a₂).

Surjective

Every element in the codomain is mapped to by at least one element in the domain:

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

Bijective

Both injective and surjective: each element in the codomain has exactly one preimage. A bijection establishes a one-to-one correspondence and can be used to prove that two sets have the same cardinality.

Example:

f:ℤ→ℤ, f(n)=n+1

Both injective and surjective, with inverse function f⁻¹(n)=n-1.

Left Inverse, Right Inverse, and the True Inverse Function

If g:B→A:

g∘f = id_A     // g is a left inverse of f, implying f is injective
f∘g = id_B     // g is a right inverse of f, implying f is surjective

When both conditions hold, f is bijective, and g is the unique inverse function.

A non-injective function cannot uniquely recover the original input from its output. A non-surjective function, if attempted to be inverted over its entire codomain, will encounter elements without preimages.

Coding or decoding APIs should specify the subset of the domain where mutual inverses exist, and whether normalization results in information loss.

Function Composition

f:A→B
g:B→C
g∘f:A→C
(g∘f)(a)=g(f(a))

Composite satisfaction obeys the associative law:

h∘(g∘f)=(h∘g)∘f

It is generally not commutative. The type boundaries must also match: the codomain of f must be appropriate as the domain of g.

If f,g are both injective, their composition is injective; if both are surjective, their composition is surjective; if both are bijective, their composition is bijective, and:

(g∘f)⁻¹=f⁻¹∘g⁻¹

Partial Functions and Total Functionality

Mathematical partial functions may not be defined for certain inputs:

reciprocal(x) = 1/x, x ≠ 0

The domain can be narrowed accordingly:

reciprocal: ℝ \ {0} → ℝ

Alternatively, the codomain can be extended to explicitly represent failure as a value:

safeReciprocal: ℝ → Option<ℝ>

In programs, exceptions, crashes, and non-termination undermine the notion that a function returns a value of a declared type for all inputs. Static type signatures often fail to capture all side effects.

Modeling expected failures as Option/Result enables callers to handle them within normal control flow. However, events such as resource exhaustion or process termination may still lie outside the model.

Accurate Analogy for Database Unique Keys

If each row is mapped to a unique key and all rows have non-empty keys, a unique constraint ensures that this mapping is injective (meaning no two rows share the same key value) for the current set of rows. However, the semantics of unique constraints in SQL, represented by NULL, vary across databases, and the applicability of such constraints can be further modified by composite indexes or conditional indexes.

A unique index does not guarantee surjectivity: the vast majority of possible key values may not correspond to any existing row. Furthermore, primary keys also enforce non-null constraints and serve as row identity within the database's contractual agreements, thus, they cannot be fully described by the concept of "injectivity" alone.

Encryption Functions Are Not Necessarily Bijective

An ideal block cipher with a fixed key operates as a permutation over a fixed-length block space, meaning encryption and decryption are inverses of each other. However, modern cryptographic schemes typically also accept additional inputs such as nonces, random numbers, and associated data, and produce ciphertexts accompanied by authentication tags. If we simply describe the function as "plaintext → ciphertext," different random inputs can lead to entirely different ciphertexts.

Thus, the statement "the encryption function is bijective" holds true only under explicit assumptions of fixed key, fixed parameters, and a finite block space. Security in these schemes is not solely derived from the bijective property.

Counting Functions on Finite Sets

If:

|A| = m, |B| = n

The total number of functions from A to B is:

n^m

Because each element in A independently chooses one of the n outputs in n.

When m≤n, the number of injective (one-to-one) functions is:

n(n-1)(n-2)...(n-m+1) = n! / (n-m)!

If m>n, no injective functions exist, this is a form of the pigeonhole principle. This topic will be further explored in Chapter 6 on combinatorics.

API Design Checks

When you see UserId→Email, first ask:

• Does every user have an email, or is the relationship more function-like?
• Can multiple users share the same email? Is it injective?
• Is the codomain all valid email strings, or only verified addresses?
• How do case sensitivity and Unicode normalization affect equality?
• How do query failures, timeouts, and permission denials enter the result type?
• If the mapping changes over time, does the function still need a time parameter?

Mathematical notation can expose missing assumptions, but real systems often require context and side effects to be incorporated into the model.

Completion Check

Determine whether each of the following functions is injective, surjective, or bijective, and specify its domain, codomain, and range:

1. f:ℤ→ℤ, f(n)=2n;
2. g:ℝ→[0,∞), g(x)=x²;
3. h:[0,∞)→[0,∞), h(x)=x²;
4. k:ℤ→{0,1,2}, k(n)=n mod 3.

Then refactor a potentially failing configuration parsing function to return a total result type, and identify which external failures remain outside the model's coverage.

References

• MIT Mathematics for Computer Science