Bijective Function

A bijective function, or bijection, is a function that is both injective and surjective. It establishes a one-to-one correspondence between two sets: every element of the target set is the image of exactly one element of the source set. Bijections provide the basic criterion for two sets to have the same size and characterize functions that can be reversed without ambiguity. (math.mit.edu)

Definition and terminology

Let $f:A\to B$ be a function, with domain $A$ and codomain $B$. The function is bijective precisely when

where $\exists!$ means “there exists exactly one.” This combines two requirements:

• Injectivity: if $f(a_1)=f(a_2)$, then $a_1=a_2$. Distinct inputs never have the same output.
• Surjectivity: for every $b\in B$, some $a\in A$ satisfies $f(a)=b$. Every element of the codomain is reached. (jirka.org)

Bijectivity depends on the specified domain and codomain, not merely on a formula. For example, $f(x)=x^2$ is not bijective from the real numbers to themselves: opposite nonzero inputs have equal outputs, and negative numbers are not reached. Restricting both sets to $[0,\infty)$ makes the same formula bijective. This illustrates why the codomain must be distinguished from the set of outputs actually attained. (jirka.org)

Inverse functions and composition

A function $f:A\to B$ is bijective if and only if it has a two-sided inverse function $f^{-1}:B\to A$, satisfying

Here $\operatorname{id}_A(a)=a$ is the identity function. Surjectivity guarantees that an input can be recovered for every element of $B$; injectivity guarantees that the recovered input is unique. Consequently, the inverse exists, is unique, and is itself bijective. (jirka.org)

For example, $f:\mathbb R\to\mathbb R$, defined by $f(x)=3x-2$, has inverse

Substituting either formula into the other returns the original argument, establishing both inverse identities.

Bijections are also preserved by function composition. If $f:A\to B$ and $g:B\to C$ are bijective, then $g\circ f:A\to C$ is bijective, with

The reversed order reflects the need to undo the last operation first. (jirka.org)

Finite sets and permutations

For finite sets, a bijection exists exactly when the sets have the same number of elements. Moreover, if $A$ and $B$ are finite and equally large, any injective function $A\to B$ is automatically surjective, and any surjective function is automatically injective. Thus either condition suffices in this particular setting. (web.cecs.pdx.edu)

A bijection from a set to itself is called a permutation. An $n$-element set has $n!$ permutations, where $n!$ denotes the factorial: the successive images can be chosen in $n,n-1,\ldots,1$ ways. This includes the empty set, which has one permutation, consistent with $0!=1$. (web.cecs.pdx.edu)

Cardinality and infinite sets

In set theory, two sets have equal cardinality precisely when a bijection exists between them. This definition extends the comparison of sizes beyond finite counting. For instance, taking the natural numbers to be $\mathbb N=\{0,1,2,\ldots\}$, the function

is bijective. Its inverse sends each even number $m$ to $m/2$. Therefore, an infinite set can have the same cardinality as a proper subset of itself. (people.csail.mit.edu)

The finite equivalence between injectivity and surjectivity fails for infinite sets. The map $n\mapsto n+1$ from $\mathbb N$ to itself is injective but misses $0$. A countably infinite set is one that admits a bijection with $\mathbb N$; the existence of such a correspondence, rather than the appearance of the elements, determines countable infinitude. (people.csail.mit.edu)

Bijective proofs

In combinatorics, a bijective proof establishes that two collections have equal size by constructing an explicit bijection. Such a proof explains the equality through a reversible correspondence rather than only through numerical calculation. (math.mit.edu)

For example, subsets of $\{1,\ldots,n\}$ correspond bijectively to binary strings of length $n$: position $i$ contains $1$ exactly when $i$ belongs to the subset. Reading the positions containing $1$ reverses the construction. Since each position has two choices, the power set of an $n$-element set contains $2^n$ elements. (math.mit.edu)

Additional mathematical structure

Bijectivity concerns the underlying sets; preserving additional structure requires further conditions. In linear algebra, a bijective linear map between vector spaces is a linear isomorphism. For a square matrix over a field, the associated linear map is bijective exactly when the matrix is invertible, equivalently when its determinant is nonzero. (people.math.carleton.ca)

In topology, a continuous bijection need not have a continuous inverse. A homeomorphism requires continuity in both directions. An important sufficient condition is that a continuous bijection from a compact space onto a Hausdorff space is a homeomorphism. (web.math.ucsb.edu)