Bijection, injection and surjection

In mathematics, an injection, surjection or bijection is a certain type of function. An injection maps distinct arguments to distinct images, a surjection maps to all possible images and a bijection is simply a function that is both an injection and a surjection. The four possible combinations of injective and surjective are illustrated in the following pictures.

Injection

An injection, injective function or one-to-one function is a function which maps distinct arguments to distinct images. More formally a function f : A → B is injective if, for every x and y in its domain A, if x<math>\ne<math> y then also f(x) <math>\ne<math> f(y). Thus at most one argument is mapped to any possible image. Since trivially every function is surjective when its codomain is restricted to its range, every injection is actually a bijection to its range and thus there exists an inverse from its range to its domain. The composition of two injections is again an injection, but if the composition of two functions is an injection, then it can only be concluded that the first applied is injective, since its entire image must be included in the domain of the second, which may be non-injective on a part of its domain which is not in the range of the first.

Surjection

A surjection, surjective function or onto function is a function which maps to all possible images. More formally a function f : A → B is surjective if, for every y in its codomain B, there exists an x in its domain A such that f(x)=y. Put another way, a function is surjective if its range is equal to its codomain, or equivalently, if every element in the codomain has non-empty preimage. Thus at least one argument is mapped to any possible image. The composition of two surjections is again a surjection, but if the composition of two functions is a surjection, then it can only be concluded that the second applied is surjective.

Bijection

A bijection or bijective function is per definition a function that is both injective (one-to-one) and surjective (onto). A bijection associates each possible image with exactly one argument. More formally, a function f: A → B is bijective if for every y in its codomain Y, there exists exactly one x in its domain A such that f(x) = y. We can use this property to define a new function which maps each image to its unique preimage. This function is the (two-sided) inverse. The composition of two bijections is again a bijection, but if the composition of two functions is a bijection, then it can only be concluded that the first applied is injective and that the second applied is surjective. The bijections from a set to itself form a group under composition, called the symmetric group.

Cardinal numbers

Suppose you want to define what it means for two sets to have the same number of elements. Surely if you can pair off each element of the first set with an element of the second set, then they must have the same number of elements. Accordingly, for two sets to have the same number of elements is defined to mean that there exists a bijection between them. The equivalence classes of this equivalence relation are called cardinal numbers.

Examples

It is important to specify the domain and codomain of each function since by changing these, functions which we think of as the same may have different jectivity.

Injective and surjective (bijective)

• For every set A the identity function id_A and thus specifically <math>\mathbf{R} \to \mathbf{R} : x \mapsto x<math>.
• <math>\mathbf{R}^+ \to \mathbf{R}^+ : x \mapsto x^2<math> and thus also its inverse <math>\mathbf{R}^+ \to \mathbf{R}^+ : x \mapsto \sqrt{x}<math>
• The exponential function <math>\exp : \mathbf{R} \to \mathbf{R}^+ : x \mapsto \mathrm{e}^x<math> and thus also its inverse the natural logarithm <math>\ln : \mathbf{R}^+ \to \mathbf{R}^+ : x \mapsto \ln{x}<math>

Injective and non-surjective

• The exponential function <math>\exp : \mathbf{R} \to \mathbf{R} : x \mapsto \mathrm{e}^x<math>

Non-injective and surjective

• <math>\mathbf{R} \to \mathbf{R} : x \mapsto (x-1)x(x+1) = x^3 – x <math>

Non-injective and non-surjective

• <math>\mathbf{R} \to \mathbf{R} : x \mapsto x^2<math>

Properties

• For every function f, subset A of the domain and subset B of the codomain we have A ⊂ f ⁻¹(fA) and f(f ⁻¹B) ⊂ B. If f is injective we have A = f ⁻¹(fA) and if f is surjective we have f(f ⁻¹B) = B.
• For every function h : A → C we can define a surjection H : A → h(A) : a → h(a) and an injection I : h(A) → C : a → a. It follows that h = I o H. This decomposition is unique up to isomorphism.

Category theory

In the category of sets, injections and surjections correspond precisely to monomorphisms and epimorphisms respectively. It then follows that bijections correspond to isomorphisms.

See also

• injective module
• permutation
• horizontal line test