Bijection

“One-to-one correspondence” redirects here. For a function that is one-to-one but not necessarily onto, see injective function .

Bijective function

A bijective function, also known as a bijection or one-to-one correspondence, is a fundamental concept in mathematics , specifically within the realm of functions . It describes a specific type of mapping between two sets , say set $X$ (the domain ) and set $Y$ (the codomain ). The defining characteristic of a bijection is that it creates a perfect pairing: every single element in the codomain $Y$ is the unique image of precisely one element from the domain $X$.

Think of it this way: if you have two collections of items, and you can match each item in the first collection with exactly one item in the second collection, and vice versa, without any leftovers or duplicates, you’ve established a bijection. It’s a relationship of perfect equivalence between the elements of the two sets.

Formal Definition and Properties

Mathematically, a function $f: X \to Y$ is bijective if and only if it satisfies two crucial conditions:

1. Injectivity (One-to-One): For any two distinct elements $x_1$ and $x_2$ in the domain $X$, their images under $f$ must also be distinct in the codomain $Y$. That is, if $x_1 \neq x_2$, then $f(x_1) \neq f(x_2)$. This ensures that no two elements from the domain map to the same element in the codomain.
2. Surjectivity (Onto): For every element $y$ in the codomain $Y$, there must exist at least one element $x$ in the domain $X$ such that $f(x) = y$. This guarantees that every element in the codomain is “hit” by the function.

When a function is both injective and surjective, it’s a bijection.

An alternative, and often more intuitive, way to define a bijection is through the concept of an inverse function . A function $f: X \to Y$ is bijective if and only if it has an inverse function, denoted as $g: Y \to X$. This inverse function $g$ “undoes” what $f$ does. Specifically, the composition of $f$ and $g$ in either order must result in the identity function for their respective sets:

• $g(f(x)) = x$ for all $x$ in $X$.
• $f(g(y)) = y$ for all $y$ in $Y$.

This property of having an inverse is a hallmark of bijections. If a function can be reversed to yield another function, it must have been a bijection to begin with.

Examples to Illuminate the Concept

Consider the function that maps an integer $n$ to its double, $2n$. Let $X$ be the set of all integers, and $Y$ be the set of all even numbers . This function, $f(n) = 2n$, is a bijection.

• Injective: If you take two different integers, say 3 and 5, their doubles (6 and 10) are also different. No two different integers produce the same double.
• Surjective: Every even number can be obtained by doubling some integer. For example, the even number 14 is $2 \times 7$, and 14 is also $2 \times (-7)$, but since we’re mapping from the integers, we only need one integer. The inverse function here is simply dividing by two. This function establishes a one-to-one correspondence between the integers and the even numbers.

Let’s look at another example: the batting line-up of a sports team, like baseball or cricket . If set $X$ is the set of players on the team (say, nine players) and set $Y$ is the set of batting positions (1st, 2nd, …, 9th), the assignment of a player to a specific batting position forms a bijection.

• Each player is assigned exactly one position in the batting order (injective).
• Each batting position has exactly one player assigned to it (surjective).

The instructor in a classroom example vividly illustrates this. If there are students and seats, and every student is sitting in exactly one seat, and every seat is occupied by exactly one student, then the instructor has observed a bijection between the set of students and the set of seats. They know, without counting, that the number of students equals the number of seats. This is the fundamental idea behind counting finite sets.

Mathematical Examples and Nuances

• The identity function , $1_X(x) = x$, which maps every element of a set $X$ to itself, is always a bijection from $X$ to $X$. It’s the most basic form of a one-to-one correspondence.

• The function $f(x) = 2x + 1$ mapping the real numbers $\mathbb{R}$ to itself is a bijection. For any real number $y$, there’s a unique real number $x = (y-1)/2$ such that $f(x) = y$. This demonstrates that linear functions $f(x) = ax + b$ with a non-zero slope $a$ are bijections from $\mathbb{R}$ to $\mathbb{R}$.

• Consider the arctangent function , $f(x) = \arctan(x)$, mapping $\mathbb{R}$ to the open interval $(-\pi/2, \pi/2)$. This is a bijection. Each real number $x$ corresponds to a unique angle $y$ in that specific interval whose tangent is $x$. However, if the codomain were expanded to include $\pi/2$ or $-\pi/2$, it would cease to be surjective because the arctangent function never reaches these values.

• The exponential function , $g(x) = e^x$, mapping $\mathbb{R}$ to $\mathbb{R}$, is not a bijection. It fails to be surjective because there’s no real number $x$ for which $e^x$ is negative or zero. If we restrict its codomain to just the positive real numbers, $(0, \infty)$, then it does become a bijection, with the natural logarithm function, $\ln(x)$, as its inverse.

• The squaring function, $h(x) = x^2$, mapping $\mathbb{R}$ to $\mathbb{R}$, is also not a bijection. It fails to be injective because, for example, $h(-2) = 4$ and $h(2) = 4$; two different inputs give the same output. However, if we restrict its domain to the non-negative real numbers, $[0, \infty)$, then it becomes a bijection, with the positive square root function as its inverse.

Cardinality and the Infinite

The concept of a bijection is absolutely central to understanding the sizes of sets , especially infinite sets . Two sets, whether finite or infinite, are considered to have the same cardinal number if and only if there exists a bijection between them. This is known as equinumerosity .

This definition is particularly profound when applied to infinite sets. It implies that some infinite sets are “larger” than others. For instance, the set of natural numbers ${1, 2, 3, …}$ and the set of even numbers ${2, 4, 6, …}$ have the same cardinality because we can construct a bijection between them (the $f(n) = 2n$ example). This is counterintuitive for finite sets, where a proper subset can never have the same number of elements as the set itself. However, for infinite sets, this is precisely how we define “having the same size.”

The Schröder–Bernstein theorem is a powerful result that states if there’s an injection from set $X$ to set $Y$, and another injection from $Y$ to $X$, then there must exist a bijection between $X$ and $Y$. This means if we can show that $X$ isn’t “larger” than $Y$ and $Y$ isn’t “larger” than $X$, then they must be the same size.

Bijections in Group Theory and Beyond

A bijective function from a set to itself is called a permutation . The collection of all permutations of a set $X$, along with the operation of function composition , forms a mathematical structure known as the symmetric group of $X$. This group is fundamental in understanding symmetries and abstract algebra.

In category theory , bijections are precisely the isomorphisms in the category of sets . However, in more specialized categories, like the category of groups , an isomorphism must not only be a bijection but also preserve the structure of the objects (in this case, homomorphisms ).

Generalizations and Related Concepts

The concept can be extended to partial functions , where they are called partial bijections. These are simply injective partial functions. A partial bijection from $A$ to $B$ can also be viewed as a relation that corresponds to the graph of a bijection between some subset of $A$ and some subset of $B$.

The notion of a one-to-one correspondence is deeply intertwined with other mathematical ideas:

• Injective functions are one-to-one but not necessarily onto.
• Surjective functions are onto but not necessarily one-to-one.
• Permutations are bijections from a set to itself.
• Isomorphisms are bijections that preserve structure in various mathematical contexts.
• Homeomorphisms are bijections between topological spaces that preserve topological properties.
• Diffeomorphisms are bijections between smooth manifolds that preserve smooth structure.

In essence, a bijection signifies a perfect, reversible match between the elements of two sets. It’s a foundational concept that underpins our understanding of counting, size, structure, and equivalence in mathematics.