Movatterモバイル変換

[0]ホーム

Jump to content

Surjective function

Edit links

From Wikipedia, the free encyclopedia

(Redirected fromSurjection)

Mathematical function such that every output has at least one input

"Onto" redirects here. For other uses, seewiktionary:onto.

Function
x ↦f (x)
History of the function concept
Types bydomain andcodomain
`X` →𝔹 𝔹 →`X` 𝔹ⁿ →`X` `X` →ℤ ℤ →`X` `X` →ℝ ℝ →`X` ℝⁿ →`X` `X` →ℂ ℂ →`X` ℂⁿ →`X`
Classes/properties
Constant Identity Linear Polynomial Rational Algebraic Analytic Smooth Continuous Measurable Injective Surjective Bijective
Constructions
Restriction Composition λ Inverse
Generalizations
Relation (Binary relation) Set-valued Multivalued Partial Implicit Space Higher-order Morphism Functor
List of specific functions
v t e

Inmathematics, asurjective function (also known assurjection, oronto function/ˈɒn.tuː/) is afunctionf such that, for every elementy of the function'scodomain, there existsat least one elementx in the function'sdomain such thatf(x) =y. In other words, for a functionf :X →Y, the codomainY is theimage of the function's domainX.^[1]^[2] It is not required thatx beunique; the functionf may map one or more elements ofX to the same element ofY.

The termsurjective and the related termsinjective andbijective were introduced byNicolas Bourbaki,^[3]^[4] a group of mainlyFrench 20th-centurymathematicians who, under this pseudonym, wrote a series of books presenting an exposition of modern advanced mathematics, beginning in 1935. The French wordsur meansover orabove, and relates to the fact that theimage of the domain of a surjective function completely covers the function's codomain.

Any function induces a surjection byrestricting its codomain to the image of its domain. Every surjective function has aright inverse assuming theaxiom of choice, and every function with a right inverse is necessarily a surjection. Thecomposition of surjective functions is always surjective. Any function can be decomposed into a surjection and an injection.

Definition

[edit]

Further information on notation:Function (mathematics) § Notation

Asurjective function is afunction whoseimage is equal to itscodomain. Equivalently, a function $f {\displaystyle f}$ withdomain $X {\displaystyle X}$ and codomain $Y {\displaystyle Y}$ is surjective if for every $y {\displaystyle y}$ in $Y {\displaystyle Y}$ there exists at least one $x {\displaystyle x}$ in $X {\displaystyle X}$ with $f(x)=y$ .^[1] Surjections are sometimes denoted by a two-headed rightwards arrow (U+21A0 ↠RIGHTWARDS TWO HEADED ARROW),^[5] as in $f\colon X\twoheadrightarrow Y$ .

Symbolically,

f\colon X\rightarrow Y

, then

f {\displaystyle f}

is said to be surjective if

\forall y\in Y,\,\exists x\in X,\;\;f(x)=y

.^[2]^[6]

Examples

[edit]

**A non-surjective function** fromdomainX tocodomainY. The smaller yellow oval insideY is theimage (also calledrange) off. This function isnot surjective, because the image does not fill the whole codomain. In other words,Y is colored in a two-step process: First, for everyx inX, the pointf(x) is colored yellow; Second, all the rest of the points inY, that are not yellow, are colored blue. The functionf would be surjective only if there were no blue points.

For more examples, see§ Gallery.

For any setX, theidentity function id_X onX is surjective.
The functionf :Z → {0, 1} defined byf(n) =nmod 2 (that is,even integers are mapped to 0 andodd integers to 1) is surjective.
The functionf :R →R defined byf(x) = 2x + 1 is surjective (and evenbijective), because for everyreal numbery, we have anx such thatf(x) =y: such an appropriatex is (y − 1)/2.
The functionf :R →R defined byf(x) =x³ − 3x is surjective, because the pre-image of anyreal numbery is the solution set of the cubic polynomial equationx³ − 3x −y = 0, and every cubic polynomial with real coefficients has at least one real root. However, this function is notinjective (and hence notbijective), since, for example, the pre-image ofy = 2 is {x = −1,x = 2}. (In fact, the pre-image of this function for everyy, −2 ≤y ≤ 2 has more than one element.)
The functiong :R →R defined byg(x) =x² isnot surjective, since there is no real numberx such thatx² = −1. However, the functiong :R →R_≥0 defined byg(x) =x² (with the restricted codomain)is surjective, since for everyy in the nonnegative real codomainY, there is at least onex in the real domainX such thatx² =y.
Thenatural logarithm functionln : (0, +∞) →R is a surjective and even bijective (mapping from the set of positive real numbers to the set of all real numbers). Its inverse, theexponential function, if defined with the set of real numbers as the domain and the codomain, is not surjective (as its range is the set of positive real numbers).
Thematrix exponential is not surjective when seen as a map from the space of alln×nmatrices to itself. It is, however, usually defined as a map from the space of alln×n matrices to thegeneral linear group of degreen (that is, thegroup of alln×ninvertible matrices). Under this definition, the matrix exponential is surjective for complex matrices, although still not surjective for real matrices.
Theprojection from acartesian productA ×B 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

[edit]

A function isbijective if and only if it is both surjective andinjective.

If (as is often done) a function is identified with itsgraph, then surjectivity is not a property of the function itself, but rather a property of themapping.^[7] 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

[edit]

The functiong :Y →X is said to be aright inverse of the functionf :X →Y iff(g(y)) =y for everyy inY (g can be undone byf). In other words,g is a right inverse off if thecompositionfog ofg andf in that order is theidentity function on the domainY ofg. The functiong need not be a completeinverse off because the composition in the other order,gof, may not be the identity function on the domainX off. In other words,f can undo or "reverse"g, but cannot necessarily be reversed by it.For example, $f:\mathbb {R} ^{2}\rightarrow \mathbb {R} ,(x,y)\mapsto x$ has right inverse $g:z\mapsto (z,0);$ the composition in the other order gives⁠ $g(f((x,y)))=(x,0)$ ⁠, which equals⁠ $(x,y)$ ⁠ only if⁠ $x=0$ ⁠.

Every function with a right inverse is necessarily a surjection. The proposition that every surjective function has a right inverse is equivalent to theaxiom of choice.

Iff :X →Y is surjective andB is asubset ofY, thenf(f⁻¹(B)) =B. Thus,B can be recovered from itspreimagef⁻¹(B).

For example, in the first illustration in thegallery, there is some functiong such thatg(C) = 4. There is also some functionf such thatf(4) =C. It doesn't matter thatg is not unique (it would also work ifg(C) equals 3); it only matters thatf "reverses"g.

Surjections as epimorphisms

[edit]

A functionf :X →Y is surjective if and only if it isright-cancellative:^[8]^[9] given any functionsg,h :Y →Z, whenevergof =hof, theng =h. This property is formulated in terms of functions and theircomposition and can be generalized to the more general notion of themorphisms of acategory and their composition. Right-cancellative morphisms are calledepimorphisms. Specifically, surjective functions are precisely the epimorphisms in thecategory of sets. The prefixepi is derived from the Greek prepositionἐπί meaningover,above,on.

Any morphism with a right inverse is an epimorphism, but the converse is not true in general. A right inverseg of a morphismf is called asection off. A morphism with a right inverse is called asplit epimorphism.

Surjections as binary relations

[edit]

Any function with domainX and codomainY can be seen as aleft-total andright-unique binary relation betweenX andY by identifying it with itsfunction graph. A surjective function with domainX and codomainY is then a binary relation betweenX andY that is right-unique and both left-total andright-total.

Cardinality of the domain of a surjection

[edit]

Thecardinality of the domain of a surjective function is greater than or equal to the cardinality of its codomain: Iff :X →Y is a surjective function, thenX has at least as many elements asY, in the sense ofcardinal numbers. (The proof appeals to theaxiom of choice to show that a functiong :Y →X satisfyingf(g(y)) =y for ally inY exists.g is easily seen to be injective, thus theformal definition of |Y| ≤ |X| is satisfied.)

Specifically, if bothX andY arefinite with the same number of elements, thenf :X →Y is surjective if and only iff isinjective.

Composition and decomposition

[edit]

Thecomposition of surjective functions is always surjective: Iff andg are both surjective, and the codomain ofg is equal to the domain off, thenfog is surjective. Conversely, iffog is surjective, thenf is surjective (butg, the function applied first, need not be). These properties generalize from surjections in thecategory of sets to anyepimorphisms in anycategory.

Any function can be decomposed into a surjection and aninjection: For any functionh :X →Z there exist a surjectionf :X →Y and an injectiong :Y →Z such thath =gof. To see this, defineY to be the set ofpreimagesh⁻¹(z) wherez is inh(X). These preimages aredisjoint andpartitionX. Thenf carries eachx to the element ofY which contains it, andg carries each element ofY to the point inZ to whichh sends its points. Thenf is surjective since it is a projection map, andg is injective by definition.

Induced surjection and induced bijection

[edit]

Any function induces a surjection by restricting its codomain to its range. Any surjective function induces a bijection defined on aquotient of its domain by collapsing all arguments mapping to a given fixed image. More precisely, every surjectionf :A →B can be factored as a projection followed by a bijection as follows. LetA/~ be theequivalence classes ofA under the followingequivalence relation:x ~y if and only iff(x) =f(y). Equivalently,A/~ is the set of all preimages underf. LetP(~) :A →A/~ be theprojection map which sends eachx inA to its equivalence class [x]_~, and letf_P :A/~ →B be the well-defined function given byf_P([x]_~) =f(x). Thenf =f_P oP(~).