Definition of Surjectivity in set-theoretical definition of functions

Question

I am puzzled by the question of how to define surjectivity in the light of the set-theoretical definition of functions.

A function $f : A \rightarrow B$ from a set $A$ to a set $B$ is a subset $f \subseteq A \times B$ of the Cartesian product $A \times B$ such that the following conditions hold:

1. $\forall a \in A : \exists b \in B : (a,b) \in f$
2. $\forall a \in A : \forall b, b' \in B : (a,b), (a,b') \in f \rightarrow b=b'$

Both conditions encode the idea that for every value $a \in A$ there exists a unique output value $b \in B$.

A function $f : A \rightarrow B$ is surjective if

3. $ \forall b \in B : \exists a \in A : f(a) = b$.

We note that the notion of a function being surjective depends on the codomain of the function; by enlarging the codomain the function loses any surjectivity and by shrinking the codomain a function may eventually become surjective.

However, in the set-theoretical definition of functions we identify functions by their graph, which is enough to recover the domain $A$ and the image $f(A)$, but not enough to recover the codomain $B$.

For example, the identity function $f : \{0\} \rightarrow \{0\}$ is surjective and can be identified with its graph: $f = \{ (0,0) \} \in \{0\} \times \{0\}$. However, this is also the graph of the non-surjective function $f : \{0\} \rightarrow \mathbb R$.

It seems intuitive to me the "same" function with different codomains is actually different functions. Consequently, the codomain should be included as information when we define a "function object" in mathematics.

Answer 1

There are two incompatible, but closely related, definitions of what a function is. The category-theoretic definition has an associated set-theoretic definition, and this is that a function $f$ is a triple $(X, Y, G)$, where $X$ and $Y$ are sets, and $G\subseteq{X\times{Y}}$, such that $G$ satisfies the two axioms you listed. In this context, $X$ is the domain, and $Y$ is the codomain, and so, the definition of surjectivity as stated in the book is actually meaningful, since changing the codomain changes what the function itself is.

Now, notice that if I replace $Y$ with a superset of $Y$, I still have a function, although it is a different function than the one I started with. If I replace $Y$ with $f[X]$, then I get a third function, and this one is actually surjective. However, if I change $Y$ to a proper subset of $f[X]$, the resulting relation ceases to be a function, unless you want to consider it as a partial function, which is typically not preferred in mathematics outside some very limited contexts.

This brings us to the other definition of a function. Rather than defining a function $f$ as a triple $(X, Y, G)$, one can define $G$ itself to be the function, and in many disciplines in mathematics, this is more useful than the former definition. However, one tradeoff is that, with this definition, the codomain of a function is not unique: as long as you specify the domain of the function, and what elements are associated to what elements, you have uniquely identified the function. The codomain itself does not really matter: the codomain can be chosen to be any superset of $f[X]$, including $f[X]$ itself. In light of this, every function can be said to be surjective, and so it is not meaningful to talk about surjectivity in contexts where this latter definition of a function is being used. Depending on the context, this can be a good thing, or a bad thing.

Answer 2

One thing to pay careful attention to is that your passage isn't the definition of "function"; it is the definition of "function from $A$ to $B$".

You don't need to include anything in your model of such an object to remember the codomain of such a thing, since the codomain is right there in the type. A "function from $A$ to $B$" has codomain $B$.

It is possible that you might be able to use the same set to represent both a "function from $A$ to $B$" and a "function from $A$ to $C$", but that's not really an issue if you keep track of what type of object you're working with. It's not much different from the fact you might sometimes use $\{ \varnothing, \{ \varnothing \} \}$ to denote a particular set with two elements, and other times you would use the same object to denote the natural number $2$.

Now, if you want to have a notion of "function", you do indeed need to do something extra. A common approach is to define "function" to be a triple $(A, f, B)$ where $A$ and $B$ are sets and $f$ is a "function from $A$ to $B$". This is consistent with a more general approach to defining disjoint unions; here, think of the class of "functions" as being the disjoint union of all the individual classes of "functions from $A$ to $B$".

Or... alternatively you could accept that a "function" doesn't uniquely determine a codomain; only when you construe it as a "function from $A$ to $B$" does it have a well-defined codomain. I get the impression that people really do do this, but that it is rather unpopular in modern times and increasingly so.

Answer 3

In the set theoretic context, every function is surjective on its range (or "image" in some terminologies). But the notion of being a function between $A$ and $B$ is a property which is not intrinsic to the function.

The same can be said about reflexive relations. Or equivalence relations. We always say that $E$ is an equivalence relation on a set. Because reflexivity is an extrinsic property, it requires information beyond what we know about $E$. It is a property of the function and two sets (the domain, which we can actually omit as it is computed from the function, and the codomain).

You could argue that this more credence to the categorical definition of a function as $(f,A,B)$ where $A$ and $B$ are the domain of the function. But then you have that the function $(\{(0,0)\},\{0\},\{0\})$ and $(\{(0,0)\},\{0\},\Bbb R)$ are not the same function.

While you can argue "Well, there is a natural morphism between these functions", this is not the point. The two functions are different objects. In set theory it is often convenient that the function is the same, and its codomain is specified explicitly, or ignored entirely (e.g. when looking at the class of all functions from some set to the universe of sets).

Much like everything else, there are trade-offs between the definitions, and you should consider them in the correct context to decide which one is more fitting.

In fact, even more is true: in some contexts it is easier to talk about partial functions, so $f\colon A\to B$ just means that the domain of $f$ is a subset of $A$ (e.g. computable functions, or in many definitions of forcing posets). And there you can even argue that more things go awry, and that's true. Which is why—again—context is everything.