HOME

TheInfoList



OR:

In
mathematics Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...
, a surjective function (also known as surjection, or onto function) is a function that every element can be mapped from element so that . In other words, every element of the function's
codomain In mathematics, the codomain or set of destination of a function is the set into which all of the output of the function is constrained to fall. It is the set in the notation . The term range is sometimes ambiguously used to refer to either the ...
is the
image An image is a visual representation of something. It can be two-dimensional, three-dimensional, or somehow otherwise feed into the visual system to convey information. An image can be an artifact, such as a photograph or other two-dimension ...
of one element of its domain. 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'' and ''
bijective In mathematics, a bijection, also known as a bijective function, one-to-one correspondence, or invertible function, is a function between the elements of two sets, where each element of one set is paired with exactly one element of the other ...
'' were introduced by Nicolas Bourbaki, a group of mainly French 20th-century
mathematician A mathematician is someone who uses an extensive knowledge of mathematics in their work, typically to solve mathematical problems. Mathematicians are concerned with numbers, data, quantity, structure, space, models, and change. History ...
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 is a visual representation of something. It can be two-dimensional, three-dimensional, or somehow otherwise feed into the visual system to convey information. An image can be an artifact, such as a photograph or other two-dimension ...
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 assuming the axiom of choice, and every function with a right inverse is necessarily a surjection. The
composition Composition or Compositions may refer to: Arts and literature *Composition (dance), practice and teaching of choreography * Composition (language), in literature and rhetoric, producing a work in spoken tradition and written discourse, to include ...
of surjective functions is always surjective. Any function can be decomposed into a surjection and an injection.


Definition

A surjective function is a function whose
image An image is a visual representation of something. It can be two-dimensional, three-dimensional, or somehow otherwise feed into the visual system to convey information. An image can be an artifact, such as a photograph or other two-dimension ...
is equal to its
codomain In mathematics, the codomain or set of destination of a function is the set into which all of the output of the function is constrained to fall. It is the set in the notation . The term range is sometimes ambiguously used to refer to either the ...
. Equivalently, a function f with domain X and codomain Y is surjective if for every y in Y there exists at least one x in X with f(x)=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 and only if :\forall y \in Y, \, \exists x \in X, \;\; f(x)=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 that always returns the value that was used as its argument, unc ...
id''X'' on ''X'' is surjective. * The function defined by ''f''(''n'') = ''n'' mod 2 (that is, even
integer An integer is the number zero (), a positive natural number (, , , etc.) or a negative integer with a minus sign (−1, −2, −3, etc.). The negative numbers are the additive inverses of the corresponding positive numbers. In the language o ...
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, a bijection, also known as a bijective function, one-to-one correspondence, or invertible function, is a function between the elements of two sets, where each element of one set is paired with exactly one element of the other ...
), because for every
real number In mathematics, a real number is a number that can be used to measure a ''continuous'' one-dimensional quantity such as a distance, duration or temperature. Here, ''continuous'' means that values can have arbitrarily small variations. Every ...
''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, a real number is a number that can be used to measure a ''continuous'' one-dimensional quantity such as a distance, duration or temperature. Here, ''continuous'' means that values can have arbitrarily small variations. Every ...
''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 (and hence not
bijective In mathematics, a bijection, also known as a bijective function, one-to-one correspondence, or invertible function, is a function between the elements of two sets, where each element of one set is paired with exactly one element of the other ...
), 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 of the mathematical constant , which is an irrational and transcendental number approximately equal to . The natural logarithm of is generally written as , , or sometimes, if ...
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 denoted by f(x)=\exp(x) or e^x (where the argument is written as an exponent). Unless otherwise specified, the term generally refers to the positive-valued function of a real variable, a ...
, 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 is not surjective when seen as a map from the space of all ''n''×''n'' matrices 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, the general linear group of degree ''n'' is the set of invertible matrices, together with the operation of ordinary matrix multiplication. This forms a group, because the product of two invertible matrices is again invertible, ...
of degree ''n'' (that is, the group of all ''n''×''n'' invertible matrices). 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, specifically set theory, the Cartesian product of two sets ''A'' and ''B'', denoted ''A''×''B'', is the set of all ordered pairs where ''a'' is in ''A'' and ''b'' is in ''B''. In terms of set-builder notation, that is : A\tim ...
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, a bijection, also known as a bijective function, one-to-one correspondence, or invertible function, is a function between the elements of two sets, where each element of one set is paired with exactly one element of the other ...
if and only if it is both surjective and injective. If (as is often done) a function is identified with its graph, then surjectivity is not a property of the function itself, but rather a property of the mapping. 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 and literature *Composition (dance), practice and teaching of choreography * Composition (language), in literature and rhetoric, producing a work in spoken tradition and written discourse, to include ...
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 that always returns the value that was used as its argument, unc ...
on the domain ''Y'' of ''g''. The function ''g'' need not be a complete inverse 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. If is surjective and ''B'' is a
subset In mathematics, set ''A'' is a subset of a set ''B'' if all elements of ''A'' are also elements of ''B''; ''B'' is then a superset of ''A''. It is possible for ''A'' and ''B'' to be equal; if they are unequal, then ''A'' is a proper subset o ...
of ''Y'', then ''f''(''f'' −1(''B'')) = ''B''. Thus, ''B'' can be recovered from its
preimage In mathematics, the image of a function is the set of all output values it may produce. More generally, evaluating a given function f at each element of a given subset A of its domain produces a set, called the "image of A under (or through ...
. 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''.


Surjections as epimorphisms

A function is surjective if and only if it is right-cancellative: 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 and literature *Composition (dance), practice and teaching of choreography * Composition (language), in literature and rhetoric, producing a work in spoken tradition and written discourse, to include ...
and can be generalized to the more general notion of the
morphism In mathematics, particularly in category theory, a morphism is a structure-preserving map from one mathematical structure to another one of the same type. The notion of morphism recurs in much of contemporary mathematics. In set theory, morphisms a ...
s of a
category Category, plural categories, may refer to: Philosophy and general uses *Categorization, categories in cognitive science, information science and generally *Category of being * ''Categories'' (Aristotle) * Category (Kant) * Categories (Peirce) ...
and their composition. Right-cancellative morphisms are called epimorphisms. Specifically, surjective functions are precisely the epimorphisms in the category of sets. 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 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. 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, the cardinality of a set is a measure of the number of elements of the set. For example, the set A = \ contains 3 elements, and therefore A has a cardinality of 3. Beginning in the late 19th century, this concept was generalized ...
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 In mathematics, cardinal numbers, or cardinals for short, are a generalization of the natural numbers used to measure the cardinality (size) of sets. The cardinality of a finite set is a natural number: the number of elements in the set. The ...
s. (The proof appeals to the axiom of choice 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 of , ''Y'', ≤ , ''X'', is satisfied.) Specifically, if both ''X'' and ''Y'' are finite with the same number of elements, then is surjective if and only if ''f'' is injective. 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 theorem.


Composition and decomposition

The
composition Composition or Compositions may refer to: Arts and literature *Composition (dance), practice and teaching of choreography * Composition (language), in literature and rhetoric, producing a work in spoken tradition and written discourse, to include ...
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 sets to any epimorphisms in any
category Category, plural categories, may refer to: Philosophy and general uses *Categorization, categories in cognitive science, information science and generally *Category of being * ''Categories'' (Aristotle) * Category (Kant) * Categories (Peirce) ...
. Any function can be decomposed into a surjection and an injection: 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, the image of a function is the set of all output values it may produce. More generally, evaluating a given function f at each element of a given subset A of its domain produces a set, called the "image of A under (or through ...
s where ''z'' is in . These preimages are disjoint and partition ''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, a quotient (from lat, quotiens 'how many times', pronounced ) is a quantity produced by the division of two numbers. The quotient has widespread use throughout mathematics, and is commonly referred to as the integer part of a ...
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 classes of ''A'' under the following
equivalence relation In mathematics, an equivalence relation is a binary relation that is reflexive, symmetric and transitive. The equipollence relation between line segments in geometry is a common example of an equivalence relation. Each 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 In mathematics, a projection is a mapping of a set (or other mathematical structure) into a subset (or sub-structure), which is equal to its square for mapping composition, i.e., which is idempotent. The restriction to a subspace of a projec ...
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, the cardinality of a set is a measure of the number of elements of the set. For example, the set A = \ contains 3 elements, and therefore A has a cardinality of 3. Beginning in the late 19th century, this concept was generalized ...
of this set is one of the twelve aspects of Rota's Twelvefold way, and is given by , B, !\begin, A, \\, B, \end, where \begin, A, \\, B, \end denotes a Stirling number of the second kind.


Gallery

File:Surjective composition.svg, Surjective composition: the first function need not be surjective. File:Non-surjective function2.svg, alt=, Non-surjective functions in the Cartesian plane. Although some parts of the function are surjective, where elements ''y'' in ''Y'' do have a value ''x'' in ''X'' such that ''y'' = ''f''(''x''), some parts are not. Left: There is ''y''0 in ''Y'', but there is no ''x''0 in ''X'' such that ''y''0 = ''f''(''x''0). Right: There are ''y''1, ''y''2 and ''y''3 in ''Y'', but there are no ''x''1, ''x''2, and ''x''3 in ''X'' such that ''y''1 = ''f''(''x''1), ''y''2 = ''f''(''x''2), and ''y''3 = ''f''(''x''3). File:Surjective function.svg, alt=, Interpretation for surjective functions in the Cartesian plane, defined by the mapping ''f'' : ''X'' → ''Y'', where ''y'' = ''f''(''x''), ''X'' = domain of function, ''Y'' = range of function. Every element in the range is mapped onto from an element in the domain, by the rule ''f''. There may be a number of domain elements which map to the same range element. That is, every ''y'' in ''Y'' is mapped from an element ''x'' in ''X'', more than one ''x'' can map to the same ''y''. Left: Only one domain is shown which makes ''f'' surjective. Right: two possible domains ''X''1 and ''X''2 are shown.


See also

* Bijection, injection and surjection * Cover (algebra) * Covering map *
Enumeration An enumeration is a complete, ordered listing of all the items in a collection. The term is commonly used in mathematics and computer science to refer to a listing of all of the elements of a set. The precise requirements for an enumeration (fo ...
*
Fiber bundle In mathematics, and particularly topology, a fiber bundle (or, in Commonwealth English: fibre bundle) is a space that is a product space, but may have a different topological structure. Specifically, the similarity between a space E and a ...
*
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 may be ''indexed'' or ''labeled'' by means of the elements of a set , then is an index set. The indexing consist ...
* Section (category theory)


References


Further reading

* {{Mathematical logic Functions and mappings Basic concepts in set theory Mathematical relations Types of functions