5
$\begingroup$

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

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

$\endgroup$
  • 1
    $\begingroup$ I think the problem is that you identify $f$ to a subset of $A\times B$, namely to its graph. I would rather say that a function (this is how I have seen it defined) is defined by $f=(A,B,\Gamma)$ where $\Gamma$ is the graph of the function i.e. a subset of $A\times B$ satisfying the axioms $1$ and $2$. In this case the surjectivity is well defined. $\endgroup$ – Clément Guérin Feb 19 '18 at 2:58
1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

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.