Logical Matrix

Origin. Łukasiewicz and Tarski, "Investigations into the sentential calculus" (1930), where the matrix method is set out; Jerzy Łoś and Roman Suszko, "Remarks on sentential logics" (1958), which gave the general theory and the notion of a structural consequence relation. Wójcicki's Theory of Logical Calculi (1988) is the reference; Font and Jansana's abstract algebraic logic is where it now lives.

Models. The apparatus the Algebraic division is defined by, stated in general. A matrix is an algebra together with a subset of its elements marked as designated, and consequence is preservation of designation: Γ ⊨ φ when every valuation sending Γ into the designated set sends φ there too. Truth tables are the two-element case; three-valued logics, fuzzy logics, and the whole many-valued family are matrices with more elements and a different designated set.

Formalism.

The matrix: M = (A, D) where A is an algebra of the logic's similarity type and D ⊆ A. A valuation v : Fm → A is a homomorphism from the formula algebra.

Consequence: Γ ⊨_M φ iff for every valuation v: v[Γ] ⊆ D implies v(φ) ∈ D. The logic of M is that relation. The logic of a class of matrices is the intersection.

Structurality: ⊨_M is closed under substitution — because valuations are homomorphisms. Łoś–Suszko: the structural consequence relations are exactly those determined by a class of matrices. So "matrix semantics" and "structural consequence" are the same notion twice.

The designated set does the work: Same algebra, different D, different logic. Kleene's K3 and Priest's LP share the Strong Kleene tables and differ only in whether ½ is designated: K3 takes D = {1}, LP takes D = {1, ½}. One is paracomplete and the other paraconsistent, and the algebra is identical.

Reduced matrices and the Leibniz operator: Two elements are Leibniz-congruent if no formula distinguishes them relative to D. Quotienting gives the reduced matrix; the reduced models of a logic are its algebraic counterpart. Blok and Pigozzi's algebraizability is a condition on how well the Leibniz operator behaves.

Limits: Not every logic has a finite characteristic matrix — Gödel (1932) proved IPC has none, which is why the intermediate logics needed algebraic semantics rather than tables. Every structural logic has some matrix (the Lindenbaum matrix), so the existence claim is trivial and the finiteness claim is where the content is.

Symbols.

Metatheory. The Łoś–Suszko theorem is the reason this notion is the field's and not a technique: structural consequence relations and matrix-definable ones coincide, so any logic closed under substitution has a matrix semantics, trivially — and the interesting questions are all about which matrices, how many, and how finite. K3 and LP sharing an algebra and differing only in D is the cleanest demonstration that the designated set carries the logic: paracompleteness and paraconsistency are one table read with two thresholds. Gödel's 1932 proof that IPC has no finite characteristic matrix is the negative result that pushed the Heyting family toward algebraic rather than tabular semantics, and the Leibniz operator is what abstract algebraic logic replaced the matrix with once it needed to classify logics rather than present them.

Applies to. Every entry in Algebraic, whose criteria is stated in matrix terms. Abstract algebraic logic and the Leibniz hierarchy. Many-valued logic, where the matrix is the definition. Decidability by finite matrices. Independence proofs, which are Łukasiewicz's original use: exhibit a matrix validating the axioms and refuting the candidate.

Limitations. Existence is trivial and finiteness is not, so the notion classifies nothing by itself — the Lindenbaum matrix always exists and says nothing. Matrices require truth-functionality: a logic whose connectives are not functions of their arguments' values has no matrix, which is why supervaluationism and da Costa's C-systems fall outside despite being many-valued in spirit. And the Leibniz operator's good behaviour is a strong condition; most of the interesting logics sit in the middle of the hierarchy, where the matrix presentation is available and uninformative.

© 2026 Lingenic LLC