Bijection, injection and surjection

Surjection

A function is surjective or onto if each element of the codomain is mapped to by at least one element of the domain. In other words, each element of the codomain has a non-empty preimage. Equivalently, a function is surjective if its image is equal to its codomain. A surjective function is a surjection. The formal definition is the following.

The function ${\displaystyle f:X\to Y}$ is surjective, if for all ${\displaystyle y\in Y}$, there is ${\displaystyle x\in X}$ such that ${\displaystyle f(x)=y.}$

The following are some facts related to surjections:

• A function ${\displaystyle f:X\to Y}$ is surjective if and only if it is right-invertible; that is, if and only if there is a function ${\displaystyle g:Y\to X}$ such that ${\displaystyle f\circ g=}$ identity function on ${\displaystyle Y}$. (This statement is equivalent to the axiom of choice.)
• By collapsing all arguments mapping to a given fixed image, every surjection induces a bijection from a quotient set of its domain to its codomain. More precisely, given a function ${\displaystyle f}$, define an equivalence relation on the domain of ${\displaystyle f}$, such that x and y are equivalent if and only if they have the same image under ${\displaystyle f}$; then the equivalence classes of this relation are the preimages under ${\displaystyle f}$ of the elements of the image of ${\displaystyle f}$. As all elements of any one of these equivalence classes are mapped by ${\displaystyle f}$ on the same element of the codomain, this induces a bijection between the quotient set by this equivalence relation (the set of the equivalence classes) and the image of ${\displaystyle f}$ (which is its codomain when ${\displaystyle f}$ is surjective). Moreover, ${\displaystyle f}$ is the composition of the canonical projection from ${\displaystyle f}$ to the quotient set, and the bijection between the quotient set and the codomain of ${\displaystyle f}$.
• The composition of two surjections is again a surjection, but if ${\displaystyle g\circ f}$ is surjective, then it can only be concluded that ${\displaystyle g}$ is surjective (see figure).

Bijection

A function is bijective if it is both injective and surjective. A bijective function is also called a bijection or a one-to-one correspondence (not to be confused with one-to-one function, which refers to injection). A function is bijective if and only if every possible image is mapped to by exactly one argument. This equivalent condition is formally expressed as follows:

The function ${\displaystyle f:X\to Y}$ is bijective, if for all ${\displaystyle y\in Y}$, there is a unique ${\displaystyle x\in X}$ such that ${\displaystyle f(x)=y.}$

The following are some facts related to bijections:

• A function ${\displaystyle f:X\to Y}$ is bijective if and only if it is invertible; that is, there is a function ${\displaystyle g:Y\to X}$ such that ${\displaystyle g\circ f=}$ identity function on ${\displaystyle X}$ and ${\displaystyle f\circ g=}$ identity function on ${\displaystyle Y}$. This function maps each image to its unique preimage.
• The composition of two bijections is again a bijection, but if ${\displaystyle g\circ f}$ is a bijection, then it can only be concluded that ${\displaystyle f}$ is injective and ${\displaystyle g}$ is surjective (see the figure at right and the remarks above regarding injections and surjections).
• The bijections from a set to itself form a group under composition, called the symmetric group.

Cardinality

Suppose that one wants to define what it means for two sets to "have the same number of elements". One way to do this is to say that two sets "have the same number of elements", if and only if all the elements of one set can be paired with the elements of the other, in such a way that each element is paired with exactly one element. Accordingly, one can define two sets to "have the same number of elements"—if there is a bijection between them. In which case, the two sets are said to have the same cardinality.

Likewise, one can say that set ${\displaystyle X}$ "has fewer than or the same number of elements" as set ${\displaystyle Y}$, if there is an injection from ${\displaystyle X}$ to ${\displaystyle Y}$; one can also say that set ${\displaystyle X}$ "has fewer than the number of elements" in set ${\displaystyle Y}$, if there is an injection from ${\displaystyle X}$ to ${\displaystyle Y}$, but not a bijection between ${\displaystyle X}$ and ${\displaystyle Y}$.

Examples

It is important to specify the domain and codomain of each function, since by changing these, functions which appear to be the same may have different properties.

Injective and surjective (bijective)

• The identity function id_X for every non-empty set X, and thus specifically ${\displaystyle \mathbf{R}\to \mathbf{R}:x\mapsto x.}$
• ${\displaystyle {\mathbf{R}}^{+}\to {\mathbf{R}}^{+}:x\mapsto x^2}$, and thus also its inverse ${\displaystyle {\mathbf{R}}^{+}\to {\mathbf{R}}^{+}:x\mapsto \sqrt{x}.}$
• The exponential function ${\displaystyle \exp :\mathbf{R}\to {\mathbf{R}}^{+}:x\mapsto {\mathrm{e}}^x}$ (that is, the exponential function with its codomain restricted to its image), and thus also its inverse the natural logarithm ${\displaystyle \ln :{\mathbf{R}}^{+}\to \mathbf{R}:x\mapsto \ln x.}$ Here, ${\displaystyle {\mathbf{R}}^{+}}$ denotes the positive real numbers.
• ${\displaystyle \mathbf{R}\to \mathbf{R}:x\mapsto x^3}$

Injective and non-surjective

• The exponential function ${\displaystyle \exp :\mathbf{R}\to \mathbf{R}:x\mapsto {\mathrm{e}}^x.}$

Non-injective and surjective

• ${\displaystyle \mathbf{R}\to \mathbf{R}:x\mapsto (x-1)x(x+1)=x^3-x.}$
• ${\displaystyle \mathbf{R}\to [-1,1]:x\mapsto \sin (x).}$

Non-injective and non-surjective

• ${\displaystyle \mathbf{R}\to \mathbf{R}:x\mapsto \sin (x).}$
• ${\displaystyle \mathbf{R}\to \mathbf{R}:x\mapsto x^2}$

Properties

• For every function ${\displaystyle f}$, let ${\displaystyle X}$ be a subset of the domain and ${\displaystyle Y}$ a subset of the codomain. One has always ${\displaystyle X\subset f^{-1}(f(X))}$ and ${\displaystyle f(f^{-1}(Y))\subset Y}$, where ${\displaystyle f(X)}$ is the image of ${\displaystyle X}$ and ${\displaystyle f^{-1}(Y)}$ is the preimage of ${\displaystyle Y}$ under ${\displaystyle f}$. If ${\displaystyle f}$ is injective, then ${\displaystyle X=f^{-1}(f(X))}$, and if ${\displaystyle f}$ is surjective, then ${\displaystyle f(f^{-1}(Y))=Y}$.
• For every function ${\displaystyle h:X\to Y}$, one can define a surjection ${\displaystyle H:X\to h(X):x\mapsto h(x)}$ and an injection ${\displaystyle I:h(X)\to Y:y\mapsto y}$. It follows that ⁠${\displaystyle h=I\circ H}$⁠. This decomposition as the composition of a surjection and an injection is unique up to an isomorphism, in the sense that, given such a decomposition, there is a unique bijection ${\displaystyle \phi :h(X)\to H(X)}$ such that ${\displaystyle H(x)=\phi (h(x))}$ and ${\displaystyle I(\phi (h(x)))=h(x)}$ for every ${\displaystyle x\in X.}$

Category theory

In the category of sets, injections, surjections, and bijections correspond precisely to monomorphisms, epimorphisms, and isomorphisms, respectively.

History

The Oxford English Dictionary records the use of the word injection as a noun by S. Mac Lane in Bulletin of the American Mathematical Society (1950), and injective as an adjective by Eilenberg and Steenrod in Foundations of Algebraic Topology (1952).

However, it was not until the French Bourbaki group coined the injective-surjective-bijective terminology in 1954 in Théorie des ensembles (both as nouns and adjectives) that they achieved widespread adoption.