§ Quantifiers as adjoints

• Consider S(x, y) ⊂ X × Y, as a relation that tells us when (x, y) is true.
• We can then interpret ∀x, S(x, y) to be a subset of Y, that has all the elements such that this predicate holds. ie, the set { y : Y | ∀ x, S(x, y) }.
• Similarly, we can interpret ∃x, S(x, y) to be a subset of Y given by { y : Y | ∃ x, S(x, y) }.
• We will show that these are adjoints to the projection π: X × Y → Y.
• Treat P(S) to be the boolean algebra of all subsets of S, and similarly P(Y).
• Then we can view P(S) and P(Y) to be categories, and we have the functor π: P(S) → P(Y).
• Recall that in this boolean algebra and arrow a → b denotes a subset relation a ⊆ b.

§ A first try: direct image, find right adjoint

• Suppose we want to analyze when π T ⊆ Z, with the hopes of getting some condition when T ⊆ ? Z where ?is some to-be-defined adjoint to π.
• See that π T ⊆ Z then means ∀ (x, y) ∈ T, y ∈ Z.

     T
   t t t
   t t t
    |
    v
---tttt---- π(T)
-zzzzzzzzz--Z

• Suppose we build the set Q(Z) ≡ { (x, y) ∈ S : y ∈ Z }. That is to say, Q ≡ π⁻¹(Z). ( Q for inverse of P).
• Then, it's clear that we have π T ⊂ Z implies that T ⊆ Q(Z) [almost by definition ].
• However, see that this Q(Z) construction goes in the wrong direction; we want a functor from P(S) to P(Y), which projects out a variable via ∃ / ∀. We seem to have built a functor in the other direction, from P(Y) to P(S).
• Thus, what we must actually do is to reverse the arrow π: S ⊆ X × Y → Y, and rather we must analyze π⁻¹ itself, because its adjoints will have the right type.
• However, now that we've gotten this far, let's also analyze left adjoints to π.

§ Direct image, left adjoint

• Suppose that Z ⊆ π T. This means that for every y ∈ Z, there is some x_y such that (x_y, y) ∈ T

     T
   t t t
   t t t
    |
    v
---tttt---- π(T)
----zz--------Z

• I want to find an operation ? such that ? Z ⊆ T.
• One intuitive operation that comes to mind to unproject, while still reminaing a subset, is to use π⁻¹(Z) ∩ T. This would by construction have that π⁻¹(Z) ∩ T ⊆ T.
• Is this an adjoint? we'll need to check the equation :).

§ Inverse image, left adjoint.

• Suppose we consider π⁻¹ = π* : P(Y) → P(S).
• Now, imagine we have π*(Z) ⊆ T.

    S
    -
    -
   tttt
   tztt
   tztt T
   tztt
    ^^
    || π*(Z)
----zz-------Z

• In this case, we can say that for each z ∈ Z, for all x ∈ X such that (x, z) ∈ S, we had (x, z) ∈ T.
• Consider the set ∀ T ≡ { y ∈ T: ∀ x, (x, y) ∈ S => (x, y) ∈ T}.
• Thus, we can say that π*(Z) ⊂ T iff Z ⊂ ∀ T.
• Intuitively, T ⊂ π*(π(T)), so it must be "hard" for the inverse image of a set Z ( π*(Z)) to be contained in the set T, because inverse images cannot shrink the size.
• Furthermore, it is the right adjoint to π*(Z) because the ???