0
$\begingroup$

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.

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

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – xotix Jan 13 '18 at 11:36
  • $\begingroup$ @xotix yes, the second clause is the unicity I wrote. But what are your notes on surjectivity? $\endgroup$ – Henno Brandsma Jan 13 '18 at 11:38
  • $\begingroup$ 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 $\endgroup$ – xotix Jan 13 '18 at 11:43
2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.