In discrete mathematics a function is not a formula but a rule that assigns to each element of one set exactly one element of another. This more general view lets us reason about encodings, tables, identifiers and hash functions in the same language. The three properties of injectivity, surjectivity and bijectivity answer very practical questions: is information lost? are all values covered? can we go back?
Definition
A function f: A → B assigns to each element a of A one and only one element f(a) of B.
- A is the domain.
- B is the codomain.
- The image is the set of values actually reached: f(A) = {f(a) | a ∈ A}, a subset of B.
Formally, f is a relation between A and B in which every element of A appears as the first element of exactly one pair. Two conditions: no element of the domain is left without a value, and none has two.
Example: the function that assigns each user their department is a function (each user has one department); the one that assigns each department one of its employees is not, because a department has many employees and some may be empty.
Injective
f is injective if different elements have different images: if a ≠ a′ then f(a) ≠ f(a′). Equivalently: if f(a) = f(a′) then a = a′.
An injective function loses no information: from the value you can recover the starting element. Examples:
- f(n) = 2n on the integers is injective.
- f(n) = n² on the integers is not: f(3) = f(−3) = 9.
- The Italian tax code, as a function from people to strings, is designed to be injective; the so-called omocodie, handled by substituting some characters, are precisely the cases where the basic rule would not be.
A primary key in a database is, by definition, an attribute that makes the function from rows to key values injective.
Surjective
f is surjective if every element of the codomain is reached: for every b ∈ B there is at least one a with f(a) = b. In other words the image equals the codomain.
- f(n) = n mod 7, from the integers to {0, 1, …, 6}, is surjective.
- f(n) = 2n from the integers to the integers is not: odd numbers are never reached.
Surjectivity depends on the chosen codomain. f(n) = 2n is surjective if you regard it as a function from the integers to the even numbers.
Bijective
f is bijective if it is both injective and surjective: every element of the codomain is reached by exactly one element of the domain. Bijections are the functions that can be inverted: there is f⁻¹: B → A with f⁻¹(f(a)) = a and f(f⁻¹(b)) = b.
Examples of bijections in computing:
- conversion between a number and its hexadecimal representation;
- Base64 encoding between byte sequences and valid Base64 strings;
- a block cipher with a fixed key, which must be bijective on blocks, otherwise decryption would be impossible.
The link with cardinality
For finite sets, the three properties impose constraints on size:
| If f: A → B is… | then |
|---|---|
| injective | |A| ≤ |B| |
| surjective | |A| ≥ |B| |
| bijective | |A| = |B| |
The first row, read backwards, is the pigeonhole principle: if |A| > |B|, no function from A to B can be injective. That is why a hash function, which maps inputs of arbitrary length to an output of fixed length, necessarily has collisions. A good cryptographic hash function does not avoid them: it only makes them extremely hard to find.
Another useful consequence: if |A| = |B| and both are finite, injective and surjective are equivalent. Checking one is enough to get a bijection. This does not hold for infinite sets, as f(n) = 2n shows.
Composition
Given f: A → B and g: B → C, the composition g ∘ f: A → C is defined by (g ∘ f)(a) = g(f(a)). The properties are preserved:
- a composition of injective functions is injective;
- a composition of surjective functions is surjective;
- a composition of bijections is a bijection, and (g ∘ f)⁻¹ = f⁻¹ ∘ g⁻¹.
The reversed order in the formula makes practical sense: to undo "first compress, then encrypt" you must first decrypt and then decompress.
A check in Python
For functions on finite domains, represented as dictionaries, the properties can be checked in one line:
def injective(f):
return len(set(f.values())) == len(f)
def surjective(f, codomain):
return set(f.values()) == set(codomain)
In short
- A function assigns to each element of the domain exactly one element of the codomain.
- Injective: no collisions, no loss of information; surjective: the whole codomain is covered.
- Bijective means invertible, like encodings and ciphers.
- If the domain is larger than the codomain there can be no injectivity: hence hash collisions.
- The inverse of a composition is obtained by undoing the steps in reverse order.
