Exercise 2.2.13 Let f : K \rightarrow L be a map of sets. Let f^* : \mathscr{P}(L) \rightarrow \mathscr{P}(K) be the inverse image functor, sending a subset B to its preimage under f. Consider \mathscr{P}(L) and \mathscr{P}(K) as ordered sets (via inclusion) – then f^* is order preserving. Then, further considering \mathscr{P}(L) and \mathscr{P}(K) as categories makes f^* into a functor. A left adjoint to f^* is the the direct image functor, f_* : \mathscr{P}(K) \rightarrow \mathscr{P}(L), sending a subset A \subseteq K to its image under f. We claim f_* \dashv f^*. The unit \eta is the statement “for all A \in \mathscr{P}(K), A \subseteq f^* f_* A”, which is clearly true. Likewise, the counit is the statement “for all B \in \mathscr{P}(L), f_* f^* B \subseteq B”, clearly true as well. The right adjoint is much harder. We will denote it f_*^c and call it the “complemented image functor”. Define f_*^c(A) = f_*(A^c)^c, where (\cdot)^c denotes the complement in the appropriate set (K or L). The unit and counit statements are a bit nontrivial and require proof. The unit says “For all B \in \mathscr{P}(L), B \subseteq f_*^c f^* B”. This is non-trivial, and we show its truth via the following chain of implications: % So by contrapositive we have the unit. the counit is the statement “For all A \in \mathscr{P}(K), f^* f_*^c A \subseteq A”. We show this directly: % thus, the unit and counit statements are true, and we have an adjunction f^* \dashv f_*^c. So, f^* has left and right adjoints: f_* \dashv f^* \dashv f_*^c. Now, let’s apply this to a particular situation. Let X and Y be sets and p : X \times Y \rightarrow X be projection. We will regard a subset S \subseteq X as a predicate S(x) that is true on the members of S. Similarly subsets R \subseteq X \times Y are 2-predicates R(x,y). We wish to determine what the left and right adjoints from the previous construction, p_* and p_*^c, represent in terms of predicates. This is really just a matter of interpreting the definitions in the language of logic. Given a 2-predicate R(x,y), one can see that p_* R is the predicate \exists y \in Y \tst R(x,y) which is a predicate in one variable x \in X. Since p_*^c is defined in terms of p_* in the first place, we can simply plug it in and interpret complement as “not” (\neg). So p_*^c R is the predicate \neg (\exists y \in Y \tst \neg R(x,y)) Of course, this reduces to \forall y \in Y, R(x,y) So, when we take p as the projection onto X, p_* corresponds to the operation of placing “\exists y \in Y” in front of the input, and p_*^c places “\forall y \in Y” in front of the input.