Algebraic logic

In mathematical logic, algebraic logic is the reasoning obtained by manipulating equations with free variables.

What is now usually called classical algebraic logic focuses on the identification and algebraic description of models appropriate for the study of various logics (in the form of classes of algebras that constitute the algebraic semantics for these deductive systems) and connected problems like representation and duality. Well known results like the representation theorem for Boolean algebras and Stone duality fall under the umbrella of classical algebraic logic (Czelakowski 2003).

Works in the more recent abstract algebraic logic (AAL) focus on the process of algebraization itself, like classifying various forms of algebraizability using the Leibniz operator (Czelakowski 2003).

Calculus of relations

A homogeneous binary relation is found in the power set of X × X for some set X, while a heterogeneous relation is found in the power set of X × Y, where X ≠ Y. Whether a given relation holds for two individuals is one bit of information, so relations are studied with Boolean arithmetic. Elements of the power set are partially ordered by inclusion, and lattice of these sets becomes an algebra through relative multiplication or composition of relations.

"The basic operations are set-theoretic union, intersection and complementation, the relative multiplication, and conversion."

The conversion refers to the converse relation that always exists, contrary to function theory. A given relation may be represented by a logical matrix; then the converse relation is represented by the transpose matrix. A relation obtained as the composition of two others is then represented by the logical matrix obtained by matrix multiplication using Boolean arithmetic.

For instance, a function is a relation R with range B such that R^T R = I, the identity relation on B.

In the practice of the calculus of relations, Jacques Riguet used the algebraic logic to advance useful concepts: he extended the concept of an equivalence relation (on a set) to heterogeneous relations with the difunctional concept. Riguet also extended ordering to the heterogeneous context by his note that a staircase logical matrix has a complement that is also a staircase, and that the theorem of N. M. Ferrers follows from interpretation of the transpose of a staircase. Riguet generated rectangular relations by taking the outer product of logical vectors; these contribute to the non-enlargeable rectangles of formal concept analysis.

The relation algebra structure, based in set theory, was transcended by Tarski with axioms describing it. Then he asked if every algebra satisfying the axioms could be represented by a set relation. The negative answer opened the frontier of abstract algebraic logic.

Algebras as models of logics

Algebraic logic treats algebraic structures, often bounded lattices, as models (interpretations) of certain logics, making logic a branch of the order theory.

In algebraic logic:

• Variables are tacitly universally quantified over some universe of discourse. There are no existentially quantified variables or open formulas;
• Terms are built up from variables using primitive and defined operations. There are no connectives;
• Formulas, built from terms in the usual way, can be equated if they are logically equivalent. To express a tautology, equate a formula with a truth value;
• The rules of proof are the substitution of equals for equals, and uniform replacement. Modus ponens remains valid, but is seldom employed.

In the table below, the left column contains one or more logical or mathematical systems, and the algebraic structure which are its models are shown on the right in the same row. Some of these structures are either Boolean algebras or proper extensions thereof. Modal and other nonclassical logics are typically modeled by what are called "Boolean algebras with operators."

Algebraic formalisms going beyond first-order logic in at least some respects include:

• Combinatory logic, having the expressive power of set theory;
• Relation algebra, arguably the paradigmatic algebraic logic, can express Peano arithmetic and most axiomatic set theories, including the canonical ZFC.

Logical system	Lindenbaum–Tarski algebra
Classical sentential logic	Boolean algebra
Intuitionistic propositional logic	Heyting algebra
Łukasiewicz logic	MV-algebra
Modal logic K	Modal algebra
Lewis's S4	Interior algebra
Lewis's S5, monadic predicate logic	Monadic Boolean algebra
First-order logic	Complete Boolean algebra, polyadic algebra, predicate functor logic
First-order logic with equality	Cylindric algebra
Set theory	Combinatory logic, relation algebra

History

Algebraic logic is, perhaps, the oldest approach to formal logic, arguably beginning with a number of memoranda Leibniz wrote in the 1680s, some of which were published in the 19th century and translated into English by Clarence Lewis in 1918. But nearly all of Leibniz's known work on algebraic logic was published only in 1903 after Louis Couturat discovered it in Leibniz's Nachlass. Parkinson (1966) and Loemker (1969) translated selections from Couturat's volume into English.

Modern mathematical logic began in 1847, with two pamphlets whose respective authors were George Boole and Augustus De Morgan. In 1870 Charles Sanders Peirce published the first of several works on the logic of relatives, and in 1883, Christine Ladd, a student of Peirce at Johns Hopkins University, published "On the Algebra of Logic". Logic turned more algebraic when binary relations were combined with composition of relations. For sets A and B, relations were first understood as elements of the power set of A×B with properties described by Boolean algebra. The "calculus of relations" is arguably the culmination of Leibniz's approach to logic. At the Hochschule Karlsruhe the calculus of relations was described by Ernst Schröder. In particular he formulated Schröder rules, though De Morgan had anticipated them with his Theorem K.

The "Boole-Schröder algebra of logic" was developed at University of California, Berkeley in a textbook by Clarence Lewis in 1918. He treated the logic of relations as derived from the propositional functions of two or more variables.

Hugh MacColl, Frege, Peano, Bertrand Russell, and A. N. Whitehead all shared Leibniz's dream of combining symbolic logic, mathematics, and philosophy.

Some writings by Leopold Loewenheim and Thoralf Skolem on algebraic logic appeared after the 1910–13 publication of Principia Mathematica, and Tarski revived interest in relations with his 1941 essay "On the Calculus of Relations".

According to Helena Rasiowa, "The years 1920-40 saw, in particular in the Polish school of logic, researches on non-classical propositional calculi conducted by what is termed the logical matrix method. Since logical matrices are certain abstract algebras, this led to the use of an algebraic method in logic."

Brady (2000) discusses the rich historical connections between algebraic logic and model theory. The founders of model theory, Ernst Schröder and Leopold Loewenheim, were logicians in the algebraic tradition. Alfred Tarski, the founder of set theoretic model theory as a major branch of contemporary mathematical logic, also:

• Initiated abstract algebraic logic with relation algebras
• Invented cylindric algebra
• Co-discovered Lindenbaum–Tarski algebra.

Leibniz had no influence on the rise of algebraic logic because his logical writings were little studied before the Parkinson and Loemker translations. Our present understanding of Leibniz as a logician stems mainly from the work of Wolfgang Lenzen, summarized in Lenzen (2004). To see how present-day work in logic and metaphysics can draw inspiration from, and shed light on, Leibniz's thought, see Zalta (2000).

See also

• Boolean algebra (logic)
• Codd's theorem
• Universal algebra

References

• Brady, Geraldine (2000). From Peirce to Skolem: A Neglected Chapter in the History of Logic. Amsterdam, Netherlands: North-Holland/Elsevier Science BV.
• Czelakowski, Janusz (2003). "Review: Algebraic Methods in Philosophical Logic by J. Michael Dunn and Gary M. Hardegree". The Bulletin of Symbolic Logic. Association for Symbolic Logic, Cambridge University Press. 9. ISSN 1079-8986. JSTOR 3094793.
• Lenzen, Wolfgang, 2004, "Leibniz’s Logic" in Gabbay, D., and Woods, J., eds., Handbook of the History of Logic, Vol. 3: The Rise of Modern Logic from Leibniz to Frege. North-Holland: 1-84.
• Loemker, Leroy (1969) [First edition 1956], Leibniz: Philosophical Papers and Letters (2nd ed.), Reidel.
• Parkinson, G.H.R (1966). Leibniz: Logical Papers. Oxford University Press.
• Zalta, E. N., 2000, "A (Leibnizian) Theory of Concepts," Philosophiegeschichte und logische Analyse / Logical Analysis and History of Philosophy 3: 137-183.

Further reading

• J. Michael Dunn; Gary M. Hardegree (2001). Algebraic Methods in Philosophical Logic. Oxford University Press. ISBN 978-0-19-853192-0. Good introduction for readers with prior exposure to non-classical logics but without much background in order theory and/or universal algebra; the book covers these prerequisites at length. This book however has been criticized for poor and sometimes incorrect presentation of AAL results. Review by Janusz Czelakowski
• Hajnal Andréka, István Németi and Ildikó Sain (2001). "Algebraic logic". In Dov M. Gabbay, Franz Guenthner. Handbook of Philosophical Logic, vol 2 (2nd ed.). Springer. ISBN 978-0-7923-7126-7. Draft.
• Ramon Jansana (2011), "Propositional Consequence Relations and Algebraic Logic". Stanford Encyclopedia of Philosophy. Mainly about abstract algebraic logic.
• Stanley Burris (2015), "The Algebra of Logic Tradition". Stanford Encyclopedia of Philosophy.
• Willard Quine, 1976, "Algebraic Logic and Predicate Functors" in The Ways of Paradox. Harvard Univ. Press: 283-307.

Historical perspective

• Ivor Grattan-Guinness, 2000. The Search for Mathematical Roots. Princeton University Press.

External links

• Media related to Algebraic logic at Wikimedia Commons