# What's the dual of “inverse image” in Set?

My book defines the "inverse image" as the pullback of a morphism $f:A\to B$ and a monomorphism $i:C \rightarrowtail B$.

If the category under consideration is Set, and we interpret $i$ as the inclusion $C \subseteq B$, the object that completes the pullback square can be interpreted as the subset $f^{-1}(C)$, where $f^{-1}$ denotes the standard (i.e. set-theoretical) inverse of $f$, regarded as a function of sets. (Hence the name of this construction.) The remaining arrows in the pullback correspond (essentially) to the inclusion $f^{-1}(C) \subseteq A$ and the restriction of $f$ to $f^{-1}(C)$.

Is it possible to give a useful interpretation (in Set) to the dual of this construction?

The best I can come up with is to produce the pushout diagram for the morphisms $f^{\;\mathrm{op}}:\mathcal{P}(B)\to \mathcal{P}(A)$ and $i^{\;\mathrm{op}}:\mathcal{P}(B)\twoheadrightarrow \mathcal{P}(C)$ (where $\mathcal{P}(X)$ denotes the power-set of $X$), derived from the (function) inverses of $f$ and $i$. The object that completes this pushout square is indeed $\mathcal{P}(f^{-1}(C))$, but this is not a very illuminating construction. In particular, it does not provide any meaningful interpretation to the "epicity" of $i^{\;\mathrm{op}}$ to go with the interpretation of the monicity of $i$ as the inclusion $C \subseteq B$.

(Basically, I'm looking for an interpretation based on the pushout of a morphism $g:B \to A$ and an epic morphism $\sigma:B\twoheadrightarrow B/R$, where $B/R$ denotes the quotient space of $B$ with respect to some suitable equivalence relation $R$ on $B$. The trick is defining the "suitable" equivalence relation $R$, and the object and morphisms that complete the pushout diagram.)

Thanks!

-
I removed the set-theory tag after reading its description. –  Rasmus Nov 8 '11 at 20:38
@kjo: I've written things up; I think I miswrote that comment, and I deleted it while I was writing, but you had probably already replied. The object you want is $A/S$, where $S$ is the smallest equivalence relation on $A$ that contains $g(R)$. –  Arturo Magidin Nov 8 '11 at 21:07

The key here is that just like monic into $B$ can be identified with subsets of $B$, epics from $B$ can be identified with equivalence relations on $B$ (given $p\colon B\to C$, define $b\sim b'$ if $p(b)=p(b')$; then there is a natural bijection between $C$ and the set of its singletons, and there is a natural bijection between the set of singletons and the set of equivalence classes in $B$ under $\sim$). The dual of the inverse image is going to be the equivalence closure of the image of this equivalence relation.

For the dual construction we would start, as you note, with a function $f\colon B\to A$, and an epi $p\colon B\to C$, and look at the pushout diagram $$\begin{array}{ccc} B & \stackrel{f}{\to} & A\\ {\tiny p}\downarrow & &\\ C & & \end{array}$$ We then form the pushout $$\begin{array}{ccc} B & \stackrel{f}{\to} & A\\ {\tiny p}\downarrow & &\downarrow\\ C &\to & Y. \end{array}$$ $Y$ can be identified with the disjoint union modulo an equivalence relation, $$Y = A\amalg C/\sim$$ where $\sim$ is the smallest equivalence relation on $A\amalg C$ such that $f(b)\sim p(b)$. It is somewhat unfortunate that this is harder to figure out than the pullback...

Because $p$ is epi, that means that for every $c\in C$ there exists $a\in A$ such that $a\sim c$. So we can take $A$ as an intermediate step between $A\amalg C$ and $Y$. Now note that if $p(b)=p(b')$, then $f(b)\sim f(b')$. So let $R$ be the equivalence relation induced on $B$ by $p$, namely $bRb'$ if and only if $p(b)=p(b')$, and let $S$ be the smallest equivalence relation on $A$ that contains $f(R)$. This is the smallest equivalence relation on $A$ for which the induced function $\overline{f}\colon B/R\to A/S$ is well-defined.

If $aSa'$, then either $a=a'$ or else there exist $a_1,\ldots,a_n\in A$ such that $a=a_1$, $a'=a_n$, and for each $i$ we have $(a_i,a_{i+1})\in f(R)$ or $(a_{i+1},a_i)\in f(R)$. But since $R$ is symmetric, this is equivalent to asking that $(a_i,a_{i+1})\in f(R)$; hence there exist $b_i,b_{i+1}\in B$ such that $p(b_i)=p(b_{i+1})$ and $f(b_i)=a_i$, $f(b_{i+1})=a_{i+1}$. So $aSa'$ if and only if $a=a'$, or there exist $b_1,\ldots,b_n\in B$ with $f(b_1)=a$, $f(b_n)=a'$, and for $i$, $1\leq i\lt n$, $p(b_i) = p(b_{i+1})$. But for this to hold, we must have $p(b_1)=p(b_2)=\cdots=p(b_n)$. So $aSa'$ if and only if $a=a'$, or else there exist $b,b'\in B$ with $p(b)=p(b')$, $a=f(b)$, and $a'=f(b')$.

I claim that $A/S$ is the pushout. It fits into the pushout diagram, by mapping from $A$ as the quotient, and mapping from $C$ by taking $c\in C$, selecting any preimage of $c$ in $B$, and mapping this to $A$ via $f$ and then to $A/S$. This is well-defined by definition of $S$, and makes the diagram commutative.

Let $Z$ be any set, and $h\colon C\to Z$ and $m\colon A\to Z$ be maps such that $h\circ p = m\circ f$. I claim that $m$ factors through $S$. If $aSa'$, then either $a=a'$, in which case $m(a)=m(a')$; or else there exist $b,b'\in B$ such that $p(b)=p(b')$, $f(b)=a$, and $f(b') = a'$. Then $$m(a) = m(f(b)) = h(p(b)) = h(p(b')) = m(f(b')) = m(a').$$ Thus, $m$ factors through $A/S$.

I claim that $h$ also factors through $A/S$. If $c$ and $c'$ map to the same element of $A/S$, then there exist $b,b'\in B$ with $p(b)=c$, $p(b') = c'$, and $[f(b)]=[f(b')]$ in $A/S$. But $[f(b)]=[f(b')]$ in $A/S$ implies that either $f(b)=f(b')$, in which case we have $$h(c) = h(p(b)) = m(f(b)) = m(f(b')) = h(p(b')) = h(c'),$$ or else that there exist $x,x'\in B$ with $f(x)=f(b)$, $f(x')=f(b')$, and $p(x)=p(x')$. Then we have \begin{align*} h(c) &= h(p(b)) = m(f(b)) = m(f(x)) = h(p(x))\\ &= h(p(x')) = m(f(x')) = m(f(b')) = h(p(b'))\\ &= h(c'). \end{align*} So either way, $h$ factors through $A/S$.

Therefore, $A/S$ is the pushout of the diagram.

So, to answer your question: given a function $f\colon B\to A$ and an epi $p\colon B\to C$, identify $p$ with the equivalence relation on $B$ that it determines; then consider the smallest equivalence relation on $A$ that contains the image of this equivalence relation; and take the quotient of $A$ modulo that equivalence relation.

-

Arturo's reply (which I've already accepted) really nails it, but here I would like to add some of what I learned from studying it (and others may find helpful). (The remarks below desperately cry out for diagrams, but unfortunately my LaTeX-fu is not up to the task. Therefore, it may be a good idea to follow along with pencil and paper in hand.)

[Some notation: if $f$ and $g$ are morphisms $f;g$ is defined as $g\circ f$. I use $\langle x, 0\rangle$ and $\langle y, 1\rangle$ to refer to elements of the disjoint union $X \amalg Y$ of sets $X$ and $Y$ whenever $x \in X$ and $y \in Y$. If $f:X\to Y$ is a surjective function, I will use $E_f$ to represent the equivalence relation induced by $f$ on $X$, i.e.

$$E_f = \{(x, x'): f(x) = f(x')\} \subseteq X \times X$$

I will use the shorthand $X/f$, instead of $X/E_f$, to represent the quotient of $X$ with respect to $E_f$. For any relation $R \subseteq X \times X$, I'll use $\overline{R}$ to represent the equivalence closure of $R$ (i.e. the smallest equivalence relation on $X$ that contains $R$). Furthermore, for any function $f:X\to Y$, the shorthand $f(R)$ denotes the relation on $Y$ given by $\{(f(x), f(x')):x, x' \in X\}$. I use both $\prod$ and $\times$ to refer to the product of sets, to emphasize either its categorical or its set-theoretical aspect, respectively.]

First, at the beginning of his reply Arturo points out that the pushout $Y$ can be identified with $A \amalg C/\!\!\!\sim$, where $\sim$ is the equivalence closure of $$\{\,(\;\langle f(b), 0 \rangle, \;\;\langle p(b), 1 \rangle\;)\;\;|\;\;b \in B\,\}\;\; \subseteq (A\amalg C) \times (A\amalg C).$$ In fact it is worthwhile to realize that such a construction of the pushout in Set is possible for any pair of functions with a common domain, even when neither of them is a surjection.

Second, it follows from Arturo's derivation that in this special case (where $p:B \twoheadrightarrow C$ is a surjection), the pushout $A \amalg C/\!\!\!\sim$ turns out to be Set-isomorphic to a quotient $A/\!\!\!\sim$ of $A$, and it is interesting to see why this is. (It goes without saying that the "$\sim$" in $A \amalg C/\!\!\!\sim$ is necessarily a different equivalence relation from the "$\sim$" in $A/\!\!\!\sim$.) As Arturo noted, the surjectivity of $p$ ensures that every equivalence class in $A \amalg C/\!\!\!\sim$ contains an element $a$ that "came from $A$" (into the disjoint union $A \amalg C$, that is). (BTW, I think this is the key observation; it's the one that I was missing.) Therefore, in this case, if we interpret $A \amalg C/\!\!\!\sim$ as a partition of $A \amalg C$, it is easy to see that, by removing all the $C$-elements from the classes of this partition, we obtain a (Set-isomorphic) partition of $A$. (Note that this would not be the case if the partition of $A \amalg C$ contained a class consisting only of $C$-elements, which is what happens when $p$ is not surjective.) The new partition by this procedure clearly represents a quotient $A/\!\!\!\sim'$, and this quotient is Set-isomorphic to $A \amalg C/\!\!\!\sim$. It's not hard to show that the quotient $A/\!\!\!\sim'$ suggested by this informal argument is the same as the quotient $A/\!\!\!\sim$ produced by Arturo's more thorough one.

Third, it is interesting to see how the counterpart (through duality) of this Set-isomorphism

$$\frac{A \amalg C}{\sim} \simeq \frac{A}{\sim}$$

shows up in the original construction of the inverse image. To do this, it is helpful to first contrast the constructions (in Set) of the pushout for functions $\alpha:Z\to X$ and $\beta:Z\to Y$ and the pullback for functions $\gamma:U\to W$ and $\delta:V\to W$. As already described, the pushout of $\alpha$ and $\beta$ is the quotient $X \amalg Y/\!\!\!\sim_{\alpha, \beta}$ of $X\amalg Y$ by the equivalence relation

$$\sim_{\alpha, \beta}\;\;=\;\;\{\,(\;\langle \alpha(z), 0 \rangle, \;\;\langle \beta(z), 1 \rangle\;)\;\;|\;\;z \in Z\,\}.$$

Dually, the pullback of $\gamma$ and $\delta$ is the subset $U\times_{\gamma, \delta}V$ of $U\;\Pi\; V$ given by

$$U\times_{\gamma, \delta}V = \{(u, v):\gamma(u) = \delta(v)\}$$

The morphisms that complete the pushout diagram for $\alpha:Z\to X$ and $\beta:Z\to Y$ are the compositions of the canonical inclusions $\iota_X:X\hookrightarrow X \amalg Y$ and $\iota_Y:Y\hookrightarrow X \amalg Y$ with the projection of $X \amalg Y$ onto the quotient $X \amalg Y/\!\!\!\sim_{\alpha,\beta}$. In fact, the pushout $X \amalg Y/\!\!\!\sim_{\alpha, \beta}$ is the coequalizer of $\alpha;\iota_X:Z\to X \amalg Y$ and $\beta;\iota_Y:Z\to X \amalg Y$.

Likewise, the morphisms that complete the pullback diagram for $\gamma:U\to W$ and $\delta:V\to W$ are the compositions of the inclusion of the subset $U\times_{\gamma, \delta}V$ into $U\;\Pi\; V$ with the canonical projections $\pi_U:U\;\Pi\; V \twoheadrightarrow U$ and $\pi_V:U\;\Pi\; V \twoheadrightarrow V$. In fact, the pullback $U\times_{\gamma, \delta}V$ is the equalizer of $\pi_U;\gamma$ and $\pi_V;\delta$.

Furthermore, in the special case where, say, $\beta:Z\to Y$ happens to be surjective the pushout $X \amalg Y/\!\!\!\sim_{\alpha, \beta}$ becomes Set-isomorphic with some quotient $X/\!\!\!\sim$ of $X$ (as Arturo's derivation showed). Therefore, in this case, the map $X \to X \amalg Y/\!\!\!\sim_{\alpha, \beta}$ is actually a projection (i.e. it is surjective). It can be interpreted as the "push-forward" (or "[forward] image") of the equivalence $E_\beta$ induced by $\beta$ on $Z$.

Likewise, in the special case where, say, $\delta:V\to W$ happens to be injective the pullback $U\times_{\gamma, \delta}V$ becomes Set-isomorphic to a subset $\gamma^{-1}(\delta(V))$ of $U$. (This last isomorphism is a consequence of the fact that, when $\delta$ is injective, for every $u \in U$ there is at most one $v \in V$ such that $(u, v) \in U\times_{\gamma, \delta}V$, therefore $U\times_{\gamma, \delta}V$ is Set-isomorphic to its inclusion (through $U\;\Pi\; V$) into $U$.) It's not hard to show that this inclusion is the inverse image $\gamma^{-1}(\delta(V)) \subseteq U$.

Lastly, (and now driving the analogy in the other direction), the "inverse image" tells us something about how a function maps subsets of its domain into subsets of its codomain; the "co-inverse image", or, more naturally, "forward image", tells us something about how a function maps quotient of its domain onto quotients of its codomain (namely by "pushing forward", with the function, the equivalence on the domain, and expanding the resulting relation on the codomain just enough to make it into a bona fide equivalence relation).

More precisely, the "inverse image" $\gamma^{-1}(V)$ is the largest subset of $U = \mathrm{dom}(\gamma)$ that, when the $\gamma$ is restricted to it, gets mapped into $V \subseteq \mathrm{cod}(\gamma)$. Likewise, its dual, $X/\!\!\!\sim$ (the "co-inverse image"), obtained as Arturo described, is the quotient of $X = \mathrm{cod}(\alpha)$ induced by the smallest equivalence $\sim$ on $X$ into which $\alpha$ will map the equivalence $E_{\beta}$ on $Z = \mathrm{dom}(\alpha)$, i.e. in the notation described at the beginning of this post $\sim\;=\;\overline{\alpha(E_{\beta})}$.

For me this example really brings out the intimate connections that exist among pullbacks, equalizers, products, injections/inclusions/subsets, and "restricting" a function, on the one hand, and among pushouts, co-equalizers, co-products, surjections/projections/quotients, and "coarse-graining" a function on the other.

In all the category theory books that I've looked at, these results are shoved under the rug with a quick nod at "duality". As I think this example shows, it pays off to work out exactly what is it that duality entails.

-