Injective, surjective and bijective functions

Three important kinds of mathematical functions deserve special names: a function f : X -> Y is called

• a surjection (or surjective, or onto) if for every y in Y there is at least one x in X such that f(x) = y
• an injection (or injective, or one-to-one) if for every y in Y there is at most one x in X such that f(x) = y
• a bijection (or bijective, or one-to-one and onto) if it is both a surjection and an injection, i.e., if for every y in Y there is precisely one x in X such that f(x) = y.

Motivation

These kinds of functions are generally useful for showing the relationships between different kinds of mathematical objects. Often, an injective relationship will correspond to a subset-like relationship, and the existence of a bijection will demonstrate an equality-like relationship.

For instance, a homomorphism θ is a relationship between two algebraic objects (that is sets with some kind of multiplication defined for the purposes of this example) which preserves multiplication; that is θ(x) * θ(y) = θ(x * y) for all x and y. If a homomorphism is also a bijection then the two algebraic objects are described as isomorphic; they are so closely equivalent that consideration of the algebraic properties of one is equivalent to consideration of the algebraic properties of the other; in writing a proof about one you may as well be writing a proof about the other. Therefore a convenient proof technique to show the existence of some property in object A is to demonstrate a bijection between A and some other object B, and realize that someone else has already proven this property for object B.

Examples

• The function abs from Z (the set of Integers) to Z defined by abs(x) = | x | where | x | is the absolute value of x, is neither injective nor surjective. Since there exists an integer -5 in Z such that there is no integer i in Z with abs(i) = -5, abs is not surjective. Since abs(5) = abs(-5), abs is not injective.
• Consider the function abs* from Z to N (the set of non-negative integers) that is defined by the same rule as abs. Then abs* is onto, or a surjection, since for every y in N, that is, every non-negative integer, there is at least one x in Z such that abs*(x) = y.
• Consider the function add1 from Z to Z that is specified by the rule add1(x) = x + 1. The function add1 is one-to-one and onto or a bijection, since for every y in Z there is one and only one x in Z such that add1(x) = y (namely x = y - 1).

Propositions

• A function is bijective if and only if it is injective and surjective.
• If fog is injective, then g is injective.
• If fog is surjective, then f is surjective.
• If f and g are both injective, then fog is injective.
• If f and g are both surjective, then fog is surjective.
• If hof = hog and h is injective, then f = g.
• If foh = goh and h is surjective, then f = g.
• If f is injective, then f ^-1(f(A)) = A for any subset A of the domain of f.
• If f is surjective, then f(f ^-1(B)) = B for any subset B of the codomain of f.
• Every function h can be written as h = fog with a suitable surjection g and an injection f.
• A function f : X -> Y is bijective if and only if there exists a function g : Y -> X such that gof is the identity on X and fog is the identity on Y. In this case, g is uniquely determined by f and we call g the inverse function of f and write f ^-1 = g.
• The bijective functions X -> X, together with functional composition, form a mathematical group, the symmetric group of X denoted by S(X).