# Bijection

In mathematics, a function *f* from a set *X* to a set *Y* is said to be **bijective** if and only if for every *y* in *Y* there is exactly one *x* in *X* such that *f*(*x*) = *y*.

Said another way, *f* is bijective if and only if it is a **one-to-one correspondence** between those sets; i.e., both **one-to-one** (injective) and **onto** (surjective).

For example, consider the function succ, defined from the set of integers **Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \Z}**
to **Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \Z}**
, that to each integer *x* associates the integer succ(*x*) = x + 1. For another example, consider the function sumdif that to each pair (*x*,*y*) of real numbers associates the pair sumdif(*x*,*y*) = (*x*+*y*, *x*-*y*).

A bijective function is also called a **bijection** or **permutation**. The latter is more commonly used when *X* = *Y*. It should be noted that *one-to-one function* means *one-to-one correspondence* (i.e., *bijection*) to some authors, but *injection* to others. The set of all bijections from *X* to *Y* is denoted as *X***Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle {}\leftrightarrow{}}**
*Y*.

Bijective functions play a fundamental role in many areas of mathematics, for instance in the definition of isomorphism (and related concepts such as homeomorphism and diffeomorphism), permutation group, projective map, and many others.

## Contents

## Composition and inverses

A function *f* is bijective if and only if its inverse relation *f*^{-1} is a function. In that case, *f*^{-1} is a bijection.

The composition *g***Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \circ}**
*f* of two bijections *f***Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \;:\;}**
*X***Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle {}\leftrightarrow{}}**
*Y* and *g***Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \;:\;}**
*Y***Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle {}\leftrightarrow{}}**
*Z* is a bijection. The inverse of *g***Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \circ}**
*f* is (*g***Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \circ}**
*f*)^{-1} = (*f*^{-1})*g*^{-1}).

On the other hand, if the composition *g* ^{o} *f* of two functions is bijective, we can only say that *f* is injective and *g* is surjective.

A relation *f* from *X* to *Y* is a bijective function if and only if there exists another relation *g* from *Y* to *X* such that *g**f* is the identity function on *X*, and *f**g* is the identity function on *Y*.
It is important to say that having the same cardinality for two sets is a must.

## Bijections and cardinality

If *X* and *Y* are finite sets, then there exists a bijection between the two sets *X* and *Y* if and only if *X* and *Y* have the same number of elements. Indeed, in axiomatic set theory, this is taken as the very *definition* of "same number of elements", and generalising this definition to infinite sets leads to the concept of cardinal number, a way to distinguish the various sizes of infinite sets.

## Examples and counterexamples

- For any set
*X*, the identity function id_{X}from*X*to*X*, defined by id_{X}(*x*) =*x*, is bijective. - The function
*f*from the real line**R**to**R**defined by*f*(*x*) = 2*x*+ 1 is bijective, since for each*y*there is a unique*x*= (*y*- 1)/2 such that*f*(*x*) =*y*. - The exponential function
*g*:**R****Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \rightarrow}****R**, with*g(x)*= e^{x}, is not bijective: for instance, there is no*x*in**R**such that*g*(*x*) = -1, showing that*g*is not surjective. However if the codomain is changed to be the positive real numbers**R**^{+}= (0,+∞), then*g*becomes bijective; its inverse is the natural logarithm function ln. - The function
*h*:**R****Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \rightarrow}**[0,+∞) with*h(x)*=*x*² is not bijective: for instance,*h*(-1) =*h*(+1) = 1, showing that*h*is not injective. However, if the domain too is changed to [0,+∞), then*h*becomes bijective; its inverse is the positive square root function.

- A function
*f*from the real line**R**to**R**is bijective if and only if its plot is intersected by any horizontal line at exactly one point.

**Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathbf{R} \to \mathbf{R} : x \mapsto (x-1)x(x+1) = x^3 - x }**is not a bijection because -1, 0, and +1 are all in the domain and all map to 0.**Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathbf{R} \to [-1,1] : x \mapsto \sin(x)}**is not a bijection because**Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \pi/3}**and**Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 2\cdot\pi/3}**are both in the domain and both map to**Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (\sqrt 3)/2}**.

## Properties

- If
*X*is a set, then the bijective functions from*X*to itself, together with the operation of functional composition (^{o}), form a group, the symmetric group of*X*, which is denoted variously by S(*X*),*S*_{X}, or*X*! (the last read "*X*factorial"). - For subset
*A*of the domain and subset*B*of the codomain we

|*f*(*A*)| == |*A*|, and |*f*^{-1}(*B*)| == |*B*|.

(*Note: a one-to-one function is injective, but may fail to be surjective, while a one-to-one correspondence is both injective and surjective.*)

## Bijections and category theory

Formally, bijections are precisely the isomorphisms in the category Set of sets.