Consider the set of formulas of a logic. If there was only one sort of "unary" deduction $\phi \Rightarrow \psi$ - like $(\forall x)\phi(x) \Rightarrow \phi(a)$ - we would immediately have a *category of formulas* (with deductibility $\Rightarrow$ as morphism). But alas, there are other ("higher") deduction rules, e.g. 


$\lbrace p, q \rbrace \Rightarrow p \wedge q$ (rule of conjunction)


$\lbrace p\rightarrow q, p \rbrace\Rightarrow q$ (modus ponens)



> 
> (How) can formulas of "classical logics"
>  (propositional and FO) be made into a
>  category despite of those other
>  relations (= rules)?
> 
> 
> 



Categories of logical formulae
Classical propositional logic is basically a boolean algebra, which may be viewed as a poset, which may be viewed as a category. We at the very least need to fix the primitive predicates; then the objects of the category are the well-formed formulae, and we have a morphism $P \to Q$ if and only if $\{ P \} \vdash Q$, where $P$ and $Q$ are well-formed formulae. Under this scheme, the product is logical conjunction, the coproduct is logical disjunction, and the exponential is material implication. (Write out the universal properties in logical form and you'll see they correspond to the natural deduction rules for the respective logical operators.)


We may also talk about the category of boolean algebras, where the morphisms are boolean algebra homomorphisms, but I think that's not what you're looking for.


As for first-order logic — a similar thing can be done, but now we have to introduce several (indeed, infinitely many) categories. Firstly, recall that a formula in first-order logic can have free variables. Formulae that have the same free variables live in the same categories; as before we have a morphism $\phi(x, y, \ldots, z) \to \psi(x, y, \ldots, z)$ iff $\{ \phi(x, y, \ldots, z) \} \vdash \psi(x, y, \ldots, z)$, and we have categorical products, coproducts, and exponentials corresponding to $\land$, $\lor$, and $\implies$ as before.


What do $\forall$ and $\exists$ correspond to? Well, remember that the formulae inside a given category have the at most a particular set of free variables, so these operations necessarily take objects from one category to another, i.e. they must be functors of some kind, and indeed they are. Let $\mathrm{Form}(x, y, \ldots, z)$ denote the category of formulae with free variables contained in $\{ x, y, \ldots, z \}$. Trivially, we have inclusion functors $\* : \mathrm{Form}(x, y, \ldots, z) \to \mathrm{Form}(x, y, \ldots, z, t)$. Conversely, $\forall t$ is a functor $\mathrm{Form}(x, y, \ldots, z, t) \to \mathrm{Form}(x, y, \ldots, z)$. It turns out $\forall t$ is a right adjoint for $\*$ — writing out the definition of adjunction gives the natural deduction rules for $\forall$ introduction and elimination. Similarly, $\exists t$ is a functor of the same type, and is a left adjoint of $\*$.


This categorical viewpoint of logic is discussed at various points in Awodey's *Category Theory*, but is not the main aim of the book.


