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.