how does a surjective function not contradict the definition of a function.

Question

I was reading up on functions and different types of functions.

From wikipedia :

A function is a process or a relation that associates each element x of a set X, the domain of the function, to a single element y of another set Y

Surjective function:

a function f from a set X to a set Y is surjective (or 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.

Can someone explain how these two definitions does not contradict eachother?

For each $x\in X$ there is a unique $y\in Y$ such that $f(x)=y$. It doesn't mean that for each $y\in Y$ there is a unique $x\in X$ such that $f(x)=y$. These are completely different things. — Mark, Oct 10 '19 at 15:58

score 0 · Accepted Answer · answered Oct 10 '19 at 15:56

You are understanding one of the definitions wrong.

Surjectivity means that if you have a function $f:X\to Y$ then every $y\in Y$ gets mapped onto.

A function is a process or a relation that associates each element x of a set X, the domain of the function, to a single element y of another set Y

This says that something like this:

$f:\{1,2\}\to \{1,2,3\}$, $f(1)=1$, $f(1)=2$ and $f(2)=3$ is not a function, because $f(1)$ is not unique.

Other example:

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.

Meant is something like this:

Consider the function $f:\{1,2,3\}\to\{1,2\}$

Then we can have $f(1)=1$ and $f(2)=1$ and $f(3)=2$. Then $f$ is surjective and there are values (1 and 2) that are mapped onto the same element (here 1). This is completly fine.

Keep in mind that if you have a function $f:X\to Y$. Every $x\in X$ needs to be mapped onto something. But not every $y\in Y$ needs to be mapped onto.

Example:

$g:\{1,2,3\}\to\{1,2\}$

$g(1)=g(2)=g(3)=1$ is a function. But not surjective.

score 0 · Answer 2 · answered Oct 10 '19 at 15:59

If you read those definitions carefully you will see that the "uniqueness" is in $Y$, not in $X$. For example consider the function from people in the US to states, which assigns to each person the state they live in. Each person lives in just one state (for mathematical and census purposes), but there are many people who live in the same state.

So that is a function.

If you try to define a function by assigning to each person the state in which they have ever lived you see the problem right away. People can move from state to state so there is no "the state" so there is no such function.

RyRy the Fly Guy · Answer 3 · 2019-10-10T16:29:18.657

A function is a relation that maps every element in the domain to a SINGLE element in the codomain... and it may be the case that

$1$. elements in the codomain that are mapped to are mapped to only once, or

$2$. one or more elements in the codomain are mapped to multiple times from DIFFERENT elements in the domain.

In either case, you would not have a contradiction because each element in the domain still only maps to ONE element in the codomain. In the case of #$2$, you would simply have multiple elements in the domain mapping to THE SAME element in the codomain.

When #$1$ occurs, we say the function is injective. When #$2$ occurs, we say the function is not injective. It is injective if and only if every element in the domain maps to a different element in the codomain.

In short, you think there is a contradiction because you are confusing the definition of a function with that of an injective function. And indeed, if that were true then there would be a contradiction! But this is not the case. A function can be injective or not, and in either case it can be surjective or not.

how does a surjective function not contradict the definition of a function.

3 Answers3