2
$\begingroup$

This question already has an answer here:

A function is a type of relation. That is, a function $f$ from $X$ to $Y$ is a subset of $X \times Y$ where for each $x \in X$, there is exactly one $y \in Y$ such that $(x, y) \in f$. Suppose $Y \subsetneq Y'$ and $g: X \to Y'$ is defined by $g(x) = f(x)$. Since functions are sets, and sets are completely determined by there elements $f = g$. However, $f$ can be surjective while $g$ is not, and in that case, $f \ne g$.

How does one resolve this?

$\endgroup$

marked as duplicate by Asaf Karagila, Ittay Weiss, Mario Carneiro, Zev Chonoles, Amzoti Jun 4 '13 at 4:01

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

4
$\begingroup$

There are two options:

  • Don't use that definition of function.
  • Decide that "surjectivity" is not a property of functions.

Less pithily, you can either

  • Define a function to be a triple $(f,X,Y)$ where $X$ is the domain of $f$, and $Y$ the codomain, and $f$ is the relevant subset of $X\times Y$. Then it $(f,X,Y)$ and $(g,X,Y')$ are not the same function and there is no conflict.
  • Keep the definition of function you're using, but decide the "surjectivity" is a relationship between the function and its codomain.

The first approach is the one usually taken in category theory. For example, here is an excerpt from the definition of category in Lang's Algebra:

enter image description here

Thus, in the category $\mathsf{Set}$, whose objects are sets and whose morphisms are functions, the notation $\mathrm{Mor}(A,B)$ means "the set of functions from the set $A$ to the set $B$", and the declaration that the sets $\mathrm{Mor}(A,B)$ and $\mathrm{Mor}(A',B')$ are disjoint means that Lang is not going to consider $f$ and $g$ to be the same function.

$\endgroup$
  • $\begingroup$ How does the excerpt relate to the question? What is $\operatorname{Mor}(A,B)$? $\endgroup$ – Mario Carneiro Jun 4 '13 at 3:52
  • $\begingroup$ @Mario: Sorry, I should have explained further. I've now added to my answer. $\endgroup$ – Zev Chonoles Jun 4 '13 at 3:56
2
$\begingroup$

Though we speak of a function being surjective, this is slightly sloppy if we adopt the usual set-theoretic view of functions: surjectivity is not an innate characteristic of the function considered as a set; it’s a joint characteristic of the function and its codomain.

$\endgroup$
1
$\begingroup$

$f$ is a subset of $X \times Y$, as is $g$, but surjective depends on the image set. $g$ is a subset of $X \times Y'$, but it doesn't have to cover all of $Y'$. Consider $f(x)=x$ with domain and range $\{0,1\}$. It is surjective. Now consider $g(x)=x$ with domain $\{0,1\}$ but with image $\{0,1,2\}$. It is not surjective.

$\endgroup$

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