Surjective function

Encyclopedia : S : SU : SUR : Surjective function

---

In mathematics, a function f is said to be surjective if its values span its whole codomain; that is, for every y in the codomain, there is at least one x in the domain such that f(x) = y.

Said another way, a function f: X → Y is surjective if and only if its range f(X) is equal to its codomain Y. A surjective function is called a surjection, and said to be onto.

Examples and counterexamples

• For any set X, the identity function id_X on X is surjective.
• The function f: R → R defined by f(x) = 2x + 1 is surjective, because for every real number y we have f(x) = y where x is (y - 1)/2.
• The natural logarithm function ln: (0..+∞) → R is surjective.
• The function g: R → R defined by g(x) = x² is not surjective, because (for example) there is no real number x such that x² = −1. However, if the codomain is defined as [0,+∞), then g is surjective.
• The function f: Z →  defined by f(x) = x mod 4 is surjective.

Properties

• A function f: X → Y is surjective if and only if there exists a function g: Y → X such that f o g equals the identity function on Y. (This statement is equivalent to the axiom of choice.)
• If f and g are both surjective, then f o g is surjective.
• If f o g is surjective, then f is surjective (but g may not be).
• f: X → Y is surjective if and only if, given any functions g,h:Y → Z, whenever g o f = h o f, then g = h. In other words, surjective functions are precisely the epimorphisms in the category Set of sets.
• If f: X → Y is surjective and B is a subset of Y, then f(f ⁻¹(B)) = B. Thus, B can be recovered from its preimage f ⁻¹(B).
• Every function h: X → Z can be decomposed as h = g o f for a suitable surjection f and injective function g. This decomposition is unique up to isomorphism, and f may be thought of as a function with the same values as h but with its codomain restricted to the range h(W) of h, which is only a subset of the codomain Z of h.
• By collapsing all arguments mapping to a given fixed image, every surjection induces a bijection defined on a quotient of its domain. More precisely, every surjection f : A → B 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: 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]_~, and let f_P : A/~ → B be the well-defined function given by f_P([x]_~) = f(x). Then f = f_P o P(~).
• If f: X → Y is a surjective function, then X has at least as many elements as Y, in the sense of cardinal numbers.
• 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.

See also

• bijective function
• epimorphism
• injective function

Category theory view

In the language of category theory, surjective functions are precisely the epimorphisms in the category of sets.

 

---

From Wikipedia, the Free Encyclopedia. Original article here. Support Wikipedia by contributing or donating.
All text is available under the terms of the GNU Free Documentation License See Wikipedia Copyrights for details.

Search Titles

0

1

2

3

4

5

6

7

8

9

A

B

C

D

E

F

G

H

I

J

K

L

M

N

O

P

Q

R

S

T

U

V

W

X

Y

Z

?