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 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-dimensio ...
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 * ...
. 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, an injective function (also known as injection, or one-to-one function) is a function that maps distinct elements of its domain to distinct elements; that is, implies . (Equivalently, implies in the equivalent contrapositi ...
'' 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 Nicolas Bourbaki () is the collective pseudonym of a group of mathematicians, predominantly French alumni of the École normale supérieure - PSL (ENS). Founded in 1934–1935, the Bourbaki group originally intended to prepare a new textbook i ...
, a group of mainly
French French (french: français(e), link=no) may refer to: * Something of, from, or related to France ** French language, which originated in France, and its various dialects and accents ** French people, a nation and ethnic group identified with Franc ...
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 On ...
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-dimensio ...
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 In mathematics, the axiom of choice, or AC, is an axiom of set theory equivalent to the statement that ''a Cartesian product of a collection of non-empty sets is non-empty''. Informally put, the axiom of choice says that given any collection ...
, and every function with a right inverse is necessarily a surjection. The composition 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-dimensio ...
is equal to its codomain. 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 * ...
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, un ...
id''X'' on ''X'' is surjective. * The function defined by ''f''(''n'') = ''n'' mod 2 (that is,
even Even may refer to: General * Even (given name), a Norwegian male personal name * Even (surname) * Even (people), an ethnic group from Siberia and Russian Far East **Even language, a language spoken by the Evens * Odd and Even, a solitaire game wh ...
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 languag ...
s are mapped to 0 and
odd Odd means unpaired, occasional, strange or unusual, or a person who is viewed as eccentric. Odd may also refer to: Acronym * ODD (Text Encoding Initiative) ("One Document Does it all"), an abstracted literate-programming format for describing X ...
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 In mathematics, an injective function (also known as injection, or one-to-one function) is a function that maps distinct elements of its domain to distinct elements; that is, implies . (Equivalently, implies in the equivalent contrapositi ...
(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, ...
, 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, the matrix exponential is a matrix function on square matrices analogous to the ordinary exponential function. It is used to solve systems of linear differential equations. In the theory of Lie groups, the matrix exponential give ...
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 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\t ...
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 In mathematics, an injective function (also known as injection, or one-to-one function) is a function that maps distinct elements of its domain to distinct elements; that is, implies . (Equivalently, implies in the equivalent contrapositi ...
. 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 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, un ...
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 a ...
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 mathematics, the axiom of choice, or AC, is an axiom of set theory equivalent to the statement that ''a Cartesian product of a collection of non-empty sets is non-empty''. Informally put, the axiom of choice says that given any collection ...
. 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 of ...
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 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 ...
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 In the mathematical field of category theory, the category of sets, denoted as Set, is the category whose objects are sets. The arrows or morphisms between sets ''A'' and ''B'' are the total functions from ''A'' to ''B'', and the composition o ...
. 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 sig ...
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 In mathematics, a binary relation ''R'' ⊆ ''X''×''Y'' between two sets ''X'' and ''Y'' is total (or left total) if the source set ''X'' equals the domain . Conversely, ''R'' is called right total if ''Y'' equals the range . When ''f'': ''X'' ...
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. ...
s. (The proof appeals to the
axiom of choice In mathematics, the axiom of choice, or AC, is an axiom of set theory equivalent to the statement that ''a Cartesian product of a collection of non-empty sets is non-empty''. Informally put, the axiom of choice says that given any collection ...
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 In mathematics, an injective function (also known as injection, or one-to-one function) is a function that maps distinct elements of its domain to distinct elements; that is, implies . (Equivalently, implies in the equivalent contrapositi ...
. 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 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 In the mathematical field of category theory, the category of sets, denoted as Set, is the category whose objects are sets. The arrows or morphisms between sets ''A'' and ''B'' are the total functions from ''A'' to ''B'', and the composition o ...
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 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, when the elements of some set S have a notion of equivalence (formalized as an equivalence relation), then one may naturally split the set S into equivalence classes. These equivalence classes are constructed so that elements a ...
es 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 relatio ...
: ''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''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 In combinatorics, the twelvefold way is a systematic classification of 12 related enumerative problems concerning two finite sets, which include the classical problems of counting permutations, combinations, multisets, and partitions either of ...
, 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 *
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 * Section (category theory)


References


Further reading

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