What is Surjection: Definition and 26 Discussions

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

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. The French word sur 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.
Any function induces a surjection by restricting its codomain to the image of its domain. Every surjective function has a right inverse, 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.

View More On Wikipedia.org
  1. docnet

    Does there exist a surjection from the integers to the naturals?

    a) Yes. One surjection from ##\mathbb{Z}## to ##\mathbb{N}## is the double cover of ##\mathbb{N}## induced by ##f:\mathbb{Z}\longmapsto\mathbb{N}## with $$f(z)=\begin{cases} -z & ,\forall z<0\\ z+1 & ,\forall 0\leq z \end{cases}$$ b) Yes. One surjection from ##\mathbb{R}## to ##\mathbb{N}## is...
  2. docnet

    Does there exist a surjection from the natural numbers to the reals?

    1) Two sets have the same cardinality if there exists a bijection (one to one correspondence) from ##X## to ##Y##. Bijections are both injective and surjective. Such sets are said to be equipotent, or equinumerous. (credit to wiki) 2) ##|A|\leq |B|## means that there is an injective function...
  3. P

    I What is the Definition and Understanding of Surjective Functions?

    In my book, the definition of surjection is given as follows: Let A and B be sets and f:A->B. The function f is said to be onto if, for each b ϵB, there is at least one a ϵ A for which f(a)=b. In other words, f is onto if R(f)=B. A function which is onto is also called a surjection or a...
  4. Anezka

    How to prove that this function is a surjection?

    If f were a function of 1 variable only, then this would be straight forward as I can try to find its inverse by reversing the operations defined in f. I know I need to show that for any given positive integer,p, there exists two positive integers, m and n such that 1/2(m+n−2)(m+n−1)+n=p...
  5. T

    Injective & Surjective Functions

    Just wondering if anyone could help me get in the right direction with these questions and/or point me to some material that will help me better understand how to approach these questions In what follows I will denote the identity function; i.e. I(x) = x for all x ∈ R. (a) Show that a function...
  6. M

    F bijective <=> f has an inverse

    Homework Statement Proof that: f has an inverse ##\iff## f is a bijection Homework Equations /definitions[/B] A) ##f: X \rightarrow Y## If there is a function ##g: Y \rightarrow X## for which ##f \circ g = f(g(x)) = i_Y## and ##g \circ f = g(f(x)) = i_X##, then ##g## is the inverse...
  7. B

    Injection from finite set to equally sized set is surjection

    This is a rather simple question, so it has been rattling my brain recently. Consider a surjective map ## f : S \rightarrow T ## where both ## S ## and ## T ## are finite sets of equal cardinality. Then is ## f ## necessarily injective? I proved the converse, which turned out to be quite...
  8. diracdelta

    Can Linear Surjections Exist with n < m?

    Homework Statement Let be linear surjection. Prove that then n>=m. Homework Equations Definition(surjection): The Attempt at a Solution Lets assume opposite, n<=m. If that is the case, then for some y from R^m, there is no belonging x from R^n, what is in contradiction with definition where...
  9. M

    Equivalence between an injection and a surjection

    Homework Statement Let A and B be two sets. Homework Equations Prove that there exists a injection from A to B if and only if there exists a surjection from B to A The Attempt at a Solution I did one implication which is we suppose that f: B→A is a surjection. Then by definition of a...
  10. K

    MHB Injection, Surjection, Bijection

    Can anyone explain to me how to do these types of questions? I have the answers but I don't understand it. The function f: N -> N, f(n) = n+1 is (a) Surjection but not an injection (B) Injection but not a surjection (c) A Bijection (d) Neither surjection not injection The answer is B...
  11. B

    Surjection between kernel and image of a homomorphism

    Hi, I was wondering whether the following is true at all. The first isomorphism theorem gives us a relation between a group, the kernel, and image of a homomorphism acting on the group. Could this possibly also imply that there exists a surjective homomorphism either mapping the previous kernel...
  12. G

    How can I prove it? (injection, bijection, surjection)

    Homework Statement How can I prove this? If g°f is a bijective function, then g is surjective and f is injective. Homework Equations The Attempt at a Solution
  13. B

    Surjection Between Mapping Class Grp. and Symplectic Matrices

    Hi, Everyone: I am reading a paper that refers to a "natural surjection" between M<sub>g</sub> and the group of symplectic 2gx2g-matrices. All I know is this map is related to some action of M<sub>g</sub> on H<sub>1</sub>(S<sub>g</sub>,Z). I think this action is...
  14. M

    Possible title: How to Construct a Surjection Map from N to Z

    Surjection from N --> Z Homework Statement Find a surjection map, f: N -> Z Homework Equations The Attempt at a Solution I think this is equivalent to finding an injection map: g: Z -> N So I defined it: g(z) = -z, if z is negative z, if z is positive Is this...
  15. P

    How to prove injection and surjection for a function with 2 variables?

    how do you prove injection and surjection of the function of 2 variables. for example f:RxR->R
  16. A

    Injectivity and Surjectivity of Functions with Lists and Sets

    Homework Statement Are the given functions injective? Surjective? a) seq: N -> Lists[N] b) f: Lists[A] -> P(A), f(x)=(<x1,x2,...,xn>)={x1,x2,...,xn} Homework Equations The Attempt at a Solution a) Ok so the domain contains a sequence of natural numbers. and the range contains a list? What...
  17. K

    Injection, surjection, and bijection

    I'm having trouble understanding just what is the difference between the three types of maps: injective, surjective, and bijective maps. I understand it has something to do with the values, for example if we have T(x): X -> Y, that the values in X are all in Y or that some of them are in Y...
  18. X

    Newbie Asks: ONTO Surjection Help

    Hi :smile: I'm new on these forums, and not only is this my first post, but this is also my first thread. The following is not a homework question, but a question I found. However, I have no idea how to do this. I would appreciate it if someone could help me. Please click on the following...
  19. K

    Proving "No Surjection X \rightarrow P(X)": A Closer Look

    Hi, there's a proposition in my lecture notes which states "If X is a set, there can be no surjection X \rightarrow P(X)", where P(x) is the power set of X (does anyone know how I get the squiggly P?). The proof given there seems unnecessarily complicated to me. Would the following be...
  20. N

    Question about injection, surjection, bijection, and mapping

    f(x) is a bijection if and only if f(x) is both a surjection and a bijection. Now a surjection is when every element of B has at least one mapping, and an injection is when all of the elements have a unique mapping from A, and therefore a bijection is a one-to-one mapping. Let's say that...
  21. U

    [0,1) onto [0,infinity) , continuous surjection?

    Homework Statement Find a continuous surjection from [0,1) onto [0, infinity) Homework Equations The Attempt at a Solution I have only been able to come up with one mapping but then I realized it did not work. Any help would be appreciated.
  22. nicksauce

    Proving f is Not Surjective: A Finite Set Mapping to its Power Set

    Homework Statement Suppose that f is a mapping from a finite set X to P(X) (the power set of X). Prove that f is not surjective.Homework Equations The Attempt at a Solution My proof strategy is 1) Show that P(X) always has more elements than X 2) Show that a mapping from X->Y cannot be...
  23. P

    Surjection: Is f^-1(X) Surjective? Why?

    If a function f: N-->X is surjective , is f^-1(X) (its inverse image) also surjective? If so, why?
  24. A

    Bijection, Injection, and Surjection

    I was just looking at the definitions of these words, and it reminded me of some things from linear algebra. I was just wondering: Is a bijection the same as an isomorphism?
  25. G

    Linear transformation, show surjection and ker=0.

    I have a linear map from $ V\rightarrow K[X_{1},...,X_{n}]\rightarrow K[X_{1},...,X_{n}]/I.$ how do i prove that a linear map from $ V=\{$polynomials with $\deg _{x_{i}}f\prec q\}$ to $ K[X_{1},..X_{n}]/I.$ where I is the ideal generated by the elements $ X_{i}^{q}-X_{i},1\leq i\leq n.,$ is...
  26. G

    Ring, field, injection, surjection, bijection,

    Ring, field, injection, surjection, bijection, jet, bundle. Does anybody know who first introduced those terms and when and why those people called these matimatical structures so. I mean not the definitions but the properties of real things which can be accosiated with those mathematical...