## 1. Introduction



Boole's *The Mathematical Analysis of Logic* presents many
interesting logic novelties: It was the beginning of
nineteenth-century mathematization of logic and provided an
*algorithmic* alternative (via a slight modification of
ordinary algebra) to the *catalog* approach used in traditional
logic (even if reduction procedures were developed in the latter).
Instead of a list of valid forms of argument, the validity of
arguments were determined on the basis of general principles and
rules. Furthermore, it provided an effective method for proving
logical laws on the basis of a system of postulates. As Boole wrote
later, it was a proper "science of reasoning", and not a
"mnemonic art" like traditional Syllogistics (Boole 1997:
136). Three-quarters of the way through this book, after finishing
his discussion of syllogistic logic, Boole started to develop the
general tools that would be used in his *Laws of Thought*
(1854) to greatly extend traditional logic by permitting an argument
to have many premises and to involve many classes. To handle the
infinitely many possible logical arguments of this expanded logic, he
presented theorems that provided key tools for an algorithmic analysis
(a catalog was no longer feasible).



Boole's ideas were conceived independently of earlier anticipations,
like those developed by G.W. Leibniz. They emerged from the particular
contexts of English mathematics (see Peckhaus 2009). According to
Victor Sanchez Valencia, the tradition that originated
with Boole came to be known as the *algebra of logic* since the
publication in 1879 of *Principles of the Algebra of Logic* by
Alexander MacFarlane (see Sanchez Valencia 2004: 389).
MacFarlane considered "the analytical method of reasoning about
Quality proposed by Boole" as an algebra (see MacFarlane 1879:
3).



This approach differs from what is usually called *algebraic
logic*; though there is some overlap, the historical development
of the two areas are different. Algebraic logic is understood as:



> 
> 
> *a style* [of logic] *in which concepts and relations
> are* expressed by mathematical symbols [\(\ldots\)] so that
> mathematical techniques can be applied. Here mathematics shall mean
> mostly algebra, i.e., the part of mathematics concerned with finitary
> operations on some set. (Hailperin 2004: 323)
> 
> 
> 



Algebraic logic can be already found in the work of Leibniz, Jacob
Bernoulli and other modern thinkers, and it undoubtedly constitutes an
important antecedent of Boole's approach. In a broader perspective,
both are part of the tradition of *symbolic knowledge* in the
formal sciences, as first conceived by Leibniz (see Esquisabel 2012).
This idea of algebraic logic was continued to some extent in the
French Enlightenment in the work of Condillac and Condorcet (see
Grattan-Guinness 2000: 14 ff.)



Boole's methodology for dealing with logical problems can be described
as follows:


1. Translate the logical data into suitable equations;
2. Apply algebraic techniques to solve these equations;
3. Translate this solution, if possible, back into the original
language.



In other words, symbolic formulation of logical problems and solution
of logical equations constitutes Boole's method (see Sanchez
Valencia 2004: 389).



Later, in his *Pure Logic* from 1864, Jevons changed Boole's
partial operation of union of disjoint sets to the modern unrestricted
union and eliminated Boole's questionable use of uninterpretable terms
(see Jevons 1890). Peirce (1880) eliminated explicitly the
Aristotelian derivation of particular statements from universal
statements by giving the modern meaning for "All \(A\) is
\(B\)". In addition, he extended the algebra of logic for
classes to the algebra of logic for binary relations and introduced
general sums and products to handle quantification. Ernst
Schroder, taking inspiration from previous work by Hermann
(1809-1877) and Robert Grassmann (1815-1901) and using the
framework developed by Peirce, developed and systematized the
19th Century achievements in the algebra of logic in his
three-volume work *Vorlesungen uber die Algebra der Logik*
(1890-1910).



The contributions of Gottlob Frege (1848-1925) to logic from the
period 1879-1903, based on an *axiomatic* approach to
logic, had very little influence at the time (and the same can be said
of the *diagrammatic* systems of C.S. Peirce developed at the
turn of the century). Whitehead and Russell rejected the algebra of
logic approach, with its predominantly equational formulations and
algebraic symbolism, in favor of an approach strongly inspired by the
axiomatic system of Frege, and using the notation developed by
Giuseppe Peano, namely to use logical connectives, relation symbols
and quantifiers.



During the first two decades of the twentieth century, the algebra of
logic was further developed in the works of Platon Sergeevich
Poretzsky (1846-1907), Louis Couturat (1868-1914), Leopold
Lowenheim (1878-1957), and Heinrich Behmann
(1891-1970) (see Styazhkin 1969). In particular, elimination
theorems in the algebra of logic influenced decision procedures for
fragments of first-order and second-order logic (see Mancosu, Zach,
Badesa 2009).



After WWI David Hilbert (1862-1943), who had at first adopted
the algebraic approach, picked up on the approach of
*Principia*, and the algebra of logic fell out of favor.
However, in 1941, Tarski treated relation algebras as an equationally
defined class. Such a class has many models besides the *collection
of all binary relations on a given universe* that was considered
in the 1800s, just as there are many Boolean algebras besides the
*power set Boolean algebras* studied in the 1800s. In the years
1948-1952 Tarski, along with his students Chin and Thompson,
created cylindric algebras as an algebraic logic companion to
first-order logic, and in 1956 Paul Halmos (1916-2006)
introduced polyadic algebras for the same purpose. As Halmos (1956 b,
c and d) noted, these new algebraic logics tended to focus on studying
the extent to which they captured first-order logic and on their
universal algebraic aspects such as axiomatizations and structure
theorems, but offered little insight into the nature of the
first-order logic which inspired their creation.


## 2. 1847--The Beginnings of the Modern Versions of the Algebra of Logic



In late 1847, Boole and Augustus De Morgan (1806-1871) each
published a book on logic--Boole's *Mathematical Analysis of
Logic* (1847) and De Morgan's *Formal Logic* (1847). De
Morgan's approach was to dissect every aspect of traditional deductive
logic (usually called 'Aristotelian logic') into its
minutest components, to consider ways to generalize these components,
and then, in some cases, undertake to build a logical system using
these components. Unfortunately, he was never able to incorporate his
best ideas into a significant system. His omission of a symbol for
equality made it impossible to develop an equational algebra of logic.
It seems that synthesis was not De Morgan's strong suit.



De Morgan's book of 1847 was part of a revival in logic studies that
originated at the beginning of 19th Century with Joseph Diez Gergonne
(1771-1859) in France, and Bernhard Bolzano (1781-1848) in
Bohemia, among others. George Bentham and William Hamilton in the
United Kingdom were also part of this revival and their studies
focused on the nature of variations of the categorical sentences in
traditional syllogistic, including what was called
"quantification of the predicate"; for example, "All
\(A\) are some \(B\)" or "Some \(A\) are all
\(B\)". It was thought that this problem required an extension
of the syllogistic logic of Aristotle and that some form of symbolic
method was needed both to handle such statements and provide a
classification of their different types (see Heinemann 2015 chapters 2
and 3). 



Boole approached logic from a completely different perspective, namely
how to cast Aristotelian logic in the garb of symbolical algebra.
Using symbolical algebra was a theme with which he was well-acquainted
from his work in differential equations, and from the various papers
of his young friend and mentor Duncan Farquharson Gregory
(1813-1844), who made attempts to cast other subjects such as
geometry into the language of symbolical algebra. Since the
application of symbolical algebra to differential equations had
proceeded through the introduction of differential operators, it must
have been natural for Boole to look for operators that applied in the
area of Aristotelian logic. He readily came up with the idea of using
"selection" operators, for example, a selection operator
for the color red would select the red members from a class. In his
1854 book, Boole realized that it was simpler to omit selection
operators and work directly with classes. (However he kept the
selection operators to justify his claim that his laws of logic were
not ultimately based on observations concerning the use of language,
but were actually deeply rooted in the processes of the human mind.)
From now on in this article, when discussing Boole's 1847 book, the
selection operators have been replaced with the simpler direct
formulation using classes.



Since symbolical algebra was just the syntactic side of ordinary
algebra, Boole needed ways to interpret the usual operations and
constants of algebra to create his algebra of logic for classes.
Multiplication was interpreted as intersection, leading to his one new
law, the idempotent law \(XX = X\) for multiplication, rediscovering a
logical law already formulated by Leibniz. Addition was defined as
union, provided one was dealing with *disjoint* classes; and
subtraction as class difference, provided one was subtracting a
subclass from a class. In other cases, the addition and subtraction
operations were simply undefined, or as Boole wrote,
*uninterpretable*. The usual laws of arithmetic told Boole that
1 must be the universe and \(1 - X\) must be the complement of
\(X\).



The next step in Boole's system was to translate the four kinds of
categorical propositions into equations, for example "All \(X\)
is \(Y\)" becomes \(X = XY\), and "Some \(X\) is
\(Y\)" becomes \(V = XY\), where \(V\) is a new symbol. To
eliminate the middle term in a syllogism Boole borrowed an elimination
theorem from ordinary algebra, but it was too weak for his algebra of
logic. This would be remedied in his 1854 book. Boole found that he
could not always derive the desired conclusions with the above
translation of particular propositions (i.e., those with existential
import), so he added the variants \(X = VY\), \(Y = VX\), and \(VX =
VY\) (see the entry on
 Boole).



The symbolic algebra of the 1800s included much more than just the
algebra of polynomials, and Boole experimented to see which results
and tools might apply to the algebra of logic. For example, he proved
one of his results by using an infinite series expansion. His
fascination with the possibilities of ordinary algebra led him to
consider questions such as: What would logic be like if the idempotent
law were replaced by the law \(X^3 = X\)? His successors, especially
Jevons, would soon narrow the operations on classes to the ones that
we use today, namely union, intersection and complement.



As mentioned earlier, three-quarters of the way through his brief book
of 1847, after finishing derivations of the traditional Aristotelian
syllogisms in his system, Boole announced that his algebra of logic
was capable of far more general applications. Then he proceeded to add
general theorems on developing (expanding) terms, providing
interpretations of equations, and using long division to express one
class in an equation in terms of the other classes (with side
conditions added).



Boole's theorems, completed and perfected in 1854, gave algorithms for
analyzing infinitely many argument forms. This opened a new and
fruitful perspective, deviating from the traditional approach to
logic, where for centuries scholars had struggled to come up with
clever mnemonics to memorize a very small catalog of valid conversions
and syllogisms and their various interrelations.



De Morgan's *Formal Logic* did not gain significant
recognition, primarily because it was a large collection of small
facts without a significant synthesis. Boole's *The Mathematical
Analysis of Logic* had powerful methods that caught the attention
of a few scholars such as De Morgan and Arthur Cayley
(1821-1895); but immediately there were serious questions about
the workings of Boole's algebra of logic: Just how closely was it tied
to ordinary algebra? How could Boole justify the procedures of his
algebra of logic? In retrospect it seems quite certain that Boole did
not know why his system worked. His claim, following Gregory, that in
order to justify using ordinary algebra it was enough to check the
commutative law \(XY = YX\) for multiplication and the distributive
law \(X(Y + Z) = XY + XZ\), is clearly false. Nonetheless it is also
likely that he had checked his results in a sufficient number of cases
to give substance to his belief that his system was correct.


## 3. 1854--Boole's Final Presentation of his Algebra of Logic



In his second book, *The Laws of Thought*, Boole not only
applied algebraic methods to traditional logic but also attempted some
reforms to logic. He started by augmenting the laws of his 1847
algebra of logic (without explicitly saying that his previous list of
three axioms was inadequate), and made some comments on the rule of
inference (performing the same operation on both sides of an
equation). But then he casually stated that the foundation of his
system actually rested on a single (new) principle, namely it sufficed
to check an argument by seeing if it was correct when the class
symbols took on only the values 0 and 1, and the operations were the
usual arithmetical operations. Let us call this *Boole's Rule of 0
and 1*. No meaningful justification was given for Boole's adoption
of this new foundation, it was not given a special name, and the scant
references to it in the rest of the book were usually rather clumsily
stated. For a modern analysis of this Rule of 0 and 1 see Burris &
Sankappanavar 2013.



The development of the algebra of logic in the *Laws of
Thought* proceeded much as in his 1847 book, with minor changes to
his translation scheme, and with the selection operators replaced by
classes. There is a new and very important theorem (correcting the one
he had used in 1847), the Elimination Theorem, which says the
following: given an equation \(F(x,y, z, \ldots) = 0\) in the class
symbols \(x, y, z\), etc., the most general conclusion that follows
from eliminating certain of the class symbols is obtained by (1)
substituting 0s and 1s into \(F(x, y, z, \ldots)\) for the symbols to
be eliminated, in all possible ways, then (2) multiplying these
various substitution instances together and setting the product equal
to 0. Thus eliminating \(y\) and \(z\) from \(F(x, y, z) = 0\) gives
\(F(x, 0, 0)F(x, 0, 1)F(x, 1, 0)F(x, 1, 1) = 0\). This theorem also
played an important role in Boole's interpretation of Aristotle's
syllogistic.



From an algebra of logic point of view, the 1854 treatment at times
seems less elegant than that in the 1847 book, but it gives a much
richer insight into how Boole thinks about the foundations for his
algebra of logic. The final chapter on logic, Chapter XV, was an
attempt to give a uniform proof of the Aristotelian conversions and
syllogisms. (It is curious that prior to Chapter XV Boole did not
present any examples of arguments involving particular propositions.)
The details of Chapter XV are quite involved, mainly because of the
increase in size of expressions when the Elimination and Development
Theorems are applied. Boole simply left most of the work to the
reader. Later commentators would gloss over this chapter, and no one
seems to have worked through its details.



Aside from the Rule of 0 and 1 and the Elimination Theorem, the 1854
presentation is mainly interesting for Boole's attempts to justify his
algebra of logic. He argued that in symbolical algebra it was quite
acceptable to carry out equational deductions with partial operations,
just as one would when the operations were total, as long as the terms
in the premises and the conclusion were interpretable. He said this
was the way ordinary algebra worked with the uninterpretable
\(\sqrt{-1}\), the square root of [?]1. (The geometric
interpretation of complex numbers was recognized early on by Wessel,
Argand, and Gauss, but it was only with the publications of Gauss and
Hamilton in the 1830s that doubts about the acceptability of complex
numbers in the larger mathematical community were overcome. It is
curious that in 1854 Boole regarded \(\sqrt{-1}\) as
uninterpretable.)



There were a number of concerns regarding Boole's approach to the
algebra of logic:


1. Was there a meaningful tie between his algebra of logic and the
algebra of numbers, or was it just an accident that they were so
similar?
2. Could one handle particular propositions in an algebraic logic
that focused on equations?
3. Was it really acceptable to work with uninterpretable terms in
equational derivations?
4. Was Boole using "Aristotelian" semantics (the
semantics presupposed in traditional logic, where the extension of a
term is nonempty)?


## 4. Jevons: An Algebra of Logic Based on Total Operations



Jevons, who had studied with De Morgan, was the first to offer an
alternative to Boole's system. In 1863 he wrote to Boole that surely
Boole's operation of addition should be replaced by the more natural
'inclusive or' (or 'union'), leading to the
law \(X + X = X\). Boole completely rejected this suggestion (it would
have destroyed his system based on ordinary algebra) and broke off the
correspondence. Jevons published his system in his 1864 book, *Pure
Logic* (reprinted in Jevons 1890). By 'pure' he meant
that he was casting off any dependence on the algebra of
numbers--instead of classes, which are associated with quantity,
he would use predicates, which are associated with quality, and his
laws would be derived directly from the (total) fundamental operations
of inclusive disjunction and conjunction. But he kept Boole's use of
equations as the fundamental form of statements in his algebra of
logic.



By adopting De Morgan's convention of using upper-case/lower-case
letters for complements, Jevons' system was not suited to provide
equational axioms for modern Boolean algebra. However, he refined his
system of axioms and rules of inference until the result was
essentially the modern system of Boolean algebra for *ground
terms*, that is, terms where the class symbols are to be thought
of as constants, not as variables.



It must be noticed that modern equational logic deals with
*universally quantified* equations (which would have been
called *laws* in the 1800s). In the 19th century
algebra of logic one could translate "All \(X\) is \(Y\)"
as the equation \(X = XY\). This is *not* to be viewed as the
universally quantified expression \((\forall X)(\forall Y)(X = XY)\).
\(X\) and \(Y\) are to be treated as constants (or schematic letters).
Terms that only have constants (no variables) are called
*ground* terms.



By carrying out this analysis in the special setting of an algebra of
predicates (or equivalently, in an algebra of classes) Jevons played
an important role in the development of modern equational logic. As
mentioned earlier, Boole gave inadequate sets of equational axioms for
his system, originally starting with the two laws due to Gregory plus
his idempotent law; these were accompanied by De Morgan's inference
rule that one could carry out the same operation (Boole's fundamental
operations in his algebra of logic were addition, subtraction and
multiplication) on equals and obtain equals. Boole then switched to
the simple and powerful (but unexplained) Rule of 0 and 1.



Having replaced Boole's fundamental operations with total operations,
Jevons proceeded, over a period of many years, to work on the axioms
and rules for his system. Some elements of equational logic that we
now take for granted required a considerable number of years for
Jevons to resolve:



*The Reflexive Law* (\(A=A\)). In 1864 Jevons listed this as a
postulate (1890, p. 11) and then in SS24 he referred to \(A = A\)
as a "useless Identical proposition". In his 1869 paper on
substitution it became the "Law of Identity". In the
*Principles of Science* (1874) it was one of the three
"Fundamental Laws of Thought".



*The Symmetric Law* (\(B = A\) follows from \(A = B\)). In 1864
Jevons wrote "\(A = B\) and \(B = A\) are the same
statement". This is a position he would maintain. In 1874 he
wrote



> 
> 
> I shall consider the two forms \(A = B\) and \(B = A\) to express
> exactly the same identity written differently.
> 
> 
> 



For a final form of his algebra of logic we turn to the laws which he
had scattered over 40 pages in *Principles of Science* (1874),
having replaced his earlier use of + by \(\ORjev\), evidently to move
further away from any appearance of a connection with the algebra of
numbers:



Laws of Combination

 

\[ \begin{align} A &= AA = AAA = \& c & \mbox{Law of
Simplicity (p. 33)}\\ AB &= BA & \mbox{A Law of
Commutativeness (p. 35)}\\ A \ORjev A & = A &\mbox{Law of
Unity (p. 72)}\\ A \ORjev B &= B \ORjev A &\mbox{A Law of
Commutativeness (p. 72)}\\ A(B \ORjev C) &= AB \ORjev AC &
\mbox{(no name given) (p. 76)}\\ \end{align} \]


Laws of Thought

 

\[ \begin{align} A &= A & \mbox{Law of Identity (p. 74)}\\ Aa
&= o & \mbox{Law of Contradiction (p. 74)}\\ A &= AB
\ORjev Ab & \mbox{Law of Duality (p. 74)}\\ \end{align} \]


For his single rule of inference Jevons chose his principle of
substitution--in modern terms this was essentially a combination
of ground replacement and transitivity. He showed how to derive
transitivity of equality from this; he could have derived symmetry as
well but did not. The associative law was missing--it was
implicit in the lack of parentheses in his expressions.



It was only in his *Studies in Deductive Logic* (1880) that
Jevons mentioned McColl's use of an accent to indicate negation. After
noting that McColl's accent allowed one to take the negation of
complex bracketed terms he went on to say that, for the most part, he
found the notation of De Morgan, the notation that he had always used,
to be the more elegant.


## 5. Peirce: Basing the Algebra of Logic on Subsumption



Peirce started his research into the algebra of logic in the late
1860s. In his paper "On an Improvement in Boole's calculus of
Logic" (Peirce 1867), he arrived independently at the same
conclusion that Jevons had reached earlier, that one needed to replace
Boole's partial operation of addition with the total operation of
union (see CP 3.3.6). In his important 1880 paper, "On the
Algebra of Logic", Peirce quietly broke with the traditional
extensional semantics and introduced a usual assumption of modern
semantics: the extension of a concept, understood as a class, could be
empty (as well as the universe), and stated the truth values of the
categorical propositions that we use today. For example, he said the
proposition "All \(A\) is \(B\)" is true if \(A\) and
\(B\) are both the empty class. Conversion by Limitation, that is, the
argument "All \(A\) is \(B\)" therefore "Some \(B\)
is \(A\)", was no longer a valid inference. Peirce said nothing
about the reasons for and merits of his departure from the traditional
semantic assumption of existence.



Peirce also broke with Boole's and Jevons' use of equality as the
fundamental primitive, using instead the relation of
"subsumption" interpretable in different ways (subclass
relation, implication, etc.). He stated the partial order properties
of subsumption and then proceeded to define the operations of + and
x as least upper bounds and greatest lower bounds--he
implicitly assumed such bounds existed--and listed the key
equational properties of the algebras with two binary operations that
we now call lattices. Then he claimed that the distributive law
followed, but said the proof was too tedious to include. The
fruitfulness of this perspective is evident in his seminal paper from
1885. There Peirce introduced a system for propositional logic based
on five axioms for implication (represented by the sign
'\(-\kern-.4em<\)'), including what is now called
Peirce's law. It certainly made the algebra of logic more elegant.


## 6. De Morgan and Peirce: Relations and Quantifiers in the Algebra of Logic



De Morgan wrote a series of six papers called "On the
Syllogism" in the years 1846 to 1863 (reprinted in De Morgan
1966). In his efforts to generalize the syllogism, De Morgan replaced
the copula "is" with a general binary relation in the
second paper of the series dating from 1850. By allowing different
binary relations in the two premises of a syllogism, he was led to
introduce the composition of the two binary relations to express the
conclusion of the syllogism. In this pursuit of generalized syllogisms
he introduced various other operations on binary relations, including
the converse operation, and he developed a fragment of a calculus for
these operations. His main paper on this subject was the fourth in the
series, called "On the syllogism, No. IV, and on the logic of
relations" published in 1859 (see De Morgan 1966).



Following De Morgan's paper, Peirce, in his paper "Description
of a Notation for the Logic of Relatives, resulting from an
Amplification of the Conceptions of Boole's Calculus of Logic"
from 1870, lifted Boole's work to the setting of binary
relations--with binary relations one had, in addition to union,
intersection and complement, the natural operations of composition and
converse. A binary relation was characterized as a set of ordered
pairs (see 3.328). He worked on this new calculus between 1870 and
1883. Like De Morgan, Peirce also considered a number of other natural
operations on relations. Peirce's main paper on the subject was
"On the Algebra of Logic" (1880). By employing
unrestricted unions, denoted by S, and unrestricted
intersections, denoted by P, Peirce thus introduced quantifiers
into his algebra of logic.



In a paper from 1882, "Brief Description of the Algebra of
Relatives", reprinted in De Morgan 1966, he used these
quantifiers to define operations on relations by means of operations
on certain kind of coefficients. De Morgan gets credit for introducing
the concept of relation, but Peirce is considered the true creator of
the theory of relations (see, e.g., Tarski 1941: 73). However, Peirce
did not develop this theory. As Calixto Badesa wrote, "the
calculus of relatives was never to Peirce's liking" (Badesa
2004: 32). He considered it too complicated because of the combination
of class operations with relational ones. Instead, he preferred from
1885 onwards to develop a "general algebra" including
quantifiers but no operation on relations. In this way, he arrived at
an elementary and informal presentation of what is now called
first-order logic (see Badesa 2004, *loc. cit*.).


## 7. Schroder's systematization of the algebra of logic



The German mathematician Ernst Schroder played a key role in the
tradition of the algebra of logic. A good example was his challenge to
Peirce to provide a proof of the distributive law, as one of the key
equational properties of the algebras with two binary operations.
Peirce (1885) admitted that he could not provide a proof. Years later
Huntington (1904: 300-301) described part of the content of a
letter he had received from Peirce in December 1903 that claimed to
provide the missing proof--evidently Peirce had stumbled across
the long lost pages after the death of Schroder in 1902. Peirce
explained to Huntington that he had originally assumed Schroder's
challenge was well-founded and that this apparent shortcoming of his
paper "was to be added to the list of blunders, due to the
grippe, with which that paper abounds, ...". Actually
Peirce's proof did not correct the error since the distributive law
does not hold in lattices in general; instead his proof brought in the
operation of complementation--he used the axiom



> 
> 
> if \(a\) is not contained in the complement of \(b\) then \(a\) and
> \(b\) have a common lower bound.
> 
> 
> 



On the basis of his previous algebraic work, Schroder wrote an
encyclopedic three volume work at the end of the 19th
century called *Vorlesungen uber die Algebra der Logik*
(1890-1905), built on the subsumption framework with the modern
semantics of classes as presented by Peirce. This work was the result
of his research in algebra and revealed different influences.
Schroder aimed at a general algebraic theory with applications in
many mathematical fields, where the algebra of logic was at the core.
As Geraldine Brady pointed out, it offers the first exposition of
abstract lattice theory, the first exposition of Dedekind's theory of
chains after Dedekind, the most comprehensive development of the
calculus of relations, and a treatment of the foundations of
mathematics on the basis of the relation calculus (see Brady 2000: 143
f.)



The first volume concerned the equational logic of classes, the main
result being Boole's Elimination Theorem of 1854. Three rather
complicated counter-examples to Peirce's claim of distributivity
appeared in an appendix to Vol. I, one of which involved nine-hundred
and ninety identities for quasigroups. On the basis of this volume,
Dedekind (1897) composed an elegant modern abstract presentation of
lattices (which he called *Dualgruppen*); in this paper he
presented a five-element counter-example to Peirce's claim of the
distributive law.



Volume II augments the algebra of logic for classes developed in
Volume I so that it can handle existential statements. First, using
modern semantics, Schroder proved that one cannot use equations
to express "Some \(X\) is \(Y\)". However, he noted that
one can easily express it with a negated equation, namely \(XY \ne
0\). Volume II, a study of the calculus of classes using both
equations and negated equations, attempted to cover the same topics
covered in Vol. I, in particular there was considerable effort devoted
to finding an Elimination Theorem. After dealing with several special
cases, Schroder recommended this topic as an important research
area--the quest for an Elimination Theorem would be known as the
Elimination Problem.



Inspired mainly by Peirce's work, Schroder examined the algebra
of logic for binary relations in Vol. III of his *Vorlesungen
uber die Algebra der Logik*. As Tarski once noted, Peirce's
work was continued and extended in a very thorough and systematic way
by Schroder. One item of particular fascination for him was this:
given an equation \(E(x, y, z, \ldots) = 0\) in this algebra, find the
general solution for one of the relation symbols, say for \(x\), in
terms of the other relation symbols. He managed, given a particular
solution \(x = x0\), to find a remarkable term \(S(t, y, z, \ldots)\)
with the following properties: (1) \(x = S(t, y, z, \ldots)\) yields a
solution to \(E = 0\) for any choice of relation \(t\), and (2) every
solution \(x\) of \(E = 0\) can be obtained in this manner by choosing
a suitable \(t\). Peirce was not impressed by Schroder's
preoccupation with the problem of solving equations, and pointed out
that Schroder's parametric solution was a bit of a hoax--the
expressive power of the algebra of logic for relations was so strong
that by evaluating the term \(S(t, y, z, \ldots)\) one essentially
carried out the steps to check if \(E(t, y, z, \ldots) = 0\); if the
answer was yes then \(S(t, y, z, \ldots)\) returned the value \(t\),
otherwise it would return the value \(x0\).



Summing up, Schroder constructed an algebraic version of modern
predicate logic and also a theory of relations. He applied it to
different fields (e.g., Cantor's set theory), and he considered his
algebraic notation as a general or universal language
(*pasigraphy*, see Peckhaus 2004 and Legris 2012). It is to be
noted that Lowenheim in 1940 still thought it was as reasonable
as set theory. According to him, Schroder's idea of solving a
relational equation was a precursor of Skolem functions, and
Schroder inspired Lowenheim's formulation and proof of the
famous theorem that every "arithmetical" sentence with an
infinite model has a countable model. Schroder's calculus of
relations was the basis for the doctoral dissertation of Norbert
Wiener (1894-1964) in Harvard (Wiener 1913). According to Brady,
Wiener gave the first axiomatic treatment of the calculus of
relations, preceding Tarski's axiomatization by more than twenty years
(see Brady 2000: 165).


## 8. Huntington: Axiomatic Investigations of the Algebra of Logic



At the turn of the 19th Century, David Hilbert
(1862-1943) presented, in his *Grundlagen der Geometrie*,
Euclidean geometry as an axiomatic subject that did not depend on
diagrams for its proofs (Hilbert 1899). This led to a wave of interest
in studying axiom systems in mathematics; in particular one wanted to
know if the axioms were independent, and which primitives led to the
most elegant systems. Edward Vermilye Huntington (1874-1952) was
one of the first to examine this issue for the algebra of logic. He
gave three axiomatizations of the algebra of logic, showed each set of
axioms was independent, and that they were equivalent (see Huntington
1904). In 1933 he returned to this topic with three new sets of
axioms, one of which contained the following three equations (1933:
280):

 

\[ \begin{align} a + b &= b + a \\ (a + b) + c &= a + (b + c)
\\ (a' + b')' + (a' + b)' &= a. \end{align} \]


Shortly after this, Herbert Robbins (1915-2001) conjectured that
the third equation could be replaced by the slightly simpler



\[ [(a + b)' + (a + b')']' = a. \]


Neither Huntington nor Robbins could prove this, and later it
withstood the efforts of many others, including even Tarski and his
talented school at Berkeley. Building on partial results of Winker,
the automated theorem prover EQP, designed by William McCune of the
Argonne National Laboratory, found a proof of the Robbins Conjecture
in 1996. This accomplishment was popularized in Kolata 2010.



According to Huntington (1933: 278), the term "Boolean
algebra" was introduced by Henry M. Sheffer (1882-1964) in
the paper where he showed that one could give a five-equation
axiomatization of Boolean algebra using the single fundamental
operation of joint exclusion, now known as the Sheffer stroke (see
Sheffer 1913). Whitehead and Russell claimed in the preface to the
second edition of *Principia* that the Sheffer stroke was the
greatest advance in logic since the publication of *Principia*.
(Hilbert and Ackermann (1928), by contrast, stated that the Sheffer
stroke was just a curiosity.) Neither realized that decades earlier
Schroder had discovered that the dual of the Sheffer stroke was
also such an operation--Schroder's symbol for his operation
was that of a double-edged sword.



In the 1930s Garrett Birkhoff (1911-1996) established the
fundamental results of equational logic, namely (1) equational classes
of algebras are precisely the classes closed under homomorphisms,
subalgebras and direct products, and (2) equational logic is based on
five rules: reflexivity, symmetry, transitivity, replacement, and
substitution. In the 1940s, Tarski joined in this development of
equational logic; the subject progressed rapidly from the 1950s till
the present time.


## 9. Stone: Models for the Algebra of Logic



Traditional logic studied certain simple relationships between
classes, namely *being a subclass of* and *having a nonempty
intersection with*. However, once one adopted an axiomatic
approach, the topic of possible models besides the obvious ones
surfaced. Beltrami introduced models of non-Euclidean geometry in the
late 1860s. In the 1890s Schroder and Dedekind constructed models
of the axioms of lattice theory to show that the distributive law did
not follow. But when it came to the algebra of classes, Schroder
considered only the standard models, namely each was the collection of
all subclasses of a given class.



The study of general models of the axioms of Boolean algebra did not
get underway until the late 1920s; it was soon brought to a very high
level in the work of Marshall Harvey Stone (1903-1989) (see his
papers 1936, 1937). He was interested in the structure of rings of
linear operators and realized that the central idempotents, that is,
the operators \(E\) that commuted with all other operators in the ring
under multiplication (that is, \(EL = LE\) for all \(L\) in the ring)
and which were idempotent under multiplication (\(EE = E\)) played an
important role. In a natural way, the central idempotents formed a
Boolean algebra.



Pursuing this direction of research led Stone to ask about the
structure of an arbitrary Boolean algebra, a question that he answered
by proving that *every Boolean algebra is isomorphic to a Boolean
algebra of sets*. In his work on Boolean algebras he noticed a
certain analogy between kernels of homomorphisms and the ideals
studied in ring theory--this led him to give the name
"ideal" to such kernels. Not long after this he discovered
a translation between Boolean algebras and Boolean rings; under this
translation the ideals of a Boolean algebra corresponded precisely to
the ideals of the associated Boolean ring. His next major contribution
was to establish a correspondence between Boolean algebras and certain
topological spaces now called Boolean spaces (or Stone spaces). This
correspondence would later prove to be a valuable tool in the
construction of exotic Boolean algebras. These results of Stone are
still a paradigm for developments in the algebra of logic.



Inspired by the rather brief treatment of first-order statements about
relations in Vol. III of the *Algebra der Logik*,
Lowenheim (1915) showed that if such a statement could be
satisfied in an infinite domain then it could be satisfied in a
denumerable domain. In 1920 Thoralf Skolem (1887-1963)
simplified Lowenheim's proof by introducing Skolem normal forms,
and in 1928 Skolem replaced his use of normal forms with a simpler
idea, namely to use what are now called Skolem functions. He used
these functions to convert first-order sentences into universal
sentences, that is to say, into sentences in prenex form with all
quantifiers being universal (\(\forall\)).


## 10. Skolem: Quantifier Elimination and Decidability



Skolem was strongly influenced by Schroder's *Algebra der
Logik*, starting with his PhD Thesis. Later he took a particular
interest in the quest for an Elimination Theorem in the calculus of
classes. In his 1919 paper he established some results for lattices,
in particular, he showed that one could decide the validity of
universal Horn sentences (i.e., universal sentences with a matrix that
is a disjunction of negated and unnegated atoms, with at most one
positive atom) by a procedure that we now recognize to be a polynomial
time algorithm. This algorithm was based on finding a least fixed
point of a finite partial lattice under production rules derived from
universal Horn sentences. Although this result, which is equivalent to
the uniform word problem for lattices, was in the same paper as
Skolem's famous contribution to Lowenheim's Theorem, it was
forgotten until a chance rediscovery in the early 1990s. (Whitman
(1941) gave a different solution to the more limited equational
decision problem for lattices; it became widely known as the solution
to the word problem in lattices.)



Skolem (1920) gave an elegant solution to the Elimination Problem
posed by Schroder for the calculus of classes by showing that if
one added predicates to express "has at least \(n\)
elements", for each \(n = 1, 2, \ldots\), then there was a
simple (but often lengthy) procedure to convert a first-order formula
about classes into a quantifier-free formula. In particular this
showed that the first-order theory of the calculus of classes was
decidable. This quantifier-elimination result was used by Mostowski
(1952) to analyze first-order properties of direct powers and direct
sums of single structures, and then by Feferman and Vaught (1959) to
do the same for general direct sums and direct products of
structures.



The elimination of quantifiers became a main method in mathematical
logic to prove decidability, and proving decidability was stated as
the main problem of mathematical logic in Hilbert and Ackermann
(1928)--this goal was dropped in subsequent editions because of
the famous undecidability result of Church and Turing.


## 11. Tarski and the Revival of Algebraic Logic



Model theory can be regarded as the product of Hilbert's methodology
of metamathematics and the algebra of logic tradition, represented
specifically by the results due to Lowenheim and Skolem. But it
was Tarski who gave the discipline its classical foundation. Model
theory is the study of the relations between a formal language and its
interpretation in "realizations" (that is, a domain for
the variables of the language together with an interpretation for its
primitive signs). If the interpretation happens to make a sentence of
the language state something true, then the interpretation is a
*model* of the sentence (see the entry on
 model theory).
 Models consist basically of algebraic structures, and model theory
became an autonomous mathematical discipline with its roots not only
in the algebra of logic but in abstract algebra (see Sinaceur
1999).



Apart from model theory, Tarski revived the algebra of relations in
his 1941 paper "On the Calculus of Relations". First he
outlined a formal logic based on allowing quantification over both
elements and relations, and then he turned to a more detailed study of
the quantifier-free formulas of this system that involved only
relation variables. After presenting a list of axioms that obviously
held in the algebra of relations as presented in Schroder's third
volume he proved that these axioms allowed one to reduce
quantifier-free relation formulas to equations. Thus his calculus of
relations became the study of a certain equational theory which he
noted had the same relation to the study of all binary relations on
sets as the equational theory of Boolean algebra had to the study of
all subsets of sets. This led to questions paralleling those already
posed and resolved for Boolean algebras, for example, was every model
of his axioms for relation algebras isomorphic to an algebra of
relations on a set? One question had been answered by Arwin Korselt
(1864-1947), namely there were first-order sentences in the
theory of binary relations that were not equivalent to an equation in
the calculus of relations--thus the calculus of relations
definitely had a weaker expressive power than the first-order theory
of relations. Actually the expressive power of relation algebra is
exactly equivalent to first-order logic with just three variables.
However, if in relation algebras (the calculus of relations) one wants
to formalize a set theory which has something such as the pair axiom,
then one can reduce many variables to three variables, and so it is
possible to express any first-order statement of such a theory by an
equation. Monk proved that, unlike the calculus of classes, there is
no finite equational basis for the calculus of binary relations (see
Monk 1964). Tarski and Givant (1987) showed that the equational logic
of relation algebras is so expressive that one can carry out
first-order set theory in it.



Furthermore, cylindric algebras, essentially Boolean algebras equipped
with unary cylindric operations \(C\_x\) which are intended to capture
the existential quantifiers (\(\exists x\)), were introduced in the
years 1948-1952 by Tarski, working with his students Louise Chin
and Frederick Thompson (see Henkin & Tarski 1961), to create an
algebra of logic that captured the expressive power of the first-order
theory of binary relations. Polyadic algebra is another approach to an
algebra of logic for first-order logic--it was created by Halmos
(1956c). The focus of work in these systems was again to see to what
extent one could parallel the famous results of Stone for Boolean
algebra from the 1930s.