Bijection
A function pairing each element of two sets exactly once.
Schapel · Public domain
A bijection, also known as a bijective function or one-to-one correspondence, is a function between two sets such that each element of the second set (the codomain) is the image of exactly one element of the first set (the domain). Equivalently, it is a relation between two sets such that each element of either set is paired with exactly one element of the other set. A function is bijective if and only if it is both injective (one-to-one) and surjective (onto), and if and only if it is invertible.
- field
- Mathematics
- known_for
- Defining a one-to-one correspondence between sets, establishing equal cardinality, and forming the basis for permutations and symmetric groups
Lore & Background
A bijection requires four properties: each element of the domain is paired with at least one element of the codomain, no element of the domain is paired with more than one element of the codomain, each element of the codomain is paired with at least one element of the domain, and no element of the codomain is paired with more than one element of the domain. Satisfying the first two properties means the pairing is a function with the domain. Functions satisfying the third property are surjections (onto), and those satisfying the fourth are injections (one-to-one). Thus a bijection is a function that is both a surjection and an injection. Examples include the multiplication by two as a bijection from the integers to the even numbers, with division by two as its inverse. The identity function on any set is bijective. The function f(x) = 2x + 1 over the reals is bijective, as is any linear function f(x) = ax + b with non-zero a. The arctan function is a bijection from the reals to the interval (−π/2, π/2). The exponential function is not bijective over all reals but becomes bijective when the codomain is restricted to positive real numbers. The square function is not bijective over all reals but becomes bijective when the domain is restricted to non-negative reals.
Reader's Guide
The concept of a bijection is fundamental in mathematics because it provides a precise way to compare the sizes of sets without counting. The elementary operation of counting establishes a bijection from a finite set to the first natural numbers up to the number of elements, leading to the result that two finite sets have the same number of elements if and only if there exists a bijection between them. More generally, two sets are said to have the same cardinal number if there exists a bijection between them. A bijective function from a set to itself is called a permutation, and the set of all permutations of a set forms its symmetric group. Certain bijections with further properties have specific names, including automorphisms, isomorphisms, homeomorphisms, diffeomorphisms, and most geometric transformations. Galois correspondences are bijections between sets of mathematical objects of apparently very different nature. The term 'one-to-one correspondence' must not be confused with 'one-to-one function,' which means injective but not necessarily surjective.
Did You Know?
- A function is bijective if and only if it is invertible; that is, there exists an inverse function such that composing the two functions in either order yields an identity function.
- The multiplication by two defines a bijection from the integers to the even numbers, with division by two as its inverse.
- Every map from the empty set to itself is a bijection.
- A bijective function from a set to itself is called a permutation, and the set of all permutations of a set forms its symmetric group.
Gallery
Frequently Asked Questions
Who is Bijection?
In combinatorics, Bijection is a function that pairs every element of one set with exactly one element of another set, leaving no element unmatched on either side. It is the formal way mathematicians express that two sets share the same size, or cardinality.
What are Bijection's powers and role?
A bijection must simultaneously be injective (no two inputs collide on the same output) and surjective (every output is reached). Because it satisfies both conditions, it is always invertible, meaning you can unambiguously recover the original input from the output.
How does Bijection's story end?
The concept reaches its fullest expression in the symmetric group, where every bijection from a finite set to itself is called a permutation. That collection, equipped with composition, becomes one of the central structures in algebra and combinatorial counting.
Why is Bijection important?
Bijection lets a mathematician prove two sets have the same cardinality by constructing an explicit pairing, without ever needing to count elements directly. It also underpins the definitions of permutations, symmetric groups, and a wide range of counting arguments throughout combinatorics.
What is the difference between Bijection, Injection, and Surjection?
An injection guarantees distinct inputs produce distinct outputs, while a surjection guarantees every element in the codomain is hit by at least one input. A bijection is precisely the function that is both injective and surjective at the same time.
More in Combinatorics 1-24
Elsewhere in the Combinatorics universe
Spotted an error? Know more?
This is a living reference — every entry is fact-audited, and reader corrections feed straight into our audit queue. Suggest an edit · See this site's audit record