Surjective function

From Wikipedia for FEVERv2
(Redirected from Onto)
Jump to navigation Jump to search

"Onto" redirects here. Surjective function_sentence_0

For other uses, see . Surjective function_sentence_1

In mathematics, a function f from a set X to a set Y is surjective (also known as onto, or a surjection), if for every element y in the codomain Y of f, there is at least one element x in the domain X of f such that f(x) = y. Surjective function_sentence_2

It is not required that x be unique; the function f may map one or more elements of X to the same element of Y. Surjective function_sentence_3

The term surjective and the related terms injective and bijective were introduced by Nicolas Bourbaki, a group of mainly French 20th-century mathematicians who, under this pseudonym, wrote a series of books presenting an exposition of modern advanced mathematics, beginning in 1935. Surjective function_sentence_4

The French word means over or above, and relates to the fact that the image of the domain of a surjective function completely covers the function's codomain. Surjective function_sentence_5

Any function induces a surjection by restricting its codomain to the image of its domain. Surjective function_sentence_6

Every surjective function has a right inverse, and every function with a right inverse is necessarily a surjection. Surjective function_sentence_7

The composition of surjective functions is always surjective. Surjective function_sentence_8

Any function can be decomposed into a surjection and an injection. Surjective function_sentence_9

Definition Surjective function_section_0

Further information on notation: Function (mathematics) § Notation Surjective function_sentence_10

Symbolically, Surjective function_sentence_11

Examples Surjective function_section_1

Surjective function_unordered_list_0

  • For any set X, the identity function idX on X is surjective.Surjective function_item_0_0
  • The function f : Z → {0,1} defined by f(n) = n mod 2 (that is, even integers are mapped to 0 and odd integers to 1) is surjective.Surjective function_item_0_1
  • The function f : R → R defined by f(x) = 2x + 1 is surjective (and even bijective), because for every real number y, we have an x such that f(x) = y: such an appropriate x is (y − 1)/2.Surjective function_item_0_2
  • The function f : R → R defined by f(x) = x − 3x is surjective, because the pre-image of any real number y is the solution set of the cubic polynomial equation x − 3x − 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), since, for example, the pre-image of y = 2 is {x = −1, x = 2}. (In fact, the pre-image of this function for every y, −2 ≤ y ≤ 2 has more than one element.)Surjective function_item_0_3
  • The function g : R → R defined by g(x) = x is not surjective, since there is no real number x such that x = −1. However, the function g : R → R0 defined by g(x) = x (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 = y.Surjective function_item_0_4
  • The natural logarithm function ln : (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, the exponential function, if defined with the set of real numbers as the domain, is not surjective (as its range is the set of positive real numbers).Surjective function_item_0_5
  • 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 of degree n (i.e. 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.Surjective function_item_0_6
  • The projection from a cartesian product A × B to one of its factors is surjective, unless the other factor is empty.Surjective function_item_0_7
  • In a 3D video game, vectors are projected onto a 2D flat screen by means of a surjective function.Surjective function_item_0_8

Properties Surjective function_section_2

A function is bijective if and only if it is both surjective and injective. Surjective function_sentence_12

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. Surjective function_sentence_13

This is, the function together with its codomain. Surjective function_sentence_14

Unlike injectivity, surjectivity cannot be read off of the graph of the function alone. Surjective function_sentence_15

Surjections as right invertible functions Surjective function_section_3

The function g : Y → X is said to be a right inverse of the function f : X → Y if f(g(y)) = y for every y in Y (g can be undone by f). Surjective function_sentence_16

In other words, g is a right inverse of f if the composition f o g of g and f in that order is the identity function on the domain Y of g. The function g need not be a complete inverse of f because the composition in the other order, g o f, 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. Surjective function_sentence_17

Every function with a right inverse is necessarily a surjection. Surjective function_sentence_18

The proposition that every surjective function has a right inverse is equivalent to the axiom of choice. Surjective function_sentence_19

If f : X → Y is surjective and B is a subset of Y, then f(f(B)) = B. Surjective function_sentence_20

Thus, B can be recovered from its preimage f(B). Surjective function_sentence_21

For example, in the first illustration, above, there is some function g such that g(C) = 4. Surjective function_sentence_22

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. Surjective function_sentence_23

Surjective function_unordered_list_1

  • Surjective function_item_1_9
  • Surjective function_item_1_10
  • Surjective function_item_1_11

Surjections as epimorphisms Surjective function_section_4

A function f : X → Y is surjective if and only if it is right-cancellative: given any functions g,h : Y → Z, 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 morphisms of a category and their composition. Surjective function_sentence_24

Right-cancellative morphisms are called epimorphisms. Surjective function_sentence_25

Specifically, surjective functions are precisely the epimorphisms in the category of sets. Surjective function_sentence_26

The prefix epi is derived from the Greek preposition ἐπί meaning over, above, on. Surjective function_sentence_27

Any morphism with a right inverse is an epimorphism, but the converse is not true in general. Surjective function_sentence_28

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. Surjective function_sentence_29

Surjections as binary relations Surjective function_section_5

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. Surjective function_sentence_30

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. Surjective function_sentence_31

Cardinality of the domain of a surjection Surjective function_section_6

The cardinality of the domain of a surjective function is greater than or equal to the cardinality of its codomain: If f : X → Y is a surjective function, then X has at least as many elements as Y, in the sense of cardinal numbers. Surjective function_sentence_32

(The proof appeals to the axiom of choice to show that a function g : Y → X satisfying f(g(y)) = y for all y in Y exists. Surjective function_sentence_33

g is easily seen to be injective, thus the formal definition of |Y| ≤ |X| is satisfied.) Surjective function_sentence_34

Specifically, 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. Surjective function_sentence_35

Given two sets X and Y, the notation X ≤ Y is used to say that either X is empty or that there is a surjection from Y onto X. Surjective function_sentence_36

Using the axiom of choice one can show that X ≤ Y and Y ≤ X together imply that |Y| = |X|, a variant of the Schröder–Bernstein theorem. Surjective function_sentence_37

Composition and decomposition Surjective function_section_7

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 f o g is surjective. Surjective function_sentence_38

Conversely, if f o g is surjective, then f is surjective (but g, the function applied first, need not be). Surjective function_sentence_39

These properties generalize from surjections in the category of sets to any epimorphisms in any category. Surjective function_sentence_40

Any function can be decomposed into a surjection and an injection: For any function h : X → Z there exist a surjection f : X → Y and an injection g : Y → Z such that h = g o f. To see this, define Y to be the set of preimages h(z) where z is in h(X). Surjective function_sentence_41

These preimages are disjoint and partition X. Surjective function_sentence_42

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. Surjective function_sentence_43

Then f is surjective since it is a projection map, and g is injective by definition. Surjective function_sentence_44

Induced surjection and induced bijection Surjective function_section_8

Any function induces a surjection by restricting its codomain to its range. Surjective function_sentence_45

Any surjective function induces a bijection defined on a quotient of its domain by collapsing all arguments mapping to a given fixed image. Surjective function_sentence_46

More precisely, every surjection f : A → B can be factored as a projection followed by a bijection as follows. Surjective function_sentence_47

Let A/~ be the equivalence classes of A under the following equivalence relation: x ~ y if and only if f(x) = f(y). Surjective function_sentence_48

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 fP : A/~ → B be the well-defined function given by fP([x]~) = f(x). Surjective function_sentence_49

Then f = fP o P(~). Surjective function_sentence_50

See also Surjective function_section_9

Surjective function_unordered_list_2

Credits to the contents of this page go to the authors of the corresponding Wikipedia page: function.