2
$\begingroup$

I was reading this question which asks about the equivalent of Boolean algebras for relevant logic.

In the comments, Noah Schweber mentions that the relevant logic E is not algebraizable. In the book Algebraizable Logics, Blok and Pigozzi also mention in the introduction that the Lewis Systems S1, S2, S3 are not algebraizable, although S4 and S5 are.

I have tried off and on over the years to read Algebraizable Logics and develop an understanding of what exactly algebraizable and protoalgebraizable logics are, without a lot of success. There are some other sources like the SEP article on algebraic propositional logic that are very well written, but hard to use if you're trying to go from 0 to 60 rather than 60 to 100.

I'd like to try something different and build up a collection of non-algebraizable logics that are simple as possible.

No logic too simple.

For example, I'm pretty sure that the $\land$-only fragment of classical logic is not algebraizable because you can't cobble together $\land$-s to make a formula that looks like implication or equivalence.

This $\land$-only logic, though, doesn't exercise any interesting facets of the definition of algebraizability and thus isn't a good test case for probing it.

$\endgroup$
1
  • $\begingroup$ Czelakowski's book Protoalgebraic logics (and the general search term "protoalgebraic logic") might be a good source. $\endgroup$ Dec 7, 2023 at 1:58

1 Answer 1

0
$\begingroup$

Here's an example.

∧  F U T    ¬
F  F F F    F  T
U  F U U    U  U
T  F U T    T  F

If the designated truth values are $T$ and $U$, then the equation $\lnot(a \land \lnot a) \approx a$ holds for precisely the designated truth values and thus the logic is algebraizable.

If the sole designated truth value is $T$, then there is no set of equations identifying the designated truth values. $U$ is a fixed point of both connectives $\land$ and $\lnot$ and there are no truth value constants, therefore any possible set of equations will include $U$. Thus this logic is not algebraizable.


From what I can gather, being algebraizable is equivalent to having a matrix semantics in which the set of designated truth values is definable with a finite set of equations.

More precisely,

Let $L$ be an algebraic signature with functions $f^\to$ corresponding to $\to$ and likewise for each connective.

Let $\text{EQN}$ be the equational fragment of FOL, where the sole connective is $=$ and the sole quantifier is $\forall$. $\text{EQN}$ does not have higher order equivalences (so no $\leftrightarrow$ connective), unlike equational logic on Wikipedia

Let $D(a)$ be a finite set of well-formed $L$-formulas whose open variables are among $\{a\}$. Intuitively, $D(a)$ expresses that $a$ has a designated truth value.

Let $\Delta$ be a not necessarily finite set of sentences. Intuitively, $\Delta$ is a preamble establishing the equivalences in the logic such as double negation being equivalent to the absence of any negation: $[\forall x](f^\lnot(f^\lnot(x)) = x)$, which corresponds to $\lnot\lnot x \approx x$ in traditional notation.

A deductive system $S = (\mathcal{L}, \vdash_S)$ with $\vdash_S$ being a consequence relation is algebraizable if and only if there exists a set of sentences $\Delta$ and a finite set of formulas $D(a)$ such that for all $\Gamma, \psi$, $\Gamma \vdash \psi$ if and only if $\Delta, \{ D(\varphi) : \varphi \in \Gamma \} \models_{\text{EQN}} D(\psi)$.

This is a little different from the presentation in Blok and Pigozzi. Here $\Delta$ serves the role that the quasivariety $K$ of $L$-algebras does. I think this notion is the same as the one in Blok and Pigozzi, but at the moment I don't have a proof.

In other words, when looking at a matrix semantics for a logic, that logic is algebraizable if and only if the set of designated truth values is definable using a finite set of equations.

However, the definition of algebraizability is more general than this, it takes as an input a consequence relation, not a matrix semantics. The matrix semantics is paraphrased away, but it is lurking there in the background and motivates the definition of algebraizability.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .