kidzsearch.com > wiki Explore:web images videos games
Surjective function
Surjection. There is an arrow to every element in the codomain B from (at least) one element of the domain A. 
In mathematics, a surjective or onto function is a function f : A → B with the following property. For every element b in the codomain B there is at least one element a in the domain A such that f(a)=b. This means that the range and codomain of f are the same set.^{[1]}^{[2]}
The term surjection and the related terms injection and bijection were introduced by the group of mathematicians that called itself Nicholas Bourbaki.^{[3]} In the 1930's, this group of mathematicians published a series of books on modern advanced mathematics. The French prefix sur means above or onto and was chosen since a surjective function maps its domain on to its codomain.
Not a surjection. No element in the domain A is mapped to the element {4} in the codomain B. 
Contents
Basic properties
Formally:
 [math]f:A \rightarrow B[/math] is a surjective function if [math]\forall b \in B \,\, \exists a \in A[/math] such that [math]f(a)=b \,.[/math]
The element [math]b[/math] is called the image of the element [math]a[/math].
 The formal definition means: Every element of the codomain B is the image of at least one element in the domain A.
The element [math]a[/math] is called a preimage of the element [math]b[/math].
 The formal definition means: Every element of the codomain B has at least one preimage in the domain A.
A preimage does not have to be unique. In the top image, both {X} and {Y} are preimages of the element {1}. It is only important that there be at least one preimage. (See also: Injective function, Bijective function)
Examples
Elementary functions
Let f(x):ℝ→ℝ be a realvalued function y=f(x) of a realvalued argument x. (This means both the input and output are numbers.)
 Graphic meaning: The function f is a surjection if every horizontal line intersects the graph of f in at least one point.
 Analytic meaning: The function f is a surjection if for every real number y_{o} we can find at least one real number x_{o} such that y_{o}=f(x_{o}).
Finding a preimage x_{o} for a given y_{o} is equivalent to either question:
 Does the equation f(x)y_{o}=0 have a solution? or
 Does the function f(x)y_{o} have a root?
In mathematics, we can find exact (analytic) roots only of polynomials of first, second (and third) degree. We find roots of all other functions approximately (numerically). This means a formal proof of surjectivity is rarely direct. So the discussions below are informal.
Example: The linear function of a slanted line is onto. That is, y=ax+b where a≠0 is a surjection. (It is also an injection and thus a bijection.)
 Proof: Substitute y_{o} into the function and solve for x. Since a≠0 we get x= (y_{o}b)/_{a}. This means x_{o}=(y_{o}b)/_{a} is a preimage of y_{o}. This proves that the function y=ax+b where a≠0 is a surjection. (Since there is exactly one preimage, this function is also an injection.)
 Practical example: y= –2x+4. What is the preimage of y=2? Solution: Here a= –2, i.e. a≠0 and the question is: For what x is y=2? We substitute y=2 into the function. We get x=1, i.e. y(1)=2. So the answer is: x=1 is the preimage of y=2.
Example: The cubic polynomial (of third degree) f(x)=x^{3}3x is a surjection.
 Discussion: The cubic equation x^{3}3xy_{o}=0 has real coefficients (a_{3}=1, a_{2}=0, a_{1}=–3, a_{0}=–y_{o}). Every such cubic equation has at least one real root.^{[4]} Since the domain of the polynomial is ℝ, the means that ther is at least one preimage x_{o} in the domain. That is, (x_{0})^{3}3x_{0}y_{o}=0. So the function is a surjection. (However, this function is not an injection. For example, y_{o}=2 has 2 preimages: x=–1 and x=2. In fact, every y, –2≤y≤2 has at least 2 preimages.)
Example: The quadratic function f(x) = x^{2} is not a surjection. There is no x such that x^{2} = −1. The range of x² is [0,+∞) , that is, the set of nonnegative numbers. (Also, this function is not an injection.)
Note: One can make a nonsurjective function into a surjection by restricting its codomain to elements of its range. For example, the new function, f_{N}(x):ℝ → [0,+∞) where f_{N}(x) = x^{2} is a surjective function. (This is not the same as the restriction of a function which restricts the domain!)
Example: The exponential function f(x) = 10^{x} is not a surjection. The range of 10^{x} is (0,+∞), that is, the set of positive numbers. (This function is an injection.)
Other examples with realvalued functions
Example: The logarithmic function base 10 f(x):(0,+∞)→ℝ defined by f(x)=log(x) or y=log_{10}(x) is a surjection (and an injection). (This is the inverse function of 10^{x}.)
 The projection of a Cartesian product A × B onto one of its factors is a surjection.
Example: The function f((x,y)):ℝ²→ℝ defined by z=y is a surjection. Its graph is a plane in 3dimensional space. The preimage of z_{o} is the line y=z_{o} in the x0y plane.
 In 3D games, 3dimensional space is projected onto a 2dimensional screen with a surjection.
See also
References
 ↑ Weisstein, Eric. "Surjective function" (in English). From MathWorlda Wolfram Web Resource. http://mathworld.wolfram.com/Surjection.html. Retrieved January 2014.
 ↑ C.Clapham, J.Nicholson (2009). "Oxford Concise Dictionary of Mathematics, Onto Mapping" (in English). addisonWesley. p. 568. http://web.cortland.edu/matresearch/OxfordDictionaryMathematics.pdf. Retrieved January 2014.
 ↑ Miller, Jeff (2010). "Earliest Uses of Some of the Words of Mathematics" (in English). Tripod. http://jeff560.tripod.com/i.html. Retrieved February 2014.
 ↑ Tanton, James (2005). "Cubic equation". Encyclopedia of Mathematics. Facts on File, New York. p. 112113. . (English)
Other websites
 "Injective, Surjective, Bijective" (in English). 2013. http://www.mathsisfun.com/sets/injectivesurjectivebijective.html. Retrieved December 2013. interactive quiz
 "Injectivity, Surjectivity" (in English). Wolfram alpha. https://www.wolframalpha.com/examples/InjectivitySurjectivity.html. Retrieved December 2013. interactive

