Why does the lack of a rule of necessitation mean that a logic is not algebraizable?

66 Views Asked by At

Why does the lack of a rule of necessitation mean that a logic is not algebraizable?

The introduction to Algebraizable Logics by W. J. Blok and Don Pigozzi starts out with a discussion of what the algebra of propositional formulas introduced by Tarski is. The construction seems straightforward, start off with the "raw" "syntactic" algebra given by your propositional logic and then identify well-formed formulas where implications in both directions can be proven.

The book mentions in passing that the modal logics S1, S2, and S3, which lack the rule of necessitation given below, do not have an algebraization.

$$ \;\; \text{If a logic $L$ has the rule of necessitation, then $\vdash \varphi$ implies $\vdash \square \varphi$ for every $\varphi$. } $$

In particular the book provides the following argument,

In this case [the case of S1, S2, S3], the relation defined in (1) is not a congruence relation because $\vdash \phi \to \psi$ does not imply $\vdash \square \phi \to \square \psi$.

The relation defined in one is reproduced below with a slight change of notation,

$$ \varphi \simeq \psi \;\; \text{if and only if} \;\; \vdash \varphi \to \psi \;\; \text{and} \;\; \vdash \varphi \to \psi \;\;\;\; \textit{is $\text{(1)}$ in the text} $$

$\vdash$ is a consequence relation that is supposed to be intrinsically associated with the logic under study, I think. The book does not mention explicitly whether we're building $\vdash$ or whether we're given $\vdash$ up front.

It's not clear to me why the book's claim is true. In particular, it's not clear to me what breaks when you try to carry out the construction to build the algebra modded out by the congruence given the "raw" algebra associated with a propositional logic.

First of all, I am assuming that an algebra, fundamentally, is a structure in the sense of model theory associated with a signature and a theory. The signature must not have any relation symbols. Every well-formed formula in the theory must be quantifier-free (and therefore every variable that appears in a well-formed formula in the theory is implicitly universally quantified).

If I have a propositional logic $L$, then I think of it as a structure by considering all well-formed formulas as distinct elements in its domain, and considering all the connectives as functions.

So, $a\land b$ and $b \land a$ are distinct elements in the domain. Also, $(\land)$ is a binary function that sends well-formed formulas to well-formed formulas.

My theory of $L$ as an algebra would then have no axioms. $(\land)$ isn't known to be commutative or associative or anything like that. $(\lnot)$ is similarly not known to be an involution.

This raw algebra has too many distinctions, so we impose a congruence. Repeating the definition above, here's our congruence.

$$ \varphi \simeq \psi \;\;\text{if and only if}\;\; \vdash \varphi \to \psi \;\; \text{and} \;\; \vdash \psi \to \varphi $$

Since $ \simeq $ is a congruence, that means there's a corresponding homomorphism $\Delta$ subject to the following rules. $\Delta$ sends us to a new algebra with the same signature.

$$ \Delta(\lnot \varphi) = \lnot \Delta(\varphi) $$ $$ \Delta(\varphi \land \psi) = \Delta(\varphi) \land \Delta(\psi) $$

And so on for other connectives. Our first rule then becomes.

$$ \Delta(\varphi) = \Delta(\psi) \;\; \text{if and only if} \;\; \vdash \varphi \to \psi \;\; \text{and} \;\; \vdash \psi \to \varphi $$

If the rule of necessitation fails, this means there exists a well-formed formula $c$ so that $\vdash c$ holds and $\not\vdash \square c$ holds.

However, we don't really know anything about $\square$ up front. If $\square$ were replaced with another unary connective like $\lozenge$ or $\lnot$, the failure of the analogue of the rule of necessitation would be unremarkable.

So, it seems deriving a contradiction here depends on other properties of modal logics like S1, S2, and S3, but it's not clear to me what they are.

As a follow-up question, although modal logics like S1, S2, and S3 are badly behaved with respect to the congruence relation defined in the book, they definitely have a "raw" "syntactic" algebra associated with them. Is there a different congruence relation we can mod out by in their case that still gives us an interesting object of study?