TheInfoList

In
mathematics Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained (geometry), and quantities and their changes (cal ...
, a surjective function (also known as surjection, or onto function) is a
function Function or functionality may refer to: Computing * Function key A function key is a key on a computer A computer is a machine that can be programmed to carry out sequences of arithmetic or logical operations automatically. Modern comp ...
that maps an element to every element ; that is, for every , there is an such that . In other words, every element of the function's
codomain In mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), and calculus, change (mathematical analysis, analysis). It ...

is the
image An image (from la, imago) is an artifact that depicts visual perception Visual perception is the ability to interpret the surrounding environment Environment most often refers to: __NOTOC__ * Natural environment, all living and non- ...
of one element of its
domain Domain may refer to: Mathematics *Domain of a function, the set of input values for which the (total) function is defined **Domain of definition of a partial function **Natural domain of a partial function **Domain of holomorphy of a function *Doma ...
. It is not required that be unique; the function may map one or more elements of to the same element of . The term ''surjective'' and the related terms ''
injective In mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), and calculus, change (mathematical analysis, analysis). I ...

'' and ''
bijective In mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), and calculus, change (mathematical analysis, analysis). It ...
'' were introduced by
Nicolas Bourbaki Nicolas Bourbaki () is the collective pseudonym of a group of mathematicians, predominantly French alumni of the École normale supérieure (Paris), École normale supérieure (ENS). Founded in 1934–1935, the Bourbaki group originally intended ...
, a group of mainly 20th-century
mathematician A mathematician is someone who uses an extensive knowledge of mathematics Mathematics (from Greek: ) includes the study of such topics as numbers ( and ), formulas and related structures (), shapes and spaces in which they are contained ( ...

s who, under this pseudonym, wrote a series of books presenting an exposition of modern advanced mathematics, beginning in 1935. The French word '' sur'' means ''over'' or ''above'', and relates to the fact that the
image An image (from la, imago) is an artifact that depicts visual perception Visual perception is the ability to interpret the surrounding environment Environment most often refers to: __NOTOC__ * Natural environment, all living and non- ...
of the domain of a surjective function completely covers the function's codomain. Any function induces a surjection by restricting its codomain to the image of its domain. Every surjective function has a right inverse, and every function with a right inverse is necessarily a surjection. The
composition Composition or Compositions may refer to: Arts * Composition (dance), practice and teaching of choreography * Composition (music), an original piece of music and its creation *Composition (visual arts) The term composition means "putting togethe ...
of surjective functions is always surjective. Any function can be decomposed into a surjection and an injection.

# Definition

A surjective function is a
function Function or functionality may refer to: Computing * Function key A function key is a key on a computer A computer is a machine that can be programmed to carry out sequences of arithmetic or logical operations automatically. Modern comp ...
whose
image An image (from la, imago) is an artifact that depicts visual perception Visual perception is the ability to interpret the surrounding environment Environment most often refers to: __NOTOC__ * Natural environment, all living and non- ...
is equal to its
codomain In mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), and calculus, change (mathematical analysis, analysis). It ...

. Equivalently, a function $f$ with
domain Domain may refer to: Mathematics *Domain of a function, the set of input values for which the (total) function is defined **Domain of definition of a partial function **Natural domain of a partial function **Domain of holomorphy of a function *Doma ...
$X$ and codomain $Y$ is surjective if for every $y$ in $Y$ there exists at least one $x$ in $X$ with $f\left(x\right)=y$. Surjections are sometimes denoted by a two-headed rightwards arrow (), as in $f\colon X\twoheadrightarrow Y$. Symbolically, :If $f\colon X \rightarrow Y$, then $f$ is said to be surjective if :$\forall y \in Y, \, \exists x \in X, \;\; f\left(x\right)=y$.

# Examples

* For any set ''X'', the
identity function Graph of the identity function on the real numbers In mathematics, an identity function, also called an identity relation, identity map or identity transformation, is a function (mathematics), function that always returns the same value that was ...

id''X'' on ''X'' is surjective. * The function defined by ''f''(''n'') = ''n'' mod 2 (that is, even
integer An integer (from the Latin Latin (, or , ) is a classical language belonging to the Italic branch of the Indo-European languages. Latin was originally spoken in the area around Rome, known as Latium. Through the power of the Roman Re ...
s are mapped to 0 and odd integers to 1) is surjective. * The function defined by ''f''(''x'') = 2''x'' + 1 is surjective (and even
bijective In mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), and calculus, change (mathematical analysis, analysis). It ...
), because for every
real number In mathematics Mathematics (from Greek: ) includes the study of such topics as numbers ( and ), formulas and related structures (), shapes and spaces in which they are contained (), and quantities and their changes ( and ). There is no g ...
''y'', we have an ''x'' such that ''f''(''x'') = ''y'': such an appropriate ''x'' is (''y'' − 1)/2. * The function defined by ''f''(''x'') = ''x''3 − 3''x'' is surjective, because the pre-image of any
real number In mathematics Mathematics (from Greek: ) includes the study of such topics as numbers ( and ), formulas and related structures (), shapes and spaces in which they are contained (), and quantities and their changes ( and ). There is no g ...
''y'' is the solution set of the cubic polynomial equation ''x''3 − 3''x'' − ''y'' = 0, and every cubic polynomial with real coefficients has at least one real root. However, this function is not
injective In mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), and calculus, change (mathematical analysis, analysis). I ...

(and hence not
bijective In mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), and calculus, change (mathematical analysis, analysis). It ...
), since, for example, the pre-image of ''y'' = 2 is . (In fact, the pre-image of this function for every ''y'', −2 ≤ ''y'' ≤ 2 has more than one element.) * The function defined by ''g''(''x'') = ''x''2 is ''not'' surjective, since there is no real number ''x'' such that ''x''2 = −1. However, the function defined by (with the restricted codomain) ''is'' surjective, since for every ''y'' in the nonnegative real codomain ''Y'', there is at least one ''x'' in the real domain ''X'' such that ''x''2 = ''y''. * The
natural logarithm The natural logarithm of a number is its logarithm to the base (exponentiation), base of the mathematical constant , which is an Irrational number, irrational and Transcendental number, transcendental number approximately equal to . The natura ...
function is a surjective and even bijective (mapping from the set of positive real numbers to the set of all real numbers). Its inverse, the
exponential function The exponential function is a mathematical function Function or functionality may refer to: Computing * Function key A function key is a key on a computer A computer is a machine that can be programmed to carry out sequences of ...

, if defined with the set of real numbers as the domain, is not surjective (as its range is the set of positive real numbers). * The
matrix exponential In mathematics Mathematics (from Greek: ) includes the study of such topics as numbers ( and ), formulas and related structures (), shapes and spaces in which they are contained (), and quantities and their changes ( and ). There is no gene ...
is not surjective when seen as a map from the space of all ''n''×''n''
matrices Matrix or MATRIX may refer to: Science and mathematics * Matrix (mathematics) In mathematics, a matrix (plural matrices) is a rectangle, rectangular ''wikt:array, array'' or ''table'' of numbers, symbol (formal), symbols, or expression (mathema ...
to itself. It is, however, usually defined as a map from the space of all ''n''×''n'' matrices to the
general linear group In mathematics Mathematics (from Greek: ) includes the study of such topics as numbers ( and ), formulas and related structures (), shapes and spaces in which they are contained (), and quantities and their changes ( and ). There is no ge ...
of degree ''n'' (that is, the
group A group is a number A number is a mathematical object used to counting, count, measurement, measure, and nominal number, label. The original examples are the natural numbers 1, 2, 3, 4, and so forth. Numbers can be represented in language with ...
of all ''n''×''n''
invertible matrices In linear algebra Linear algebra is the branch of mathematics concerning linear equations such as: :a_1x_1+\cdots +a_nx_n=b, linear maps such as: :(x_1, \ldots, x_n) \mapsto a_1x_1+\cdots +a_nx_n, and their representations in vector spaces and t ...
). Under this definition, the matrix exponential is surjective for complex matrices, although still not surjective for real matrices. * The projection from a
cartesian product In mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), and calculus, change (mathematical analysis, analysis). I ...
to one of its factors is surjective, unless the other factor is empty. * In a 3D video game, vectors are projected onto a 2D flat screen by means of a surjective function.

# Properties

A function is
bijective In mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), and calculus, change (mathematical analysis, analysis). It ...
if and only if it is both surjective and
injective In mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), and calculus, change (mathematical analysis, analysis). I ...

. If (as is often done) a function is identified with its
graph Graph may refer to: Mathematics *Graph (discrete mathematics), a structure made of vertices and edges **Graph theory, the study of such graphs and their properties *Graph (topology), a topological space resembling a graph in the sense of discret ...

, then surjectivity is not a property of the function itself, but rather a property of the
mapping Mapping may refer to: * Mapping (cartography), the process of making a map * Mapping (mathematics), a synonym for a mathematical function and its generalizations ** Mapping (logic), a synonym for functional predicate Types of mapping * Animated ...
. This is, the function together with its codomain. Unlike injectivity, surjectivity cannot be read off of the graph of the function alone.

## Surjections as right invertible functions

The function is said to be a right inverse of the function if ''f''(''g''(''y'')) = ''y'' for every ''y'' in ''Y'' (''g'' can be undone by ''f''). In other words, ''g'' is a right inverse of ''f'' if the
composition Composition or Compositions may refer to: Arts * Composition (dance), practice and teaching of choreography * Composition (music), an original piece of music and its creation *Composition (visual arts) The term composition means "putting togethe ...
of ''g'' and ''f'' in that order is the
identity function Graph of the identity function on the real numbers In mathematics, an identity function, also called an identity relation, identity map or identity transformation, is a function (mathematics), function that always returns the same value that was ...

on the domain ''Y'' of ''g''. The function ''g'' need not be a complete
inverse Inverse or invert may refer to: Science and mathematics * Inverse (logic), a type of conditional sentence which is an immediate inference made from another conditional sentence * Additive inverse (negation), the inverse of a number that, when add ...
of ''f'' because the composition in the other order, , may not be the identity function on the domain ''X'' of ''f''. In other words, ''f'' can undo or "''reverse''" ''g'', but cannot necessarily be reversed by it. Every function with a right inverse is necessarily a surjection. The proposition that every surjective function has a right inverse is equivalent to the
axiom of choice In , the axiom of choice, or AC, is an of equivalent to the statement that ''a of a collection of non-empty sets is non-empty''. Informally put, the axiom of choice says that given any collection of bins, each containing at least one object ...

. If is surjective and ''B'' is a
subset In mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), and calculus, change (mathematical analysis, analysis). ...

of ''Y'', then ''f''(''f'' −1(''B'')) = ''B''. Thus, ''B'' can be recovered from its
preimage In mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), and calculus, change (mathematical analysis, analysis). ...
. For example, in the first illustration above, there is some function ''g'' such that ''g''(''C'') = 4. There is also some function ''f'' such that ''f''(4) = ''C''. It doesn't matter that ''g''(''C'') can also equal 3; it only matters that ''f'' "reverses" ''g''. File:Surjective composition.svg, Surjective composition: the first function need not be surjective. File:Bijection.svg, Another surjective function. (This one happens to be a
bijection In , a bijection, bijective function, one-to-one correspondence, or invertible function, is a between the elements of two , where each element of one set is paired with exactly one element of the other set, and each element of the other set is p ...
) File:Injection.svg, A non-surjective function. (This one happens to be an
injection Injection or injected may refer to: Science and technology * Injection (medicine) An injection (often referred to as a "shot" in US English, a "jab" in UK English, or a "jag" in Scottish English and Scots Language, Scots) is the act of adminis ...

)

## Surjections as epimorphisms

A function is surjective if and only if it is
right-cancellative In mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), and calculus, change (mathematical analysis, analysis). It ...
: given any functions , whenever ''g'' o ''f'' = ''h'' o ''f'', then ''g'' = ''h''. This property is formulated in terms of functions and their
composition Composition or Compositions may refer to: Arts * Composition (dance), practice and teaching of choreography * Composition (music), an original piece of music and its creation *Composition (visual arts) The term composition means "putting togethe ...
and can be generalized to the more general notion of the
morphism In mathematics Mathematics (from Greek: ) includes the study of such topics as numbers ( and ), formulas and related structures (), shapes and spaces in which they are contained (), and quantities and their changes ( and ). There is no gener ...

s of a
category Category, plural categories, may refer to: Philosophy and general uses *Categorization Categorization is the ability and activity to recognize shared features or similarities between the elements of the experience of the world (such as O ...
and their composition. Right-cancellative morphisms are called
epimorphism 220px In category theory Category theory formalizes mathematical structure and its concepts in terms of a Graph labeling, labeled directed graph called a ''Category (mathematics), category'', whose nodes are called ''objects'', and whose labe ...
s. Specifically, surjective functions are precisely the epimorphisms in the
category of setsIn the mathematical Mathematics (from Greek Greek may refer to: Greece Anything of, from, or related to Greece Greece ( el, Ελλάδα, , ), officially the Hellenic Republic, is a country located in Southeast Europe. Its population is ...
. The prefix ''epi'' is derived from the Greek preposition ''ἐπί'' meaning ''over'', ''above'', ''on''. Any morphism with a right inverse is an epimorphism, but the converse is not true in general. A right inverse ''g'' of a morphism ''f'' is called a
section Section, Sectioning or Sectioned may refer to: Arts, entertainment and media * Section (music), a complete, but not independent, musical idea * Section (typography), a subdivision, especially of a chapter, in books and documents ** Section sign ...
of ''f''. A morphism with a right inverse is called a split epimorphism.

## Surjections as binary relations

Any function with domain ''X'' and codomain ''Y'' can be seen as a left-total and right-unique binary relation between ''X'' and ''Y'' by identifying it with its
function graph In mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), and calculus, change (mathematical analysis, analysis). ...
. A surjective function with domain ''X'' and codomain ''Y'' is then a binary relation between ''X'' and ''Y'' that is right-unique and both left-total and right-total.

## Cardinality of the domain of a surjection

The
cardinality In mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), and calculus, change (mathematical analysis, analysis). It ...
of the domain of a surjective function is greater than or equal to the cardinality of its codomain: If is a surjective function, then ''X'' has at least as many elements as ''Y'', in the sense of
cardinal number 150px, Aleph null, the smallest infinite cardinal In mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), and ca ...
s. (The proof appeals to the
axiom of choice In , the axiom of choice, or AC, is an of equivalent to the statement that ''a of a collection of non-empty sets is non-empty''. Informally put, the axiom of choice says that given any collection of bins, each containing at least one object ...

to show that a function satisfying ''f''(''g''(''y'')) = ''y'' for all ''y'' in ''Y'' exists. ''g'' is easily seen to be injective, thus the
formal definition Formal, formality, informal or informality imply the complying with, or not complying with, some set of requirements (form Form is the shape, visual appearance, or :wikt:configuration, configuration of an object. In a wider sense, the form is the ...
of , ''Y'', ≤ , ''X'', is satisfied.) Specifically, if both ''X'' and ''Y'' are
finite Finite is the opposite of Infinity, infinite. It may refer to: * Finite number (disambiguation) * Finite set, a set whose cardinality (number of elements) is some natural number * Finite verb, a verb form that has a subject, usually being inflected ...
with the same number of elements, then is surjective if and only if ''f'' is
injective In mathematics Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained (geometry), and quantities and ...
. Given two sets ''X'' and ''Y'', the notation is used to say that either ''X'' is empty or that there is a surjection from ''Y'' onto ''X''. Using the axiom of choice one can show that and together imply that , ''Y'', = , ''X'', , a variant of the
Schröder–Bernstein theoremIn set theory, the Schröder–Bernstein theorem states that, if there exist injective functions and between the Set (mathematics), sets and , then there exists a bijection, bijective function . In terms of the cardinality of the two sets, this c ...
.

## Composition and decomposition

The
composition Composition or Compositions may refer to: Arts * Composition (dance), practice and teaching of choreography * Composition (music), an original piece of music and its creation *Composition (visual arts) The term composition means "putting togethe ...
of surjective functions is always surjective: If ''f'' and ''g'' are both surjective, and the codomain of ''g'' is equal to the domain of ''f'', then is surjective. Conversely, if is surjective, then ''f'' is surjective (but ''g'', the function applied first, need not be). These properties generalize from surjections in the
category of setsIn the mathematical Mathematics (from Greek Greek may refer to: Greece Anything of, from, or related to Greece Greece ( el, Ελλάδα, , ), officially the Hellenic Republic, is a country located in Southeast Europe. Its population is ...
to any
epimorphism 220px In category theory Category theory formalizes mathematical structure and its concepts in terms of a Graph labeling, labeled directed graph called a ''Category (mathematics), category'', whose nodes are called ''objects'', and whose labe ...
s in any
category Category, plural categories, may refer to: Philosophy and general uses *Categorization Categorization is the ability and activity to recognize shared features or similarities between the elements of the experience of the world (such as O ...
. Any function can be decomposed into a surjection and an
injection Injection or injected may refer to: Science and technology * Injection (medicine) An injection (often referred to as a "shot" in US English, a "jab" in UK English, or a "jag" in Scottish English and Scots Language, Scots) is the act of adminis ...

: For any function there exist a surjection and an injection such that ''h'' = ''g'' o ''f''. To see this, define ''Y'' to be the set of
preimage In mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), and calculus, change (mathematical analysis, analysis). ...
s where ''z'' is in . These preimages are and ''X''. Then ''f'' carries each ''x'' to the element of ''Y'' which contains it, and ''g'' carries each element of ''Y'' to the point in ''Z'' to which ''h'' sends its points. Then ''f'' is surjective since it is a projection map, and ''g'' is injective by definition.

## Induced surjection and induced bijection

Any function induces a surjection by restricting its codomain to its range. Any surjective function induces a bijection defined on a
quotient In arithmetic Arithmetic (from the Ancient Greek, Greek wikt:en:ἀριθμός#Ancient Greek, ἀριθμός ''arithmos'', 'number' and wikt:en:τική#Ancient Greek, τική wikt:en:τέχνη#Ancient Greek, έχνη ''tiké échne' ...
of its domain by collapsing all arguments mapping to a given fixed image. More precisely, every surjection can be factored as a projection followed by a bijection as follows. Let ''A''/~ be the
equivalence class In mathematics Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained (geometry), and quantities an ...
es of ''A'' under the following
equivalence relation In mathematics Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained (geometry), and quantities a ...
: ''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 In mathematics, a projection is a mapping of a Set (mathematics), set (or other mathematical structure) into a subset (or sub-structure), which is equal to its square for function composition, mapping composition (or, in other words, which is idem ...
which sends each ''x'' in ''A'' to its equivalence class 'x''sub>~, and let ''f''''P'' : ''A''/~ → ''B'' be the well-defined function given by ''f''''P''( 'x''sub>~) = ''f''(''x''). Then ''f'' = ''f''''P'' o ''P''(~).

# Space of surjections

Given fixed and , one can form the set of surjections . The
cardinality In mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), and calculus, change (mathematical analysis, analysis). It ...
of this set is one of the twelve aspects of Rota's
Twelvefold way In combinatorics Combinatorics is an area of mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), and calculus, ...
, and is given by $, B, !\begin, A, \\, B, \end$, where $\begin, A, \\, B, \end$ denotes a
Stirling number of the second kind In mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), and calculus, change (mathematical analysis, analysis). It ...
.

*
Bijection, injection and surjection In mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), and calculus, change (mathematical analysis, analysis). ...
* Cover (algebra) *
Covering map In mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), and calculus, change (mathematical analysis, analysis). ...

*
Enumeration An enumeration is a complete, ordered listing of all the items in a collection. The term is commonly used in mathematics Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and r ...
*
Fiber bundle In mathematics, and particularly topology, a fiber bundle (or, in English in the Commonwealth of Nations, Commonwealth English: fibre bundle) is a Space (mathematics), space that is ''locally'' a product space, but ''globally'' may have a dif ...
*
Index set In mathematics, an index set is a set whose members label (or index) members of another set. For instance, if the elements of a Set (mathematics), set may be ''indexed'' or ''labeled'' by means of the elements of a set , then is an index set. Th ...
*
Section (category theory) In category theory Category theory formalizes mathematical structure In mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), s ...

# References

* {{Cite book , title=Theory of Sets , last=Bourbaki , first=N. , author-link=Nicolas Bourbaki , year=2004 , orig-year=1968 , publisher=Springer , isbn=978-3-540-22525-6 , doi=10.1007/978-3-642-59309-3 , lccn=2004110815 , series= , volume=1 , url=https://books.google.com/books?id=7eclBQAAQBAJ&pg=PR1 , ref=bourbaki Functions and mappings
Basic concepts in set theory{{Commons This category is for the foundational concepts of naive set theory, in terms of which contemporary mathematics is typically expressed. Mathematical concepts ...
Mathematical relations Types of functions