Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of Graph Search.
Concept
Surjective function
Summary
In mathematics, a surjective function (also known as surjection, or onto function ˈɒn.tuː) is a function f such that every element y can be mapped from some element x such that f(x) = y. In other words, every element of the function's codomain is the of one element of its domain. It is not required that x be unique; the function f may map one or more elements of X to the same element of Y.
The term surjective and the related terms injective and bijective were introduced by Nicolas Bourbaki, a group of mainly French 20th-century mathematicians who, under this pseudonym, wrote a series of books presenting an exposition of modern advanced mathematics, beginning in 1935. The French word sur means over or above, and relates to the fact that the of the domain of a surjective function completely covers the function's codomain.
Any function induces a surjection by restricting its codomain to the image of its domain. Every surjective function has a right inverse assuming the axiom of choice, and every function with a right inverse is necessarily a surjection. The composition of surjective functions is always surjective. Any function can be decomposed into a surjection and an injection.
A surjective function is a function whose is equal to its codomain. Equivalently, a function with domain and codomain is surjective if for every in there exists at least one in with . Surjections are sometimes denoted by a two-headed rightwards arrow (), as in .
Symbolically,
If , then is said to be surjective if
For any set X, the identity function idX on X is surjective.
The function f : Z → {0, 1} defined by f(n) = n mod 2 (that is, even integers are mapped to 0 and odd integers to 1) is surjective.
The function f : R → R defined by f(x) = 2x + 1 is surjective (and even bijective), because for every real number y, we have an x such that f(x) = y: such an appropriate x is (y − 1)/2.
The function f : R → R defined by f(x) = x3 − 3x is surjective, because the pre-image of any real number y is the solution set of the cubic polynomial equation x3 − 3x − y = 0, and every cubic polynomial with real coefficients has at least one real root.
Official source
About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.