Bijection

A bijection (or bijective function) is a mathematical function that is both injective ("one-to-one") and surjective ("onto"), and therefore bijections are also called one-to-one and onto.

In simple terms, a bijective function creates a one-to-one correspondence between its possible input values and possible output values. (In some references, the phrase "one-to-one" is used alone to mean bijective. Wikipedia does not follow this older usage.)

More formally, a function f: X → Y is bijective if for every y in the codomain Y there is exactly one x in the domain X with f(x) = y.

Surjective, not injective	Injective, not surjective
Bijective	Not surjective, not injective

When X and Y are both the real line R, then a bijective function f: R → R can be visualized as one whose graph is intersected exactly once by any horizontal line.

If X and Y are finite sets, then there exists a bijection between the two sets X and Y if and only if X and Y have the same number of elements. Generalising this to infinite sets leads to the concept of cardinal number, a way to distinguish the various infinite sizes of infinite sets.

Examples and counterexamples

Consider the function f: R → R defined by f(x) = 2x + 1. This function is bijective, since given an arbitrary real number y, we can solve y = 2x + 1 to get exactly one real solution x = (y − 1)/2.

On the other hand, the function g: R → R defined by g(x) = x² is not bijective, for two essentially different reasons. First, we have (for example) g(1) = 1 = g(−1), so that g is not injective; also, there is (for example) no real number x such that x² = −1, so that g is not surjective either. Either one of these facts is enough to show that g is not bijective.

However, if we define the function h: R⁺ → R⁺ by the same formula as g, but with the domain and codomain both restricted to only the nonnegative real numbers, then the function h is bijective. This is because, given an arbitrary nonnegative real number y, we can solve y = x² to get exactly one nonnegative real solution x = √y.

Properties

• A function f: X → Y is bijective if and only if there exists a function g: Y → X such that g ^o f is the identity function on X and f ^o g is the identity function on Y. (In fancy language, bijections are precisely the isomorphisms in the category of sets.) In this case, g is uniquely determined by f and we call g the inverse function of f and write f ⁻¹ = g. Furthermore, g is also a bijection, and the inverse of g is f again.
• If f ^o g is bijective, then f is surjective and g is injective.
• If f and g are both bijective, then f ^o g is also bijective.
• If X is a set, then the bijective functions from X to itself, together with the operation of functional composition (^o), form a group, the symmetric group of X, which is denoted variously by S(X), S_X, or X! (the last read "X factorial").

See also: Injective function, Surjection