Encyclopedia > SurJection

  Article Content

Surjection

Redirected from SurJection

A function fX → Y is called surjective or onto or a surjection if for every y in the codomain Y there is at least one x in the domain X with f(x) = y. Put another way, the range f(X) is equal to the codomain Y.


Surjective, not injective

Injective, not surjective

Bijective

Not surjective, not injective

When X and Y are both the real line R, then a surjective function fR → R can be visualized as one whose graph will be intersected by any horizontal line.

Examples and counterexamples

Consider the function fR → R defined by f(x) = 2x + 1. This function is surjective, since given an arbitrary real number y, we can solve y = 2x + 1 for x to get a solution x = (y − 1)/2.

On the other hand, the function gR → R defined by g(x) = x2 is not surjective, because (for example) there is no real number x such that x2 = -1.

However, if we define the function hR → R+ by the same formula as g, but with the codomain has been restricted to only the nonnegative real numbers, then the function h is surjective. This is because, given an arbitrary nonnegative real number y, we can solve y = x2 to get solutions x = √y and x = −√y.

Properties

  • A function fX → Y is surjective if and only if there exists a function gY → X such that f o g equals the identity function on Y. (This statement is equivalent to the axiom of choice.)
  • A function is bijective if and only if it is both surjective and injective.
  • If f o g is surjective, then f is surjective.
  • If f and g are both surjective, then f o g is surjective.
  • fX → 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 of sets.
  • If fX → 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 hX → Z can be decomposed as h = g o f for a suitable surjection f and injection 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.
  • If fX → Y is a surjective function, then X has at least as many elements as Y, in the sense of cardinal numbers. (This statement is also equivalent to the axiom of choice.)


See also: Injective function, Bijection



All Wikipedia text is available under the terms of the GNU Free Documentation License

 
  Search Encyclopedia

Search over one million articles, find something about almost anything!
 
 
  
  Featured Article
Autocracy

... - Wikipedia <<Up     Contents Autocracy Autocracy is a form of government which resides in the absolute power of a single individual. The term ...

 
 
 
This page was created in 47.9 ms