# Are injectivity and surjectivity dual?

Are injectivity and surjectivity dual in some sense? Their set-theoretic definitions are quite different. In particular, the injectivity is a property of a function's graph, while surjectivity is a relationship between the range of the function and its codomain.

-
In order to answer this properly I feel that I first need to understand what do it mean to be "dual in some sense". – Asaf Karagila Jan 30 at 15:45
Hi Asaf. I don't have any particular notion of duality in mind; perhaps the category-theoretical notion? – user18921 Jan 30 at 15:49
@Asaf, I recommend Lawvere & Rosebrugh's Sets for Mathematics. Many distinct-looking dualities are shown to emerge from the more general duality between categorical limits and colimits. However, there are multiple notions of "duality". Terence Tao has a blog entry that lists many but there are many more he doesn't list. – alancalvitti Jan 30 at 19:06

## 3 Answers

Yes, in some sense.

Surjections and injections are "categorical duals" (in $\mathbf{Set}$). The simplest way to see a manifestation in the duality is the following: let $X,Y,Z$ be sets. If $f:X\to Y$ is surjective, then for any $g_1,g_2:Y\to Z$, $$g_1\circ f = g_2 \circ f \iff g_1 = g_2$$ Whereas if $h: Y\to X$ is injective, then for any $d_1,d_2: Z\to Y$ $$h\circ d_1 = h\circ d_2 \iff d_1 = d_2$$ The duality is clearer if you draw the diagram $$X \overset{f}{\underset{h}{\rightleftarrows}} Y \overset{g_*}{\underset{d_*}{\rightleftarrows}} Z$$

-
 What you've actually shown is right, and left cancellation, which corresponds to epimorphism, resp. monomorphism. They happen to be coincident to surjections and injections in, eg, $\bf Set$, but not in general. – alancalvitti Jan 30 at 19:03 @alancalvitti judging by how the OP phrased the question, I think it is safe to assume that at least as a starting point the OP is working in $\mathbf{Set}$. – Willie Wong♦ Jan 31 at 8:18 I agree, yet how does your answer in terms of monos & epics relate to the OP's issue: "former being a property of a function's graph, the latter denoting a relationship between the range of the function and its codomain." – alancalvitti Jan 31 at 14:31 @WillieWong I think the statement "surjections and injections are categorical duals" should be qualified. "Surjections and injections are categorical duals in the category of sets and functions." If you make this change, I'll choose this as the "selected answer." – user18921 Feb 1 at 11:12 @user: thanks for the note. I added the qualification as requested. – Willie Wong♦ Feb 1 at 11:17

There is an important sense in which they are not strictly dual.

Let X is a non-empty set.

Then f: X --> Y is injective if and only if it has a left inverse. The proof does not require the Axiom of Choice.

But it is not true that f:X --->Y is surjective if and only it has a right inverse, unless you invoke the Axiom of Choice. In fact, this is logically equivalent to the Axiom of Choice.

-
 I would rephrase slightly. Because there are certainly sets $X,Y$ for which it is true that $X\to Y$ is surjective iff it has a right inverse. The Axiom of Choice only enters when the sets are sufficiently large. – Willie Wong♦ Jan 31 at 14:59 @WillieWong, right inverse is a choice of an element in the inverse image for each point in the codomain. Do you mean then, that this is true for example in $\bf FinSet$ without Choice? – alancalvitti Jan 31 at 15:08 @alancalvitti: If you work in ZF, only the size of $Y$ matters. But yes, you may also restrict $X$ to be finite if you wish. – Willie Wong♦ Jan 31 at 15:16 @WillieWong, it is interesting that in set theory Choice can be added or removed "at will" whereas in cat. theory, Choice holds in $\bf Set$, presumably because functions carry no structure (relative to, eg, $\bf Top$ where not all epics split) – alancalvitti Jan 31 at 15:26 @alancalvitti I find your statement somewhat doubtful. See mathoverflow.net/questions/119454/… for example; what you are talking about seems more about the internal axiom of choice versus the usual one. (Also the nCatLab page: ncatlab.org/nlab/show/axiom+of+choice .) But I am not a choice expert. – Willie Wong♦ Jan 31 at 15:34
show 1 more comment

Let $K$ be a field, let $V$ and $W$ be $K$-vector spaces, and let $f: V \rightarrow W$ be a $K$-linear map. Let $V^{\vee} = \operatorname{Hom}(V,K)$ and $W^{\vee} = \operatorname{Hom}(W,K)$ be the dual spaces. Then $f$ induces a map

$f^{\vee}: W^{\vee} \rightarrow V^{\vee}$, by $\ell \in \operatorname{Hom}(W,K) \mapsto (v \in V \mapsto \ell(f(v)))$.

1) $f$ is surjective iff $f^{\vee}$ is injective.

Suppose $f$ is surjective and that there is $\ell \in W^{\vee}$ with $f^{\vee}(\ell) = 0$. That is, for all $v \in V$, $\ell(f(v)) = 0$. Since $f$ is surjective this means that $\ell(w) = 0$ for all $w \in W$ and thus $\ell = 0$.

Suppose $f$ is not surjective, and let $w \in W \setminus f(V)$. Then there is a linear functional $\ell$ on $W$ which vanishes identically on $f(V)$ but not at $w$. Thus $\ell$ is not $0$ but $f^{\vee}(\ell)$ is, so $f^{\vee}$ is not injective.

2) $f$ is injective iff $f^{\vee}$ is surjective.

Suppose $f$ is injective. Then we may view $V$ as a subspace of $W$, and the map $f^{\vee}$ is just restriction of linear functionals to a subspace. This is clearly surjective, since any linear map on a subspace can be extended to a linear map on the ambient space.

Suppose $f$ is not injective: let $0 \neq v \in V$ be such that $f(v) = 0$. Then no linear functional on $V$ with $L(v) \neq 0$ lies in the image of $f^{\vee}$, so $f^{\vee}$ is not surjective.

-