Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?
share|improve this question
2  
$P \vdash Q$ in logic means $Q$ is derivable from $P$. $P \dashv \vdash Q$ is an abbreviation for "$P \vdash Q$ and $Q \vdash P$". A left adjoint preserves all coproducts, so if a functor doesn't preserve even one coproduct, it cannot be a left adjoint. –  Zhen Lin Aug 13 '12 at 17:18
    
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. –  Byron Hawkins Aug 13 '12 at 20:38

1 Answer 1

up vote 2 down vote accepted

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.

share|improve this answer
    
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! –  Byron Hawkins Aug 13 '12 at 20:31

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.