SURJECTIVE FUNCTION
- + Add to Faves
- + Translate
- + Share
العربية
ä¸å›½
Français
Deutsch
Ελληνική
हिनà¥à¤¦à¥€
Italiano
日本語
Português
РуÑÑкий
Español
(Redirected from Surjection)
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'.
★ 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.
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
: (''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).
★ 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'' −1(''B'')) = ''B''. Thus, ''B'' can be recovered from its preimage ''f'' −1(''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.
★ bijective function
In the language of category theory, surjective functions are precisely the epimorphisms in the category of sets.
A surjective function.
Another surjective function.
A 'non'-surjective function.
Surjective composition: the first function need not be surjective.
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:
★ 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
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
: (''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'' −1(''B'')) = ''B''. Thus, ''B'' can be recovered from its preimage ''f'' −1(''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.
This article provided by Wikipedia. To edit the contents of this article, click here for original source.
psst.. try this: add to faves
