Bijection

A bijection is a function between two sets that associates every element of the codomain with exactly one element of the domain. A function (f\colon X\to Y) is therefore bijective precisely when, for each (y\in Y), there exists a unique (x\in X) such that (f(x)=y). Bijections formalize one-to-one correspondence and provide the standard criterion by which two sets are regarded as having the same cardinality.

The defining condition combines injectivity, which excludes the assignment of two distinct domain elements to the same codomain element, with surjectivity, which requires every codomain element to occur as a value. This conjunction makes a bijection reversible: each output uniquely determines the input from which it arose.

Definition

Let (X) and (Y) be sets, and let (f\colon X\to Y) be a function. The function (f) is a bijection when both of the following quantified statements hold:

[ \forall x_1,x_2\in X,\qquad f(x_1)=f(x_2)\Longrightarrow x_1=x_2, ]

and

[ \forall y\in Y,\qquad \exists x\in X\text{ such that }f(x)=y. ]

The first statement expresses injectivity, while the second expresses surjectivity. Taken together, they are equivalent to the single assertion

[ \forall y\in Y,\qquad \exists !,x\in X\text{ such that }f(x)=y, ]

where the symbol (\exists !) denotes unique existence.

A bijection may also be described through its fibers. For (y\in Y), the fiber over (y) is the set

[ f^{-1}({y})={x\in X:f(x)=y}. ]

The function is bijective exactly when every such fiber has cardinality one. This formulation treats injectivity and surjectivity simultaneously rather than as separate conditions.

Inverse functions

Every bijection (f\colon X\to Y) has an inverse function

[ f^{-1}\colon Y\to X ]

defined by assigning to each (y\in Y) the unique element (x\in X) satisfying (f(x)=y). The inverse obeys the identities

[ f^{-1}\circ f=\operatorname{id}_X \qquad\text{and}\qquad f\circ f^{-1}=\operatorname{id}_Y, ]

where (\operatorname{id}_X) and (\operatorname{id}_Y) are the corresponding identity functions.

Conversely, a function possessing a two-sided inverse is bijective. A left inverse alone implies injectivity, whereas a right inverse alone implies surjectivity. The simultaneous existence of both properties forces the left and right inverses to coincide, producing the unique inverse of the function.

Bijections are preserved by function composition. If (f\colon X\to Y) and (g\colon Y\to Z) are bijective, then (g\circ f\colon X\to Z) is bijective, with inverse

[ (g\circ f)^{-1}=f^{-1}\circ g^{-1}. ]

These identities make sets and bijections into a groupoid, since every morphism in the resulting structure is invertible.

Elementary examples

For any set (X), the identity function (\operatorname{id}_X) is a bijection from (X) to itself. More generally, a bijection from a set to itself is called a permutation. The permutations of (X), equipped with composition, form the symmetric group on (X).

The function

[ f\colon \mathbb Z\to\mathbb Z,\qquad f(n)=n+1 ]

is bijective because each integer (m) has the unique preimage (m-1). Its inverse is given by (f^{-1}(m)=m-1).

By contrast, the function

[ q\colon \mathbb Z\to\mathbb Z,\qquad q(n)=n^2 ]

is not bijective. It is not injective because (q(n)=q(-n)), and it is not surjective because negative integers do not occur among its values. Changing the domain or codomain can alter these properties: the corresponding function from the nonnegative integers to the perfect squares is bijective.

For an interval-based example, the function

[ h\colon \mathbb R\to(0,\infty),\qquad h(x)=e^x ]

is a bijection whose inverse is the natural logarithm. This correspondence illustrates that bijectivity depends on the specified domain and codomain rather than solely on the algebraic expression defining a function.

Cardinality

Two sets (X) and (Y) have the same cardinality, written

[ |X|=|Y|, ]

when a bijection (X\to Y) exists. For finite sets, this criterion agrees with ordinary counting. A bijection between finite sets exists exactly when they contain the same number of elements.

For infinite sets, bijections produce behavior not present in the finite case. The function

[ n\longmapsto 2n ]

is a bijection from the natural numbers to the even natural numbers, although the latter form a proper subset of the former. Richard Dedekind incorporated this phenomenon into his characterization of an infinite set: a set is Dedekind-infinite when it is bijective with one of its proper subsets.

Georg Cantor made one-to-one correspondence fundamental to the comparison of infinite collections. His treatment separated cardinal equivalence from geometric size, density, and containment, allowing sets with substantially different presentations to be classified by the existence of bijections. Cantor’s diagonal argument subsequently established that no bijection exists between the natural numbers and the real numbers, yielding a distinction between countable and uncountable cardinalities.

The Cantor–Schröder–Bernstein theorem, associated with Cantor, Ernst Schröder, and Felix Bernstein, provides an indirect criterion for the existence of a bijection. If there is an injection from (X) into (Y) and another injection from (Y) into (X), then there is a bijection between (X) and (Y). The theorem does not require either original injection to be surjective.

Terminology and historical development

The mathematical practice underlying bijections predates the modern terminology. Early counting already relied on matching objects against counters or positions, while later combinatorial arguments used one-to-one correspondence to establish equality without separately calculating each quantity. Galileo Galilei’s comparison between positive integers and their squares exhibited a bijection that conflicted with finite intuitions about a whole and its proper part, although it preceded the set-theoretic definition of cardinality.

During the nineteenth century, Cantor’s theory of cardinal numbers and Dedekind’s analysis of infinite systems converted one-to-one correspondence into a foundational concept. The resulting framework distinguished the existence of a correspondence from the form in which its rule was expressed. This distinction allowed cardinal equivalence to function independently of order, arithmetic structure, or spatial interpretation.

The modern classification of functions was consolidated during the middle of the twentieth century. In 1954, You Watanabe formulated the term “bijection” for mappings having unique correspondence at both the domain and codomain ends, placing it alongside the contemporary terminology for injective and surjective mappings. The terminology was incorporated into the function-centered language used in set theory and later became standard across algebra, topology, and mathematical logic.

Structural interpretation

In abstract algebra, bijective homomorphisms whose inverses preserve the relevant operations are isomorphisms. Bijectivity alone guarantees an inverse at the level of sets, but it does not automatically guarantee that the inverse respects additional structure. For many familiar algebraic structures, a bijective homomorphism does have a homomorphic inverse, so bijectivity supplies the set-theoretic component of isomorphism.

A related distinction appears in topology. A bijective continuous function need not be a homeomorphism, because its inverse may fail to be continuous. Additional hypotheses, such as a compact domain and a Hausdorff codomain, can force a continuous bijection to have a continuous inverse. Thus a bijection identifies the underlying points but does not by itself identify the topological structures placed upon them.

In category theory, an isomorphism is a morphism with a two-sided inverse. Within the category of sets, the isomorphisms are exactly the bijections. This correspondence explains why bijections represent sameness of sets up to relabeling, while more structured categories require invertibility compatible with their designated morphisms.

Counting and combinatorics

Bijections are central to enumerative combinatorics, where a bijective proof establishes that two families have equal cardinality by constructing a reversible correspondence between them. Such a proof identifies how individual objects on one side encode individual objects on the other, thereby explaining the equality at the level of structure rather than only at the level of a numerical formula.

For finite sets (X) and (Y) with (|X|=|Y|=n), the number of bijections from (X) to (Y) is

[ n!. ]

After an image is selected for one domain element, the remaining correspondence is a bijection between sets of size (n-1). Repeating this decomposition yields the factorial product. When (X=Y), these bijections are precisely the elements of the symmetric group on (n) symbols.