A surjective function.

Another surjective function.

A non-surjective function.

Surjective composition: the first function need not be surjective.

In mathematics, a function f is said to be surjective 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. Image File history File links Surjection. ... Image File history File links Surjection. ... Image File history File links Bijection. ... Image File history File links Bijection. ... Image File history File links Injection. ... Image File history File links Injection. ... Image File history File links Surjective_composition. ... Image File history File links Surjective_composition. ... Euclid, Greek mathematician, 3rd century BC, as imagined by by Raphael in this detail from The School of Athens. ... Graph of example function, The mathematical concept of a function expresses the intuitive idea of deterministic dependence between two quantities, one of which is viewed as primary (the independent variable, argument of the function, or its input) and the other as secondary (the value of the function, or output). A... A codomain in mathematics is the set of output values associated with (or mapped to) the domain of inputs in a function. ... In mathematics, the domain of a function is the set of all input values to the function. ...

Said another way, a function f: X → 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 also said to be onto.

Examples and a counterexample

• For any set X, the identity function id_X on X is surjective.
• The function f: R → 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 f: Z → {0,1,2,3} defined by f(x) = x mod 4 is surjective.
• 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 the codomain is defined as [0,+∞), then g is surjective.

The natural logarithm, formerly known as the hyperbolic logarithm, is the logarithm to the base e, where e is equal to 2. ... Modular arithmetic (sometimes called modulo arithmetic, or clock arithmetic because of its use in the 24-hour clock system) is a system of arithmetic for integers, where numbers wrap around after they reach a certain value — the modulus. ...

There always exists a function "reversible" by a surjection

A surjection can be also defined as a function that can undo another function. A function f: X → Y is surjective if and only if there exists a function g: Y → X such that, for every This article does not cite any references or sources. ...

(g can be undone by f)

that is a function g such that f o g equals the identity function on Y (cf. with definition of inverse function). An identity function f is a function which doesnt have any effect: it always returns the same value that was used as its argument. ... In mathematics, an inverse function is in simple terms a function which does the reverse of a given function. ...

Note that g may not be a complete inverse of f because the composition in the other order, g o f, may not be the identity on X. In other words, f can undo or "reverse" g, but not necessarily can be reversed by it. Surjections are not always invertible (bijective). In mathematics, an inverse function is in simple terms a function which does the reverse of a given function. ... In mathematics, an inverse function is in simple terms a function which does the reverse of a given function. ... In mathematics, a bijection, bijective function, or one-to-one correspondence is a function that is both injective (one-to-one) and surjective (onto), and therefore bijections are also called one_to_one and onto. ...

Other properties

• If f and g are both surjective, then f o g is surjective.
• If f o g is surjective, then f is surjective (but g may not be).
• 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 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 : A → B 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(~) : A → A/~ be the projection map which sends each x in A to its equivalence class [x]_~, and let f_P : A/~ → B be the well-defined function given by f_P([x]_~) = f(x). Then f = f_P o P(~).
• If f: X → 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.

In category theory an epimorphism (also called an epic morphism or an epi) is a morphism f : X → Y which is right-cancellable in the following sense: g1 o f = g2 o f implies g1 = g2 for all morphisms g1, g2 : Y → Z. Epimorphisms are analogues of surjective functions, but... In mathematics, category theory deals in an abstract way with mathematical structures and relationships between them. ... In mathematics, the category of sets is the category whose objects are all sets and whose morphisms are all functions. ... A is a subset of B, and B is a superset of A. In mathematics, especially in set theory, the terms, subset, superset and proper (or strict) subset or superset are used to describe the relation, called inclusion, of one set being contained inside another set. ... In mathematics, the image of an element x in a set X under the function f : X → Y, denoted by f(x), is the unique y in Y that is associated with x. ... An injective function. ... In mathematics, the term up to xxxx is used to describe a situation in which members of an equivalence class can be regarded as a single entity for some purpose. ... Aleph-0, the smallest infinite cardinal In mathematics, cardinal numbers, or cardinals for short, are a generalized kind of number used to denote the size of a set. ... In mathematics, a set is called finite if there is a bijection between the set and some set of the form {1, 2, ..., n} where is a natural number. ... In mathematics, an injective function (or one-to-one function or injection) is a function which maps distinct input values to distinct output values. ...

See also

Look up surjective, surjection, onto in Wiktionary, the free dictionary.

• bijective function

Wikipedia does not have an article with this exact name. ... Wiktionary (a portmanteau of wiki and dictionary) is a multilingual, Web-based project to create a free content dictionary, available in over 150 languages. ... A bijective function. ...

Category theory view

In the language of category theory, surjective functions are precisely the epimorphisms in the category of sets. In mathematics, category theory deals in an abstract way with mathematical structures and relationships between them. ... In category theory an epimorphism (also called an epic morphism or an epi) is a morphism f : X → Y which is right-cancellable in the following sense: g1 o f = g2 o f implies g1 = g2 for all morphisms g1, g2 : Y → Z. Epimorphisms are analogues of surjective functions, but... In mathematics, the category of sets is the category whose objects are all sets and whose morphisms are all functions. ...