Order algebraizable logics

DOI10.1016/J.APAL.2012.10.013MaRDI QIDQ1935866zbMATH OpenOpenAlexFDO

Authors J. G. Raftery

Publication date 19 February 2013

Published in Annals of Pure and Applied Logic (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.apal.2012.10.013

zbMATH Keywords

abstract algebraic logic consequence relation deductive system order algebraizable logic polarity quasi-order

Mathematics Subject Classification ID

Abstract algebraic logic (03G27)

Review text

In the article under review the author provides an order-theoretic generalization of the classical notion of an algebraizable logic. I recall that a deductive system is said to be algebraizable if it is fully equivalent to the equational consequence relation of a class of algebras (with a common algebraic signature). For a given language \(\mathcal{L} = (\mathbf{\Sigma},V)\), where \(\mathbf{\Sigma}\) is an algebraic signature and \(V\) a set of variables, \(\mathbf{Tm}\), the free \(\mathbf{\Sigma}\)-algebra on \(V\), and a class \(\mathsf{K}\) of partially ordered \(\mathbf{\Sigma}\)-algebras, where a partially ordered \(\mathbf{\Sigma}\)-algebra is a pair \((\mathbf{A},\leq)\) with \(\mathbf{A}\) a \(\mathbf{\Sigma}\)-algebra and \(\leq\) a partial order on the underlying set \(A\) of \(\mathbf{A}\) (no compatibility between \(\leq\) and the operations of \(\mathbf{A}\) is assumed), the author defines the inequational consequence relation \(\models^{\leq}_{\mathsf{K}}\) of \(\mathsf{K}\) as the subset of \(\mathrm{Sub}(Tm^{2})\times Tm^{2}\), where \(Tm\) is the underlying set of \(\mathbf{Tm}\), consisting of all pairs \((\Gamma,\alpha\preccurlyeq\beta)\) in \(\mathrm{Sub}(Tm^{2})\times Tm^{2}\) such that, for every \((\mathbf{A},\leq)\) in \(\mathsf{K}\) and every homomorphism \(f\) from \(\mathbf{Tm}\) to \(\mathbf{A}\), if, for all \(\mu\preccurlyeq\nu\) in \(\Gamma\), \(f(\mu)\leq f(\nu)\), then \(f(\alpha)\leq f(\beta)\). Then, after defining for \((\mathcal{L},\mathbf{R})\), where \(\mathbf{R} = (R,\mathrm{rk})\), with \(\mathrm{rk}\) a mapping from \(R\) to \(\mathbb{N}-\{0\}\), the concept of \(\mathbf{R}\)-formula over \(\mathcal{L}\) as an expression \(r(\alpha_{0},\dots,\alpha_{n-1})\), where \(r\in R\) and \(\alpha_{0},\dots, \alpha_{n-1}\in Tm\), with \(\mathrm{rk}(r) = n\), the author defines an \(R\)-deductive system over \(\mathcal{L}\) as any consequence relation on the set of all \(\mathbf{R}\)-formulas that is substitution invariant. After this, for a deductive system \(\vdash\) (more precisely, for an \(R\)-deductive system), the author says that \(\vdash\) is order algebraizable if it is equivalent to the inequational consequence relation \(\models^{\leq}_{\mathsf{K}}\) of \(\mathsf{K}\) of a class \(\mathsf{K}\) of partially ordered \(\mathbf{\Sigma}\)-algebras. Notice that, since the equality relation is a (trivial) partial order, all algebraizable logics are order algebraizable. However, there are, as pointed out by the author, order algebraizable logics, e.g., Lambek calculus and the intensional fragments of linear and relevance logic, that are not algebraizable. Moreover, every order algebraizable logic is equivalential, but the converse is false, as shown by some fragments of Anderson and Belnap's entailment logic \(\mathbf{E}\), these facts, again, being indicated by the author. On the other hand, because polarities are implicit in the process of order algebraization, after defining the concept of polarity for \(\mathcal{L}\) as a pair \(M = (M^{+},M^{-})\), where \(M^{+}\cup M^{-}\) consists of unary polynomial forms (i.e., terms of the free \(\mathbf{\Sigma}\)-algebra on \(V\cup\{\ast\}\), where \(V\cap\{\ast\} = \emptyset\)), the author defines, for a binary relation \(\leq\) on \(A\), the underlying set of a \(\mathbf{\Sigma}\)-algebra \(\mathbf{A}\), when \(\leq\) is \(M\)-compatible with a subset \(F\) of \(A\) by saying that, for all \(a\), \(b\in A\), if \(a\leq b\) and \(p\in M^{+}(\mathbf{A})\), the set of all unary polynomials of \(\mathbf{A}\) induced by forms in \(M^{+}\), and \(p(a)\in F\), then \(p(b)\in F\); while if \(a\leq b\) and \(q\in M^{-}(\mathbf{A})\), the set of all unary polynomials of \(\mathbf{A}\) induced by forms in \(M^{-}\), and \(q(b)\in F\), then \(q(a)\in F\). Then he defines, for a polarity \(M\) and a subset \(F\) of \(A\), the (extended) \(M\)-Leibniz order of \(\mathbf{A}\) induced by \(F\) as the largest preorder (reflexive and transitive relation) on \(A\) that is \(M\)-compatible with \(F\), denoted by \(\preccurlyeq_{M}^{\mathbf{A}}(F)\), omitting the superscript when \(\mathbf{A}\) is \(\mathbf{Tm}\). The concept of Leibniz order is analogous to the Leibniz congruence of abstract algebraic logic. Next, he defines a polar system \((\vdash,M)\) as consisting of a sentential system \(\vdash\) and a polarity for \(\mathcal{L}\) and calls the maps \(F\mapsto \preccurlyeq_{M}^{\mathbf{A}}(F)\), with \(F\in Fi_{\vdash}(\mathbf{A})\), where \(Fi_{\vdash}(\mathbf{A})\) is the set of all \(\vdash\)-filters of \(\mathbf{A}\) taken over all \(\mathbf{\Sigma}\)-algebras \(\mathbf{A}\), the (extended) Leibniz order operator \(\preccurlyeq_{M}\) of \(\vdash\). After this, the author extends some central results of abstract algebraic logic to sentential systems with a polarity, in particular, a sentential logic with a polarity is order algebraizable if the Leibniz order operator has the following properties: (i) it is injective, (ii) it is isotone, (iii) it commutes with the inverse image operator of any homomorphism, and (iv) the \(M\)-Leibniz preorder is antisymmetric on the reduced models of \(\vdash\), i.e., when applied to filters that define reduced matrix models. Conversely, if a sentential system is order algebraizable in some way, then the order algebraization process naturally induces a polarity for which the Leibniz order operator has properties (i)--(iv).

Recommendations

Cited in

(28)

This page was built for publication: Order algebraizable logics

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1935866)