Exercise 2.2.13

Let be a map of sets. Let be the inverse image functor, sending a subset to its preimage under . Consider and as ordered sets (via inclusion) – then is order preserving. Then, further considering and as categories makes into a functor.

A left adjoint to is the the direct image functor, , sending a subset to its image under . We claim . The unit is the statement “for all , ”, which is clearly true. Likewise, the counit is the statement “for all , ”, clearly true as well.

The right adjoint is much harder. We will denote it and call it the “complemented image functor”. Define , where denotes the complement in the appropriate set ( or ). The unit and counit statements are a bit nontrivial and require proof. The unit says “For all , ”. 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 , ”. We show this directly:

thus, the unit and counit statements are true, and we have an adjunction .

So, has left and right adjoints: .

Now, let’s apply this to a particular situation. Let and be sets and be projection. We will regard a subset as a predicate that is true on the members of . Similarly subsets are 2-predicates .

We wish to determine what the left and right adjoints from the previous construction, and , represent in terms of predicates. This is really just a matter of interpreting the definitions in the language of logic. Given a 2-predicate , one can see that is the predicate

which is a predicate in one variable . Since is defined in terms of in the first place, we can simply plug it in and interpret complement as “not” (). So is the predicate

Of course, this reduces to

So, when we take as the projection onto , corresponds to the operation of placing “” in front of the input, and places “” in front of the input.