Bijection

In mathematics, injections, surjections and bijections are classes of functions distinguished by the manner in which arguments (input expressions) and images (output expressions) are related.

• A function is an injection ("one-to-one") if it maps at most one argument to every possible image or equivalently if it maps distinct arguments to distinct images.
• A function is a surjection ("onto") if it maps at least one argument to every possible image.
• A function is a bijection if it maps exactly one argument to every possible image or equivalently if it is both an injection and a surjection.

The four possible combinations of injective and surjective features are illustrated in the following diagrams.

Injective and surjective (bijective).	Injective and non-surjective.
Non-injective and surjective.	Non-injective and non-surjective.

Injection

Injective composition: the second function doesn't need to be injective.

An injection, injective function or one-to-one function is a function which maps at most one argument to every possible image or equivalently if it 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 y then also f(x) 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 as can be seen in the image on the right.

Surjection

Surjective composition: the first function doesn't need to be surjective.

A surjection, surjective function or onto function is a function which maps at least one argument to every possible image. 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

Bijective composition: the first function doesn't need to be surjective and the second function doesn't need to be injective.

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 B, 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 .
• and thus also its inverse
• The exponential function and thus also its inverse the natural logarithm

Injective and non-surjective

• The exponential function

Non-injective and surjective

Non-injective and non-surjective

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, surjections, and bijections correspond precisely to monomorphisms, epimorphisms, and isomorphisms, respectively.

See also

• injective module
• permutation
• horizontal line test