Bijective function (bijection)

Definition and basic properties

Formally, a function f: A → B is bijective if it is both injective (no two distinct elements of A share the same image) and surjective (every element of B is the image of some element of A). Equivalently, for every b in the codomain B there exists exactly one a in the domain A with f(a) = b. A direct consequence is that a bijection has a unique inverse function f^{-1}: B → A that reverses the pairing.

Key characteristics

• Invertibility: Bijectivity is exactly the condition needed for a map to have an inverse that is also a function.
• Compositional behavior: The composition of two bijections is a bijection; the inverse of a composition is the composition of the inverses in reverse order.
• Cardinality: Existence of a bijection between sets A and B is the definition of A and B having the same cardinality.

Examples and applications

Simple finite examples include pairings between two finite lists of equal length or permutations of a finite set. In more advanced settings, bijections are used to prove combinatorial identities by pairing objects, to define isomorphisms between algebraic structures, and to demonstrate that two infinite sets have the same size (for example, the integers and even integers). In algorithms and cryptography, bijective transformations are important because they are reversible without loss of information.

History and context

The modern terminology distinguishing injection, surjection and bijection was popularized in the 20th century; the consolidated presentation appears in the structural approach associated with groups of mathematicians who wrote under the collective name Nicolas Bourbaki. The use of bijections as a tool to compare sizes of sets dates back to Georg Cantor and the development of set theory, where bijections are the standard means to classify infinite cardinalities. For further reading and technical background see mathematical context.

Notable facts and distinctions

For finite sets, a function is bijective exactly when the two sets have equal finite size. For infinite sets, bijections can produce surprising equivalences: an infinite set can be in bijection with a proper subset of itself. The Cantor–Bernstein–Schroeder theorem shows that if there are injections both ways between two sets, then a bijection exists between them. These properties make bijections a powerful and flexible concept across mathematics.

Readers interested in formal proofs and further examples can follow introductory material on injections and surjections or explore bijection-based proofs in combinatorics; additional resources are available at domain and codomain notes and related references injection overview and surjection overview.