Bijection
A function pairing each element of two sets exactly once.
Schapel · Public domain
A bijection is a pairing between two sets where every element of the first set is matched with exactly one element of the second set, and every element of the second set is matched with exactly one element of the first set. This is also called a bijective function or a one-to-one correspondence. For a function f from set A to set B, the image of an element a in A is f(a) in B, and the pre-image of an element b in B is any a in A such that f(a) = b. A function is bijective precisely when it has an inverse: a function g from Y to X such that g(f(x)) = x for every x in X and f(g(y)) = y for every y in Y. For instance, multiplying by two gives a bijection from the integers to the even numbers, with division by two as its inverse.
A bijection must satisfy four conditions: each element of the first set is paired with at least one element of the second; no element of the first is paired with more than one of the second; each element of the second is paired with at least one of the first; and no element of the second is paired with more than one of the first. The first two conditions together mean the pairing is a function from the first set. A function satisfying the third condition is surjective (onto), and one satisfying the fourth is injective (one-to-one). So a bijection is both injective and surjective. The term "one-to-one correspondence" should not be confused with "one-to-one function," which means injective but not necessarily surjective.
Counting a finite set creates a bijection from that set to the first natural numbers (1, 2, 3, ...) up to the set's size. Consequently, two finite sets have the same number of elements if and only if a bijection exists between them. More generally, two sets have the same cardinal number if a bijection exists between them. A bijection from a set to itself is called a permutation, and all permutations of a set form its symmetric group. Some bijections with special properties have specific names, such as automorphisms, isomorphisms, homeomorphisms, diffeomorphisms, permutations, and most geometric transformations. Galois correspondences are bijections between sets of mathematical objects that appear very different in nature.
Examples include the map from the empty set to itself, which is always a bijection. In a baseball or cricket team's batting line-up, the set of players and the set of batting positions form a bijection: each player occupies exactly one position, and each position is filled by exactly one player. Similarly, in a classroom, if every student sits in a seat and every seat is taken by one student, there is a bijection between the set of students and the set of seats.
- 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
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