# Why is surjectivity defined using $\exists$ rather than $\exists !$

So let $X, Y$ be two arbritary sets. And let $f: X \to Y$ be a function.

Definition : f is surjective $\Leftrightarrow$ $\forall y\in Y, \exists x \in X, \ \ : \ \ f(x)=y$

Now, I intepret this as: All elements in the codomain get "hit".

Let's consider $A=\{1\}$, $B=\{2,3\}$ and let's map $1\mapsto 2, 1\to 3$. Doesn't this fullfil the definition of surjectivity? If I get the concept of surjectivity right, that shouldn't be possible. So I'm wondering, shouldn't we rather use $\exists !$ in the definition? So we don't hit the same element in $X$ twice?

edit: I also though about, that the definition of a function probably takes care of this. But my definition of a function (total order) also does the same - so I can't see where we actually "limit" this.

• Use \to for mathjax arrow. Also the twodefinitions are different. Consider tan x being a surjective function. – user202729 Jan 13 '18 at 11:01
• Your proposed counter example is not a function. – Arnaud D. Jan 13 '18 at 11:07

Your so-called function is not function, it's just a relation $\{(1,2), (1,3)\}$.

A function $f: X \to Y$ is a relation $R \subseteq X \times Y$ with the property that for all $x$ in $X$ there is a unique $y \in Y$ (denoted $f(x)$) such that $(x,y) \in R$. So there we do have $\exists!$, which might give rise to your question:

$$\forall x \in X: \exists! y \in Y: (x,y) \in f$$

Surjectivity is just that for each $y$ at least one $x$ exists with $y = f(x)$ , but there could be more. E.g. $f:\{1,2,3\}\to \{1,2\}$ given by $f= \{(1,1), (2,2),(3,2)\}$ where every $x$ has a unique $y$ but $y$ has two corresponding $x$.

If we'd demand

$$\forall y: \exists ! x : (x,y) \in f$$

the function would be a bijection, which is a lot stronger.

Your example is a surjective relation, not a surjective function.

• Exactly what you said was my though, so I checked my lecture notes and it says: imgur.com/a/Ef8kJ so I absolutely don't see why we have that limitation. What you said and defined is what I expected but I can't see this here. – xotix Jan 13 '18 at 11:36
• @xotix yes, the second clause is the unicity I wrote. But what are your notes on surjectivity? – Henno Brandsma Jan 13 '18 at 11:38
• ah, true. Couldn't I just use first clause with $\exists !$ and skip the second clause to get the same result? Also, the definition I gave for surjectivity would hold for my example, if we treat $f$ as a (binary) relation rather than a function, right? (from the idea point of view) imgur.com/a/Ef8kJ Maybe asked differently: The definition of surjectivity doesn't give us the uniqueness of the inverse image of an element in the codomain, right? Edit: you actually mentoined it at the end. Thanks, problem solved. World's great again. :D – xotix Jan 13 '18 at 11:43

Well, you say that in surjection, every element in the codomain must be 'hit'. So, you do agree that there should be some $x$ in the domain for which we get a $y$ in the codomain under the function $f$.

Now, firstly, I would like to see the example which you set forth.

The sets you defined were $A = \left\lbrace 1 \right\rbrace$ and $B = \left\lbrace 2, 3 \right\rbrace$. And the function you defined was $f: A \rightarrow B$ where $f(1) = 2, 3$. But the definition of the function says that every element in the domain ($A$) must have a unique element in the codomain ($B$). Thus, this is not a function.

Now, consider this example. Let $A = \left\lbrace 1, 2 \right\rbrace$ and $B = \left\lbrace 3 \right\rbrace$. We define the function $f: A \rightarrow B$ where $\forall x \in A, f(x) = 3$.

This takes care of "hitting" all the elements of the codomain ($B$). Thus, this is a surjection. However, it does not give us an unique $x \in A$ for which $f(x) = 3$.

Therefore, for just a surjection, the uniqueness is not required. As mentioned in the answer by Rohan, if you put this extra condition of uniqueness, then you want a bijection (one - one and onto) actually and not a surjection.

Consider the example $X = \mathbb{R}$ and $Y = \mathbb{R}^+$, where $f: X\rightarrow Y , x \mapsto x^2$

Here you can indeed find an $x \in \mathbb{R}$ so that for any $y \geq 0$ you have $f(x)=x^2 = y$ (since you can just take the square root and would obtain $x = \sqrt y$ for one possible solution). Notice that $x$ can take on two different values here however. For example, if $y = 4$ , you can find $x = 2$ and $x = -2$, which both solve the equation $x^2 = y$ but the $x$ is not unique in this example.

If you replaced the condition $\exists$ with $\exists!$, then note that you are defining a one-one and onto function.

But, it is not necessary that for a function to be surjective, it should be injective also.

For a function to be surjective the uniqueness of pre- image is not necessary. Your example A={1}, B={2,3} and let's map $1↦2$,$1→3$ does not define a function, due to the fact that $1$ is mapped to two different values.You may define a function $f:[-1,1]\to [0,1]$ such as $f(x) = x^2$ which is onto but not one-to -one.

• so if the definition of a function would allow a mapping as I presented, it would be, by definition, surjectiv? – xotix Jan 13 '18 at 11:34
• True. If you had a relation defined as you did, it would be surjective. – Mohammad Riazi-Kermani Jan 13 '18 at 21:28