Fact-checked by Grok 2 weeks ago

Bijection

In mathematics, particularly in set theory and function theory, a bijection is a function between two sets that is both injective (one-to-one, meaning distinct elements in the domain map to distinct elements in the codomain) and surjective (onto, meaning every element in the codomain is mapped to by at least one element in the domain), thereby establishing a perfect one-to-one correspondence between the elements of the two sets.^[1] Bijections play a fundamental role in determining the cardinality of sets, where two sets are considered to have the same size or cardinality if and only if there exists a bijection between them, allowing for the comparison of infinite sets as well, such as the natural numbers and the integers.^[2] This property underpins the concept of set equivalence in naive set theory and Zermelo-Fraenkel set theory, enabling proofs of results like the uncountability of the real numbers via diagonalization, which shows no bijection exists between the reals and the naturals. Furthermore, every bijection is invertible, with its inverse function also being a bijection, which facilitates symmetry in mappings and is essential in areas like group theory for isomorphisms between structures.^[3]^[4] Examples of bijections include the identity function on a set, which maps each element to itself, and linear functions like f(x) = x + c over the real numbers, both of which preserve the one-to-one correspondence.^[5] In combinatorics, bijections are often used in bijective proofs to establish equalities between counting quantities by directly pairing elements, avoiding summation or induction.^[6] These mappings are not only theoretical but also appear in practical contexts, such as encoding schemes in computer science where data structures require reversible transformations.^[7]

Fundamentals

Definition

In mathematics, a set is a well-defined collection of distinct objects, often denoted by capital letters such as A or B. A function f: A \to B is a mapping that assigns to each element a in the domain set A exactly one element f(a) in the codomain set B.^[8] A function f: A \to B is a bijection if for every element b in B, there exists exactly one element a in A such that f(a) = b. This establishes a one-to-one correspondence between the elements of A and B.^[9] Equivalently, a bijection is a function that is both injective (one-to-one), meaning f(a_1) = f(a_2) implies a_1 = a_2 for all a_1, a_2 \in A, and surjective (onto), meaning for every b \in B, there exists at least one a \in A such that f(a) = b. As a consequence, every bijection has an inverse function.^[3]^[1] Bijections are often denoted using a standard function arrow f: A \to B qualified as bijective, or symbolically with a double-headed arrow A \leftrightarrow B to indicate the existence of such a correspondence, which preserves the structure of the sets in terms of their elements.^[9]^[10]^[11]

Examples

A bijection can be illustrated through simple everyday scenarios where there is a perfect one-to-one matching between two collections without any omissions or duplicates. For instance, consider the batting line-up of a baseball team, where each of the nine players is uniquely assigned to one specific position in the order, and every position is filled by exactly one player.^[4] Similarly, in a classroom, the assignment of seats to students establishes a bijection if each seat is occupied by precisely one student and every student has a unique seat, ensuring no empty seats or shared assignments.^[4] In mathematics, bijections appear in fundamental constructions on sets. The identity function on any set X, defined by f(x) = x for all x \in X, maps each element to itself and is thus both injective and surjective, making it a bijection.^[4] For finite sets, any permutation rearranges the elements such that each is mapped uniquely to another, preserving the set's structure; for example, swapping two elements in a set of three items like \{a, b, c\} to \{b, a, c\} via a specific mapping yields a bijection.^[4] Another classic example is the function f: \mathbb{N} \to 2\mathbb{N} given by f(n) = 2n, where \mathbb{N} is the set of natural numbers and $2\mathbb{N} is the set of even natural numbers, pairing each natural number with a unique even number and covering all even numbers exactly once.^[4]^[12] To visualize a bijection, imagine two finite sets represented as rows of dots, such as five dots for students and five dots for seats; lines connecting each student dot to a unique seat dot without overlaps or loose ends demonstrate the matching, where arrows can indicate the direction of the function while ensuring every dot on both sides is connected precisely once. For the natural numbers to even numbers bijection, a diagram might show a sequence of pairs like 1 to 2, 2 to 4, 3 to 6, extending infinitely to the right, illustrating the exhaustive pairing without gaps.

Structural Properties

Inverses

A bijection f: A \to B possesses a unique inverse function f^{-1}: B \to A that satisfies the conditions f^{-1}(f(a)) = a for all a \in A and f(f^{-1}(b)) = b for all b \in B.^[13] This existence and uniqueness follow directly from the bijectivity of f, as injectivity ensures that no two elements in A map to the same element in B, while surjectivity guarantees that every element in B is reached exactly once.^[14] The inverse function is constructed by defining f^{-1}(b) to be the unique element a \in A such that f(a) = b, for each b \in B.^[14] This definition is well-founded because surjectivity provides the existence of at least one such a, and injectivity ensures its uniqueness, thereby establishing f^{-1} as a total function from B to A.^[15] The inverse f^{-1} is itself bijective, as applying the same reasoning shows that f serves as its inverse, satisfying the round-trip identity conditions.^[13] Consequently, the compositions f \circ f^{-1} and f^{-1} \circ f both equal the respective identity functions \mathrm{id}_B: B \to B and \mathrm{id}_A: A \to A, where \mathrm{id}_X(x) = x for all x \in X.^[16] This uniqueness of the inverse implies that no other function can serve in this role for f.^[17]

Composition

The composition of two functions f: A \to B and g: B \to C is the function g \circ f: A \to C defined by (g \circ f)(a) = g(f(a)) for all a \in A.^[18] If f and g are bijections, then their composition g \circ f is also a bijection. To see this, first consider injectivity: suppose (g \circ f)(a_1) = (g \circ f)(a_2) for a_1, a_2 \in A. Then g(f(a_1)) = g(f(a_2)). Since g is injective, it follows that f(a_1) = f(a_2), and since f is injective, a_1 = a_2. Thus, g \circ f is injective. For surjectivity, let c \in C. Since g is bijective, there exists b \in B such that g(b) = c, namely b = g^{-1}(c). Since f is bijective, there exists a \in A such that f(a) = b, namely a = f^{-1}(b). Then (g \circ f)(a) = g(f(a)) = g(b) = c, so g \circ f is surjective.^[3]^[19] The composition of bijections is associative: for bijections f: A \to B, g: B \to C, and h: C \to D, we have (h \circ g) \circ f = h \circ (g \circ f). This follows from the general associativity of function composition, where ((h \circ g) \circ f)(a) = h(g(f(a))) and (h \circ (g \circ f))(a) = h((g \circ f)(a)) = h(g(f(a))) for all a \in A.^[18] For a finite set S with n elements, the set of all bijections from S to itself, equipped with composition as the group operation, forms the symmetric group S_n, which contains exactly n! elements and is generated by compositions of its members.^[20]

Additional Properties

In the context of ordered sets, a bijection that additionally preserves the order relation—such that if x \leq y in the domain, then f(x) \leq f(y) in the codomain—is termed an order isomorphism.^[21] For sets endowed with algebraic structures, such as groups or vector spaces, a bijection that preserves the relevant operations (e.g., f(a + b) = f(a) + f(b) for addition in vector spaces) qualifies as an isomorphism, maintaining the operational integrity of the structure.^[22] However, arbitrary bijections between unstructured sets do not inherently preserve order or algebraic properties. In infinite sets, bijections to itself similarly provide one-to-one correspondences that extend the permutation concept, though the symmetric group may involve additional considerations like choice axioms for explicit construction.^[23] Bijections possess strong cancellation properties under function composition. If f: A \to B is a bijection and g, h: C \to A satisfy f \circ g = f \circ h, then g = h (left cancellation law). Analogously, for r, s: B \to D, if r \circ f = s \circ f, then r = s (right cancellation law). These properties stem from the invertibility of bijections, allowing the "cancellation" of f by composing with its inverse.^[24] Particular bijections, especially permutations of finite sets, may lack fixed points, where no element maps to itself (f(x) \neq x for all x). Such mappings are derangements, which are bijections with no fixed points and play a key role in combinatorics for counting rearrangements without stabilizers. While derangements are typically discussed for finite permutations, the absence of fixed points can analogously characterize certain infinite bijections.^[25]

Theoretical Contexts

Cardinality

In set theory, two sets A and B have the same cardinality, denoted |A| = |B|, if and only if there exists a bijection f: A \to B, establishing a one-to-one correspondence between their elements. This definition extends the intuitive notion of size equality from finite collections to arbitrary sets, allowing precise comparisons even when direct enumeration is impossible. For finite sets, a bijection directly implies equal sizes, as the correspondence pairs each element uniquely without leftovers. For example, the sets \{1, 2, 3\} and \{a, b, c\} satisfy |\{1, 2, 3\}| = |\{a, b, c\}| = 3 via the bijection f(1) = a, f(2) = b, f(3) = c. In contrast, infinite cardinalities exhibit counterintuitive behaviors, where proper subsets can match the original set's size through bijections. Consider the natural numbers \mathbb{N} = \{1, 2, 3, \dots\} and \mathbb{N} \cup \{0\} = \{0, 1, 2, 3, \dots\}; the function f: \mathbb{N} \to \mathbb{N} \cup \{0\} defined by f(1) = 0 and f(n) = n - 1 for n > 1 is a bijection, so |\mathbb{N}| = |\mathbb{N} \cup \{0\}|.^[26] This equivalence illustrates how infinite sets can "absorb" additional elements without increasing cardinality, as popularized by Hilbert's hotel paradox: a fully occupied infinite hotel accommodates a new guest by shifting occupant n to room n+1, freeing room 1—a bijection between the original and expanded guest sets.^[27] Bijections also play a key role in distinguishing infinite cardinalities, such as in Cantor's diagonal argument, which proves the uncountability of the real numbers by assuming a bijection f: \mathbb{N} \to (0,1) exists and constructing a real number in (0,1) not in the image, yielding a contradiction; thus, no such bijection exists, and |\mathbb{R}| > |\mathbb{N}|. The Schröder–Bernstein theorem further refines cardinality comparisons: if there exist injections g: A \to B and h: B \to A, then a bijection A \to B exists. One proof constructs the bijection by iteratively defining nested subsets A_0 = A, B_0 = B, A_{n+1} = h(B_n), B_{n+1} = g(A_n), forming decreasing chains, and partitioning into differences where bijections are defined via g and h^{-1} on appropriate components, with the intersection handled separately to ensure surjectivity and injectivity.^[28]

Category Theory

In category theory, the concept of a bijection from set theory generalizes to the notion of an isomorphism, which captures invertible morphisms between objects in any category. In the category of sets, denoted Set, where objects are sets and morphisms are functions, a morphism f: A \to B is an isomorphism if and only if it is a bijection, meaning it is both injective and surjective, and possesses an inverse morphism g: B \to A such that g \circ f = \mathrm{id}_A and f \circ g = \mathrm{id}_B.^[29] This equivalence holds because the identity morphisms in Set are bijections, and the composition of bijections preserves this property, ensuring two-sided invertibility.^[30] More broadly, in an arbitrary category \mathcal{C}, an isomorphism is defined as a morphism f: X \to Y that admits an inverse morphism g: Y \to X satisfying the same composition conditions with the identity morphisms on X and Y. Thus, bijections in Set exemplify isomorphisms, but the categorical definition extends the idea of two-sided inverses to structured settings beyond mere sets, emphasizing equivalence of objects up to invertible arrows rather than strict equality.^[30] This abstraction allows category theory to unify diverse mathematical domains by focusing on relational properties preserved under inversion.^[31] In other categories, isomorphisms take forms tailored to the structure of the objects and morphisms. For instance, in the category Vect of vector spaces over a field (with linear maps as morphisms), an isomorphism is an invertible linear map, which is necessarily bijective on underlying sets but also preserves the vector space operations, such as scalar multiplication and addition.^[32] Similarly, in the category Top of topological spaces (with continuous functions as morphisms), an isomorphism is a homeomorphism: a continuous bijection with a continuous inverse, ensuring that the topological structure—open sets and continuity—is preserved bidirectionally.^[33] Automorphisms arise as a special case of isomorphisms, namely those from an object to itself, forming the automorphism group \mathrm{Aut}(X) under composition, which encodes the symmetries of X. In Set, these are precisely the bijections f: A \to A, with the symmetric group \mathrm{Sym}(A) as the automorphism group for finite sets A. This group structure highlights how isomorphisms generate algebraic insights into object equivalences within categories.^[30]

Generalizations

A partial bijection, also known as a partial isomorphism, is a partial function f: A \rightharpoonup B between sets A and B such that the restriction of f to its domain \operatorname{dom}(f) \subseteq A induces a bijection onto its image \operatorname{im}(f) \subseteq B.^[34] This means f is injective on \operatorname{dom}(f) and surjective onto \operatorname{im}(f), ensuring a one-to-one correspondence between these subsets. Partial bijections extend the concept of total bijections to scenarios where functions may be undefined on parts of the domain, preserving bijectivity where defined. They form a category under composition, where the composition of two partial bijections is defined only where domains overlap appropriately.^[34] In domain theory, partial bijections play a key role in modeling the semantics of recursive and computable functions within partially ordered sets (domains), where they represent embeddings and projections that maintain structural continuity.^[35] This framework, foundational to denotational semantics in programming languages, uses partial bijections to approximate infinite computations via finite approximations in Scott domains.^[35] Bijections also induce important relations on collections of sets. Specifically, the relation \sim on the class of all sets, defined by A \sim B if there exists a bijection between A and B, is an equivalence relation: it is reflexive (via the identity bijection), symmetric (via the inverse bijection), and transitive (via composition of bijections).^[36] This equivalence partitions the universe of sets into cardinality classes, where equivalent sets share the same "size" in the sense of Dedekind. Equivalence relations in general correspond bijectively to partitions of a set, with each relation defining a partition into equivalence classes and vice versa.^[36] In type theory and programming languages, bijections manifest as type isomorphisms, providing invertible mappings between types that preserve computational structure. For instance, in Haskell, a type isomorphism between types A and B consists of functions to: A \to B and from: B \to A such that to \circ from = id_B and from \circ to = id_A, enabling seamless conversion without information loss.^[37] Similarly, in Coq's dependently typed framework, isomorphisms are bijections equipped with proofs of invertibility, facilitating modular reasoning about data representations.^[38] The Curry-Howard correspondence further links these isomorphisms to logical equivalences, interpreting type equalities as provable bijections between proof terms.^[39] The concept of one-to-one correspondences, central to bijections, traces back to Gottlob Frege's late 19th-century work in Grundlagen der Arithmetik (1884), where he used them to logically define cardinal numbers as equivalence classes under such mappings, laying groundwork for modern set theory.^[40] In contemporary computer science, bijections underpin applications like database schema mappings, ensuring invertible transformations between relational structures to maintain data integrity during migrations.^[41]

References

[1]
Injective, surjective and bijective functions - SIUE
An injective function is one-to-one, a surjective function is onto, and a bijective function is both injective and surjective.
[2]
Cardinality
Cardinality is the number of elements in a set. Two sets have the same cardinality if there is a bijection between them.
[3]
4.6 Bijections and Inverse Functions
A function f:A→B is bijective (or f is a bijection) if each b∈B has exactly one preimage. Since "at least one'' + "at most one'' = "exactly one'', f is a ...
[4]
Functions:Bijective - Department of Mathematics at UTSA
Nov 11, 2021 · A bijective function pairs each element of one set with exactly one element of another, and is both one-to-one and onto.
[5]
[PDF] 2. Properties of Functions 2.1. Injections, Surjections, and Bijections ...
f is bijective if it is surjective and injective (one-to-one and onto). Discussion. We begin by discussing three very important properties functions defined ...<|control11|><|separator|>
[6]
[PDF] BIJECTIVE PROOF PROBLEMS
Aug 18, 2009 · The statements in each problem are to be proved combinatorially, in most cases by exhibiting an explicit bijection between two sets.Missing: theory | Show results with:theory
[7]
[PDF] INTRODUCTION TO BIJECTIONS Contents 1. Sets 1 2. Functions 2 ...
Bijections are functions f and g between sets A and B, where g(f(a)) = a and f(g(b)) = b, meaning g undoes f.
[8]
[PDF] Sets and Functions - UC Davis Math
An onto function is also called a surjection, a one-to-one function an injection, and a one-to-one, onto function a bijection. Example 1.14. The function f : A ...
[9]
Bijective -- from Wolfram MathWorld
A map is called bijective if it is both injective and surjective. A bijective map is also called a bijection. A function f admits an inverse f^(-1) ...
[10]
Bijection - an overview | ScienceDirect Topics
Let us remember the definition of bijection: A function f : X → Y is bijective if for every y ∈ Y, there is exactly one x ∈ X such that f(x) = y. A function is ...<|control11|><|separator|>
[11]
[PDF] A function is bijective if and only if has an inverse
Nov 30, 2015 · A function g : B → A is the inverse of f if f ◦ g = 1B and g ◦ f = 1A. Theorem 1. Let f : A → B be bijective. Then f has an inverse. Proof. Let ...
[12]
[PDF] Inverse of a Bijection
Hence, for each b ∈ B, there is exactly one a ∈ A such that f(a) = b. Since both existence and uniqueness hold, f-1 is well defined as a function B → A.
[13]
[PDF] Bijection and Cardinality - Introduction
The inverse function of f is the function that assigns to an element b ∈ B the unique element a ∈ A such that f(a) = b. The inverse function is denoted by .<|control11|><|separator|>
[14]
[PDF] Inverse Functions
Another important consequence of Theorem 1 is that if an inverse function for f exists, it is unique. Here is the proof. Theorem 4. Let A and B be nonempty sets ...
[15]
[PDF] Math 1365 (Intensive Mathematical Reasoning)
Inverses of Functions, X. We can also deduce that (when it exists) the inverse function is the unique two-sided inverse of f : Corollary (Uniqueness of Inverse).
[16]
7.3: Function Composition - Mathematics LibreTexts
Aug 16, 2021 · However, the associative law is true for functions under the operation of composition. Theorem 7 . 3 . 1 : Function Composition is Associative.
[17]
Proofs of relationships between inverses and 'jectivity
Claim: The composition of two bijections f and g is a bijection. Proof: Since f and g are both bijections, they are both surjections. By above, this implies ...
[18]
3.1: Symmetric Groups - Mathematics LibreTexts
Nov 20, 2024 · S n with compositions forms a group; this group is called a Symmetric group.
[19]
[TeX] Ordered Sets
An order-preserving bijection f:S. → T is called an order-isomorphism; in this case, the sets S and T are called order-isomorphic, denoted by S ≃ T.
[20]
[PDF] MATH 433 Applied Algebra Lecture 10: Permutations.
A permutation of a finite set X is a bijection from X to itself. The set of all permutations of X is called the symmetric group on X.
[21]
[PDF] 3.3. Composition of Functions
Feb 2, 2022 · Let f be a bijection. Then: f ◦ g = f ◦ h ⇒ g = h (left cancellation) r ◦ f = s ◦ f ⇒ r = s (right cancellation). Theorem 3.29. Let f ...
[22]
[PDF] Derangements [pdf] - Emory Mathematics
DERANGEMENTS. A permutation is called a derangement if no object returns to its original location. For example, there are just two derangements of three objects ...
[23]
[PDF] The Cantor-Schroeder-Bernstein theorem
We give a proof of the Cantor-Schröder-Bernstein theorem: if A injects into B and. B injects into A, then there is a bijection between A and B. This seemingly ...
[24]
[PDF] 1 Categories - UChicago Math
Thus in Set, a morphism (function) is an isomorphism (bijection) if and only if it is both injective and surjective. The notions of injections and surjections ...<|control11|><|separator|>
[25]
[PDF] introduction to category theory and the yoneda lemma
Oct 9, 2022 · An isomorphism in a category C is a morphism f : X → Y such that there exists an inverse morphism g : Y → X with the property f ◦ g = 1Y and g ◦ ...
[26]
[PDF] Chapter 4 - Basic category theory - MIT OpenCourseWare
BASIC CATEGORY THEORY. 4.3.1 Definition and examples. Let's begin with an ... same cardinality means precisely that there exists an isomorphism between them.
[27]
4.22 Isomorphisms ‣ Chapter 4 Linear algebra ‣ MATH0005 ...
Linear maps which are bijections are called vector space isomorphisms, or just isomorphisms. If there is an isomorphism U → V, we say that U and V are ...
[28]
[PDF] [DRAFT] A Peripatetic Course in Algebraic Topology
Jul 22, 2016 · Remark. Homeomorphisms play the role of isomorphisms for topological spaces. Two spaces that are isomorphic (e.g., (a,b) and R) have the same ...
[29]
[PDF] On the Category of Partial Bijections
A partial function f which induce a bijection between Def(f) and Im(f) is called a partial bijection. If f:X→Y is a partial bijection then the partial bijection ...
[30]
Whatâ•Žs the difference? a functional pearl on subtracting bijections
Instead, we must generalize to partial bijections, that is, bijections which may be undefined on some parts of their domain (Figure 5). We can think of the ...
[31]
[PDF] Partitions and Equivalence Relations - Stony Brook Computer Science
Equivalence Relations. A relation that is reflexive, transitive, and symmetric is called an equivalence relation. For example, the set {(a,a), (b, b), (c, c)} ...
[32]
Type Isomorphism - Kwang's Haskell Blog
Dec 25, 2016 · Type isomorphisms are a general notion of conversion between types. We say that type A and B are isomorphic, if we have conversion functions f :: A -> B and g ...Missing: Coq | Show results with:Coq
[33]
[PDF] Pragmatic Isomorphism Proofs Between Coq Representations
We propose some generic tools to help setting up the correspondence between two isomorphic types more easily.
[34]
[PDF] The Significance of the Curry-Howard Isomorphism | Richard Zach
Nov 26, 2019 · Abstract: The Curry-Howard isomorphism is a proof-theoretic result that estab- lishes a connection between derivations in natural deduction ...<|separator|>
[35]
[PDF] Frege's Principle - Richard Kimberly Heck
the notion of one-one correspondence can be defined in logical terms: Frege explains, as is now standard, that the Fs can be correlated one-one with the. Gs ...
[36]
33 Understanding Relational Mappings
Relational mappings let you map an object model into a relational data model. Relational mappings transform object data members to relational database fields.<|separator|>