Home > Surjection

More formally, a function f: X → Y is surjective 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, f is surjective if its range f(X) is equal to the codomain Y, or equivalently, if every element in the codomain has a preimage.

.

1 Examples and counterexamples

On the other hand, 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 we define the function h: R → [0, ∞) by the same formula as g, but with the codomain 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 = x² to get solutions x = √y and x = −√y.

2 Properties

• A function f: X → Y is surjective if and only if there exists a function g: Y → X such that f o g equals the identity function on Y. (This statement is equivalent to the axiom of choice.)
• By definition, 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.
• 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 ⁻¹(B)) = B. Thus, B can be recovered from its preimage f ⁻¹(B).
• Every function h: X → 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 f: X → Y is a surjective function, then X has at least as many elements as Y, in the sense of cardinal numberAlternative meaning: number of pitch classes in a set. In linguistics, cardinal numbers is the name given to number words that are used for quantity one two three , as opposed to ordinal numbers, words that are used for order first second third . See Hows. (This statement is also equivalent to the axiom of choice.)
• If both X and Y are finiteIn mathematics, a set is called finite if and only if there is a bijection between the set and some set of the form {1, 2,. n with n isin N . It is a theorem that a set is finite if and only if there exists no bijection between the set and any of its prop with the same number of elements, then f : X → Y is surjective if and only if f is injective.