SURJECTIVE FUNCTION

In mathematics, a function ''f'' is said to be 'surjective' if its values span its whole codomain; that is, for every ''y'' in the codomain, there is at least one ''x'' in the domain such that ''f''(''x'') = ''y''.
Said another way, a function ''f'': ''X'' → ''Y'' is surjective if and only if its range ''f''(''X'') is equal to its codomain ''Y''. A surjective function is called a 'surjection', and also said to be 'onto'.

Contents

Examples and a counterexample

There always exists a function "reversible" by a surjection

Other properties

See also

Category theory view

Examples and a counterexample

★ For any set ''X'', the identity function id_''X'' on ''X'' is surjective.

★ The function ''f'': 'R' → 'R' defined by ''f''(''x'') = 2''x'' + 1 is surjective, because for every real number ''y'' we have ''f''(''x'') = ''y'' where ''x'' is (''y'' - 1)/2.

★ The natural logarithm function ln: (0,+∞) → 'R' is surjective.

★ The function ''f'': 'Z' → '{0,1,2,3}' defined by ''f''(''x'') = ''x'' 'mod' 4 is surjective.

★ The function ''g'': 'R' → 'R' defined by ''g''(''x'') = ''x''² is ''not'' surjective, because (for example) there is no real number ''x'' such that ''x''² = −1. However, if the codomain is defined as [0,+∞), then ''g'' is surjective.

There always exists a function "reversible" by a surjection

Every function with a right inverse is a surjection. The converse is equivalent to the axiom of choice. That is, assuming choice, a function ''f'': ''X'' → ''Y'' is surjective if and only if there exists a function ''g'': ''Y'' → ''X'' such that, for every $y\; in\; Y$
:$f(g(y))\; =\; y\; ,$ (''g'' can be undone by ''f'')
that is a function ''g'' such that ''f'' o ''g'' equals the identity function on ''Y'' (cf. with definition of inverse function).
Note that ''g'' may not be a complete inverse of ''f'' because the composition in the other order, ''g'' o ''f'', may not be the identity on ''X''. In other words, f can undo or "''reverse''" ''g'', but not necessarily can be reversed by it. Surjections are not always invertible (bijective).

Other properties

★ If ''f'' and ''g'' are both surjective, then ''f'' o ''g'' is surjective.

★ If ''f'' o ''g'' is surjective, then ''f'' is surjective (but ''g'' may not be).

★ ''f'': ''X'' → ''Y'' is surjective if and only if, given any functions ''g'',''h'':''Y'' → ''Z'', whenever ''g'' o ''f'' = ''h'' o ''f'', then ''g'' = ''h''. In other words, surjective functions are precisely the epimorphisms in the category 'Set' of sets.

★ If ''f'': ''X'' → ''Y'' is surjective and ''B'' is a subset of ''Y'', then ''f''(''f'' ⁻¹(''B'')) = ''B''. Thus, ''B'' can be recovered from its preimage ''f'' ⁻¹(''B'').

★ Every function ''h'': ''X'' → ''Z'' can be decomposed as ''h'' = ''g'' o ''f'' for a suitable surjection ''f'' and injective function ''g''. This decomposition is unique up to isomorphism, and ''f'' may be thought of as a function with the same values as ''h'' but with its codomain restricted to the range ''h''(''W'') of ''h'', which is only a subset of the codomain ''Z'' of ''h''.

★ By collapsing all arguments mapping to a given fixed image, every surjection induces a bijection defined on a quotient of its domain. More precisely, every surjection ''f'' : ''A'' → ''B'' 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 ''f''_''P'' : ''A''/~ → ''B'' be the well-defined function given by ''f''_''P''([''x'']_~) = ''f''(''x''). Then ''f'' = ''f''_''P'' o ''P''(~).

★ If ''f'': ''X'' → ''Y'' is a surjective function, then ''X'' has at least as many elements as ''Y'', in the sense of cardinal numbers.

★ If both ''X'' and ''Y'' are finite with the same number of elements, then ''f'' : ''X'' → ''Y'' is surjective if and only if ''f'' is injective.

See also

★ bijective function

Category theory view

In the language of category theory, surjective functions are precisely the epimorphisms in the category of sets.