A function is
bijective if and only if it is both surjective and
injective. If (as is often done) a function is identified with its
graph, then surjectivity is not a property of the function itself, but rather a property of the
mapping. This is, the function together with its codomain. Unlike injectivity, surjectivity cannot be read off of the graph of the function alone.
Surjections as right invertible functions The function is said to be a
right inverse of the function if
f(
g(
y)) =
y for every
y in
Y (
g can be undone by
f). In other words,
g is a right inverse of
f if the
composition of
g and
f in that order is the
identity function on the domain
Y of
g. The function
g need not be a complete
inverse of
f because the composition in the other order, , may not be the identity function on the domain
X of
f. In other words,
f can undo or "
reverse"
g, but cannot necessarily be reversed by it. For example, f:\R^2\rightarrow\R,(x,y)\mapsto x has right inverse g:z\mapsto (z,0); the composition in the other order gives , which equals only if . Every function with a right inverse is necessarily a surjection. The proposition that every surjective function has a right inverse is equivalent to the
axiom of choice. If is surjective and
B is a
subset of
Y, then
f(
f −1(
B)) =
B. Thus,
B can be recovered from its
preimage . For example, in the first illustration in the
gallery, there is some function
g such that
g(
C) = 4. There is also some function
f such that
f(4) =
C. It doesn't matter that
g is not unique (it would also work if
g(
C) equals 3); it only matters that
f "reverses"
g.
Surjections as epimorphisms A function is surjective if and only if it is
right-cancellative:{{Cite book Any morphism with a right inverse is an epimorphism, but the converse is not true in general. A right inverse
g of a morphism
f is called a
section of
f. A morphism with a right inverse is called a
split epimorphism.
Surjections as binary relations Any function with domain
X and codomain
Y can be seen as a
left-total and
right-unique binary relation between
X and
Y by identifying it with its
function graph. A surjective function with domain
X and codomain
Y is then a binary relation between
X and
Y that is right-unique and both left-total and
right-total.
Cardinality of the domain of a surjection The
cardinality of the domain of a surjective function is greater than or equal to the cardinality of its codomain: If is a surjective function, then
X has at least as many elements as
Y, in the sense of
cardinal numbers. (The proof appeals to the
axiom of choice to show that a function satisfying
f(
g(
y)) =
y for all
y in
Y exists.
g is easily seen to be injective, thus the
formal definition of |
Y| ≤ |
X| is satisfied.) Specifically, if both
X and
Y are
finite with the same number of elements, then is surjective if and only if
f is
injective.
Composition and decomposition The
composition of surjective functions is always surjective: If
f and
g are both surjective, and the codomain of
g is equal to the domain of
f, then is surjective. Conversely, if is surjective, then
f is surjective (but
g, the function applied first, need not be). These properties generalize from surjections in the
category of sets to any
epimorphisms in any
category. Any function can be decomposed into a surjection and an
injection: For any function there exist a surjection and an injection such that
h =
g o
f. To see this, define
Y to be the set of
preimages where
z is in . These preimages are
disjoint and
partition X. Then
f carries each
x to the element of
Y which contains it, and
g carries each element of
Y to the point in
Z to which
h sends its points. Then
f is surjective since it is a projection map, and
g is injective by definition.
Induced surjection and induced bijection Any function induces a surjection by restricting its codomain to its range. Any surjective function induces a bijection defined on a
quotient of its domain by collapsing all arguments mapping to a given fixed image. More precisely, every surjection can be factored as a projection followed by a bijection as follows. Let
A/~ be the
equivalence classes of
A under the following
equivalence relation:
x ~
y if and only if
f(
x) =
f(
y). Equivalently,
A/~ is the set of all preimages under
f. Let
P(~) :
A →
A/~ be the
projection map which sends each
x in
A to its equivalence class [
x]~, and let
fP :
A/~ →
B be the well-defined function given by
fP([
x]~) =
f(
x). Then
f =
fP o
P(~). == The set of surjections ==