# 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 '13 at 15:45
Hi Asaf. I don't have any particular notion of duality in mind; perhaps the category-theoretical notion? –  goblin Jan 30 '13 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 '13 at 19:06

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 '13 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 '13 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 '13 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." –  goblin Feb 1 '13 at 11:12
@user: thanks for the note. I added the qualification as requested. –  Willie Wong Feb 1 '13 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 '13 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 '13 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 '13 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 '13 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 '13 at 15:34

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.

-
Assume $w'$ is linearly independent with $w$, is neither in the image of $f$, but $w'+w$ is in the image. Then $l(w'+w)$ is not $0$ so $f^\vee(l)\neq 0$. I came with this proof: $Ann \left( Im (f) \right)= \{\varphi \in W^\vee : \varphi(w)=0 \; \forall w \in Imf \}= \{\varphi \in W^\vee : f^\vee(\varphi)=0 \} = Ker f^\vee$ So $f^\vee$ injective iff $Ker f^\vee=0$ iff $Ann \left( Im (f) \right)= 0$ iff $Im (f)=W$ iff $f$ surjective. I'm not sure if this proof is right since as stated in Tu's book "An introduction to Manifolds" we need finite dimensions for $f$ surjective –  inquisitor Sep 16 '13 at 21:30
–  inquisitor Sep 16 '13 at 21:31
@inquisitor: if you're asking about the arguments above: it sure looks to me like they're valid without any finite-dimensional assumptions. I definitely assume the Axiom of Choice when doing infinite-dimensional linear algebra... –  Pete L. Clark Sep 16 '13 at 21:39