You are here

Logic as Algebra

Paul Halmos and Steven Givant
Mathematical Association of America
Publication Date: 
Number of Pages: 
Dolciani Mathematical Expositions
[Reviewed by
Mark Johnson
, on

The intent of Logic as Algebra is expressed clearly in its preface: show that logic can (and perhaps should) be viewed from an algebraic perspective. When so viewed, many of its principal notions are seen to be old friends, familiar algebraic notions that were "disguised" in logical clothing. Moreover, the connection between the principal theorems of the subject and well-known theorems in algebra becomes clearer. Even the proofs often gain in simplicity.

To this end, authors Paul Halmos and Steven Givant have written a brief, engaging text aimed at both amateurs and professionals, which requires only a course in modern algebra as background.

Since one of this book's potential uses is as a course text, an outline of its contents may be helpful:

  • What is Logic?
    An introductory parable and mini-logic prepare the reader to meet propositional logic.
  • Propositional Calculus
    A fairly traditional development of propositional logic.
  • Boolean Algebra
    The basics of Boolean algebras, motivated by their similarities with the propositional calculus. Contains a good example of the power of the algebraic method: a proof of the consistency of propositional logic by showing that the set of propositions is a non-trivial Boolean algebra.
  • Boolean Universal Algebra
    A catalog of terminology and facts about Boolean subalgebras, homomorphisms, ideals, filters, etc. Culminates in the Stone Representation Theorem, which is used to prove that the propositional calculus induces a free Boolean algebra. (This chapter seems especially useful for undergraduates as a review of abstract algebra.)
  • Logic via Algebra
    The core of the book, proving completeness and soundness for Boolean logics.
  • Lattices and Infinite Operations
    A brief digression, without ties to logic. (This is a bit puzzling, since it would have been easy to mention infinite conjunctions and disjunctions alongside the infinite inf and sup.)
  • Monadic Predicate Calculus
    Presents the theory of a single quantifier in Boolean logics (i.e., each statement has at most one quantifier) and applies it to classical syllogisms.

The prose of Logic as Algebra is elegant and clear. Based on notes from a course Halmos has given several times, the text gives the reader the impression of dropping in on those lectures. The tone is conversational: theorems and proofs arise naturally, and are only occasionally set off from the main text. As a result, the book is a pleasure to read.

As a course text, Logic as Algebra would be appropriate for an undergraduate Introduction to Algebraic Logic, although instructors should be aware that there are no exercises. It certainly leads naturally into Halmos's Algebraic Logic, which develops the theory of multiple quantifiers via polyadic algebras.

However, I believe there are better textbook choices for an Introduction to Logic (as opposed to Algebraic Logic). One example is Ebbinghaus, Flum, and Thomas's Mathematical Logic. A partial list of its table of contents illustrates some of what is missing from Logic as Algebra: Syntax of First-Order Languages, Semantics of First-Order Languages, The Löwenheim-Skolem Theorem and the Compactness Theorem, Extensions of First-Order Logic, and Limitations of the Formal Method (including Gödel's Incompleteness Theorem). Halmos and Givant mention compactness but show none of its surprising power. And their approach does not lend itself to a clear distinction between syntax and semantics. This is unfortunately exacerbated by a few key typographical errors in and around the Deduction Theorem on page 91: the symbol for semantic consequence is used when (I am fairly certain) the syntactic symbol was intended.

I have one final concern that is more personal. As a logician, I have some problems with the tone the book adopts towards logic. Consider the difference between the title of the fifth chapter, "Logic via Algebra," and the title of the book, "Logic as Algebra." The first indicates a route to an independent subject, which is fine; the second grants a primacy to algebra which feels inappropriate.

This would be a minor quibble were it not for the correspondence set up between logic and thoughtlessness in the parable of the first chapter, "What is Logic?" It appears in a section entitled, "To count or to think." In the second paragraph we are told, "The content of logic appears to be sentences and deductions, and the methods of logic appear to be enumerative (counting) and combinatorial (arranging)." This leads into the problem of counting the number of matches in a single-elimination tournament with 1025 players. Three solutions are given: counting each round and adding up the total, counting and using a geometric series to total, and "pure thought" --- realizing that each player except the champion will lose exactly one match, so 1024 matches will be played. The punch line is, "Pure thought is always better than thoughtless counting." Who could disagree? But in this context, logic has been portrayed as the method of counting, and one is left to presume that the algebraic method about to be presented is closer to pure thought. This correspondence reappears throughout the book.

Perhaps this is harmless if the reader is a professional mathematician. But my guess is that an undergraduate whose first encounter with logic is through Logic as Algebra would have little desire to explore it further. This book certainly gives no incentive for her to do so. Even for a professional I would recommend balancing this approach with an alternative, such as Abraham Robinson's Introduction to Model Theory and to the Metamathematics of Algebra, just to reinforce the idea that the two disciplines of algebra and logic are mutually supportive.

One last note: the tennis parable discussed above has appeared in Halmos's work before. In "Mathematics as a Creative Art" (see his Selecta: Expository Writing), it is used to illustrate how abstract mathematics is more than just counting. In that setting, I couldn't agree more.

Mark Johnson is Assistant Professor of Mathematics and Computer Science at Central College. Besides logic, his interests include Bill Evans, Thelonious Monk, the Minnesota Twins, and burritos as big as your head.

What is Logic?: To count or to think; A small alphabet; A small grammar; A small logic; What is truth?; Motivation of the small language; All mathematics. Propositional Calculus: Propositional symbols; Propositional abbreviations; Polish notation; Language as an algebra; Concatenation; Theorem schemata; Formal proofs; Entailment; Logical equivalence; Conjunction; Algebraic identities. Boolean Algebra: Equivalence classes; Interpretations; Consistency and Boolean algebra; Duality and commutativity; Properties of Boolean algebras; Subtraction; Examples of Boolean algebras. Boolean Universal Algebra: Subalgebras; Homomorphisms; Examples of homomorphisms; Free algebras; Kernels and ideals; Maximal ideals; Homomorphism theorem; Consequences; The representation theorem. Logic via Algebra: Pre-Boolean algebras; Substitution rule; Boolean logics; Algebra of the propositional calculus; Algebra of proof and consequence. Lattices and Infinite Operations: Lattices; Non-distributive lattices; Infinite operations. Monadic Predicate Calculus: Propositional functions; Finite functions; Functional monadic algebras; Functional quantifiers; Properties of Quantifiers; Monadic algebras; Free monadic algebras; Modal logics; Monadic logics; Syllogisms.