Definition of functions [duplicate]

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?

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:

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.

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

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.

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