An Essay in Matrix Semantics for Consequence Relations

The objective of this chapter is to study abstract sentential calculi (alternatively, abstract propositional logics) construed as pairs \((\mathcal {L}, \vdash )\) . Here, \(\mathcal {L}\) is the sentential language (absolutely free algebra) generated by a countably infinite set of propositional variables and a finite set of finitary connectives, and \(\vdash \) is a multiple-conclusion consequence relation. To call a binary relation between arbitrary sets of formulas of \(\mathcal {L}\) a (multiple-conclusion) consequence relation, it is assumed that it fulfills the three laws—(R), (M), and (C): Some relations may be additionally structural in the sense that they satisfy the following condition, which takes into account the algebraic structure of \(\mathcal {L}\) : Section 3 reviews the basic properties of consequence relations from a lattice-theoretical point of view. In particular, a description is given of the least consequence relation extending a fixed set of pairs (X, Y ), where X and Y  are finite sets of formulas. The main thread of discussion appears in Sect. 4, extends to the rest of the work, and concerns consequence relations determined by (logical) matrices, i.e., the relations of the form \(\vdash _M\) , where \(M = (\mathcal {A}, D)\) is a matrix for \(\mathcal {L}\) . One defines \(X\vdash _{M} Y\) to mean that, for every homomorphism h from \(\mathcal {L}\) to \(\mathcal {A}\) , either \(h(\alpha )\) is undesignated (does not belong to D) for some \(\alpha \) in X or \(h(\beta )\) is designated for some \(\beta \) in Y . Since every such a relation \(\vdash _M\) is structural, in discussing the problem of representing a consequence relation \(\vdash \) by a class of matrices, one naturally has to assume that \(\vdash \) is structural. Much attention is devoted to the study of strongly finite logics, i.e., logics whose consequence relations may be determined by a finite set of finite matrices. In Sect. 4.3, a criterion, expressed in terms of Lindenbaum-type matrices, for \(\vdash \) to be strongly finite is given, and in Sect. 4.4 by the well-known method of ultraproducts it is proved that every strongly finite consequence relation is compact. The subject of strengthenings of logics is treated in Sects. 4.5 and 4.6, where the so-called (A, B)-strengthenings are examined in detail. Intuitively, given two arbitrary sets of formulas A and B, the (A, B)-strengthening of consequence relation \(\vdash \) is obtained by treating formulas in A as new axiom schemas, while those from B as counter-axiom schemas. It is shown (by two methods) that any (A, B)-strengthening of a strongly finite \(\vdash \) is strongly finite, and the number of such strengthenings is finite. The remaining part of our work (Sect. 5) is devoted to a purely model-theoretical proof of Shoesmith and Smiley’s finite basis theorem, which states that every strongly finite logic is finitely based, i.e., generated by a finite set of pairs (X, Y ) with X and Y  being finite sets of formulas. In the Appendix, we abandon multiple-conclusion consequence relations and turn briefly to single-conclusion ones (i.e., consequence operations in Tarski’s sense) and furnish other proofs of two important theorems: Czelakowski’s characterization theorem for the class Matr( \(Cn_K\) ) and Wojtylak’s representation theorem for consequence operations that are \(\geq \) than \(Cn_K\) .