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

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.

The notation f⁻¹(S) also denotes the preimage {a∈A:f(a)∈S} of a subset S⊆B. Every function has such preimages; this notation does not establish the existence of an inverse function.

Function Composition

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

Composition 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 Totalization

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 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.

A computer cannot represent every real number exactly. This Python 3.10+ example instead uses standard-library Fraction, with a domain of rational values represented by that type. None means zero has no reciprocal; callers must still supply the declared input type:

from fractions import Fraction

def safe_reciprocal(x: Fraction) -> Fraction | None:
    return None if x == 0 else 1 / x

print(safe_reciprocal(Fraction(3)))  # 1/3
print(safe_reciprocal(Fraction(0)))  # None

Every input has a result in this mathematical model. Type annotations do not enforce runtime validation, and resource failures such as memory exhaustion are not converted to None.

Accurate Analogy for Database Unique Keys

If each row is mapped to a unique key and all rows have non-null 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, SQL unique-constraint handling of NULL varies 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

A fixed-key block cipher is a permutation of a fixed-length block space, with encryption and decryption as inverses. For example, the AES standard specifies 128-bit data blocks; key length is a separate quantity. Authenticated encryption also takes parameters such as a nonce and associated data and produces a tag. Omitting randomness or a nonce can make “plaintext → ciphertext” fail to describe a single-valued map.

The block-cipher bijection does not automatically extend to every encryption API. Even with fixed parameters, a space of authenticated ciphertexts contains invalid strings that decryption should reject; recovery is required on valid encryption outputs. Bijection alone does not prove confidentiality: the identity function is bijective.

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 B.

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.

An empty domain has exactly one function, the empty function; for m=n=0, this counting convention is 0^0=1. A nonempty domain admits no function to an empty codomain. This enumerates small finite functions as output tuples for inputs 0,...,m−1:

from itertools import product

def count_functions(m, n):
    images = list(product(range(n), repeat=m))
    injective = sum(len(set(image)) == m for image in images)
    return len(images), injective

print(count_functions(2, 3))  # (9, 6)
print(count_functions(0, 0))  # (1, 1): the empty function.
print(count_functions(1, 0))  # (0, 0)

The enumeration stores n^m tuples and is suitable only for small examples. Counting the function set does not require materializing it.

API Design Checks

When you see UserId→Email, first ask:

• Does every user have an email, or is this a partial function?
• 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 image:

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