2
$\begingroup$

I have a category theory homework problem which asks: "In first-order logic, why does $\forall$ not have a right adjoint?" The typical argument is that:

  1. If for some operator $\cdot$ it could be asserted $\forall \dashv \cdot$, then $\cdot$ would be a kind of coproduct.
    1. If $\forall$ preserves coproducts, then $\forall y(\phi y \vee \psi y) \dashv \vdash \forall y \phi y \vee \forall y \psi y$.
    2. Since 2 does not hold, $\forall$ must not preserve coproducts, and therefore $\forall$ does not have any kind of right adjoint.

I have a few questions about this:

  1. Why exactly does 2 not hold? Is it because the expression is equivalent to $\forall y(\phi y \vee \psi y) \dashv \vdash \forall y_1 \phi y_1 \vee \forall y_2 \psi y_2$?
    1. The meaning of $\dashv$ and $\vdash$ are unclear to me in the context of expressions. I understand what $* \dashv \forall$ means, but I need help understanding adjointness in terms of expressions.
    2. How can the relation of $\forall$ to the particular coproduct $\vee$ be generalized to all coproducts, such that all possible right adjoints to $\forall$ are ruled out?
  • 0
    Is there any relationship between the category theory usage of $\vdash$ and its usage in logic? I've seen them correlated via Heyting algebra, like $\vdash$ is regarded as the arrow, but I'm not sure if that applies here.2012-08-13

1 Answers 1

2

I'm only answering question 1 because I don't know the answers to the others. For question 1, it suffices to give a counter example. A counter example is where $\psi$ is the negation of $\phi$. Then the left side says "for all $y$, either $\phi y$ or not $\phi y$" which is true for any $\phi$ by the law of the excluded middle. The right hand side says "Either for all y $\phi y$, or for all $y$ not $\phi y$" which claims that $\phi$ is true either for all $y$ or for none of them. Which is clearly wrong in general, and therefore it would be disastrous if you could derive it from the tautology on the left.

  • 0
    Ah, so it's possible to have $\forall y(\phi y \vee \psi y)$, and yet have neither $\forall y \phi y$ nor $\forall y \psi y$. I see it now, thanks!2012-08-13