Surjection

From Example Problems
(Redirected from Surjective)
Jump to navigation Jump to search
Error creating thumbnail: Unable to save thumbnail to destination
A surjective function.
Error creating thumbnail: Unable to save thumbnail to destination
Another surjective function.
Error creating thumbnail: Unable to save thumbnail to destination
An non-surjective function.

In mathematics, a function f is said to be surjective if and only 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 fX → 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 said to be onto.

Examples and counterexamples

  • For any set X, the identity function idX on X is surjective.
  • The function fR → R defined by

f(x) = 2x + 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 gR → 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.
  • The function fZ → {0,1,2,3} defined by

f(x) = x mod 4 is surjective.

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.)
  • If f and g are both surjective, then f o g is surjective.
Error creating thumbnail: Unable to save thumbnail to destination
Surjective composition: the first function need not be surjective.
  • If f o g is surjective, then f is surjective (but g maynot be).
  • 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 Set 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 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 : AB 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(~) : AA/~ be the projection map which sends each x in A to its equivalence class [x]~, and let fP : A/~ → B be the well-defined function given by fP([x]~) = f(x). Then f = fP o P(~).
  • If fX → 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

Category theory view

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