Abstract Algebraic Logic
Encyclopedia
In mathematical logic
, abstract algebraic logic is the study of the algebraization of deductive systems
arising as an abstraction of the well-known Lindenbaum-Tarski algebra, and how the resulting algebras are related to logical systems.
and lying at the heart of all subsequently developed subtheories, is the association between the class of Boolean algebras and classical propositional calculus
. This association was discovered by George Boole
in the 1850s, and refined by others, especially Ernst Schröder
in the 1890s. This work culminated in Lindenbaum-Tarski algebras, devised by Alfred Tarski
and his student Adolf Lindenbaum
in the 1930s. Later, Tarski and his American students (whose ranks include Don Pigozzi) went on to discover cylindric algebra
, which algebraizes all of classical first-order logic
, and revived relation algebra
, whose models
include all well-known axiomatic set theories.
Classical algebraic logic, which comprises all work in algebraic logic until about 1960, studied the properties of specific classes of algebras used to "algebraize" specific logical systems of particular interest to specific logical investigations. Generally, the algebra associated with a logical system was found to be a type of lattice
, possibly enriched with one or more unary operation
s other than lattice complementation
.
Abstract algebraic logic is a modern subarea of algebraic logic that emerged in Poland during the 1950s and 60s with the work of Helena Rasiowa
, Roman Sikorski
, Jerzy Łoś, and Roman Suszko (to name but a few). It reached maturity in the 1980s with the seminal publications of the Polish logician Janusz Czelakowski, the Dutch logician Wim Blok and the American logician Don Pigozzi. The focus of AAL shifted from the study of specific classes of algebras associated with specific logical systems (the focus of classical algebraic logic), to the study of:
The passage from classical algebraic logic to abstract algebraic logic may be compared to the passage from "modern" or abstract algebra
(i.e., the study of groups
, rings
, modules
, fields
, etc.) to universal algebra
(the study of classes of algebras of arbitrary similarity types (algebraic signature
s) satisfying specific abstract properties).
The two main motivations for the development of abstract algebraic logic are closely connected to (1) and (3) above. With respect to (1), a critical step in the transition was initiated by the work of Rasiowa. Her goal was to abstract results and methods known to hold for the classical propositional calculus
and Boolean algebras and some other closely related logical systems, in such a way that these results and methods could be applied to a much wider variety of propositional logics.
(3) owes much to the joint work of Blok and Pigozzi exploring the different forms that the well-known deduction theorem
of classical propositional calculus and first-order logic
takes on in a wide variety of logical systems. They related these various forms of the deduction theorem to the properties of the algebraic counterparts of these logical systems.
Abstract algebraic logic has become a well established subfield of algebraic logic, with many deep and interesting results. These results explain many properties of different classes of logical systems previously explained only in a case by case basis or shrouded in mystery. Perhaps the most important achievement of AAL has been the classification of propositional logics in a hierarchy
, called the abstract algebraic hierarchy or Leibniz hierarchy, whose different levels roughly reflect the strength of the ties between a logic at a particular level and its associated class of algebras. The position of a logic in this hierarchy determines the extent to which that logic may be studied using known algebraic methods and techniques. Once a logic is assigned to a level of this hierarchy, one may draw on the powerful arsenal of results, accumulated over the past 30-odd years, governing the algebras situated at the same level of the hierarchy.
The above terminology can be misleading. 'Abstract Algebraic Logic' is often used to indicate the approach of the Hungarian School including Hajnal Andréka, István Németi and others. What is termed 'Abstract Algebraic Logic' in the above paragraphs should be 'Algebraic Logic'. Algebraization of Gentzen systems by Ramon Jansana, J. Font and others is a significant improvement over 'algebraic logic'.
Mathematical logic
Mathematical logic is a subfield of mathematics with close connections to foundations of mathematics, theoretical computer science and philosophical logic. The field includes both the mathematical study of logic and the applications of formal logic to other areas of mathematics...
, abstract algebraic logic is the study of the algebraization of deductive systems
arising as an abstraction of the well-known Lindenbaum-Tarski algebra, and how the resulting algebras are related to logical systems.
Overview
The archetypal association of this kind, one fundamental to the historical origins of algebraic logicAlgebraic logic
In mathematical logic, algebraic logic is the study of logic presented in an algebraic style.What is now usually called classical algebraic logic focuses on the identification and algebraic description of models appropriate for the study of various logics and connected problems...
and lying at the heart of all subsequently developed subtheories, is the association between the class of Boolean algebras and classical propositional calculus
Propositional calculus
In mathematical logic, a propositional calculus or logic is a formal system in which formulas of a formal language may be interpreted as representing propositions. A system of inference rules and axioms allows certain formulas to be derived, called theorems; which may be interpreted as true...
. This association was discovered by George Boole
George Boole
George Boole was an English mathematician and philosopher.As the inventor of Boolean logic—the basis of modern digital computer logic—Boole is regarded in hindsight as a founder of the field of computer science. Boole said,...
in the 1850s, and refined by others, especially Ernst Schröder
Ernst Schröder
Ernst Schröder was a German mathematician mainly known for his work on algebraic logic. He is a major figure in the history of mathematical logic , by virtue of summarizing and extending the work of George Boole, Augustus De Morgan, Hugh MacColl, and especially Charles Peirce...
in the 1890s. This work culminated in Lindenbaum-Tarski algebras, devised by Alfred Tarski
Alfred Tarski
Alfred Tarski was a Polish logician and mathematician. Educated at the University of Warsaw and a member of the Lwow-Warsaw School of Logic and the Warsaw School of Mathematics and philosophy, he emigrated to the USA in 1939, and taught and carried out research in mathematics at the University of...
and his student Adolf Lindenbaum
Adolf Lindenbaum
Adolf Lindenbaum , was a Polish logician and mathematician.He was a student of Wacław Sierpiński, became a distinguished author of works on set theory and had served as an Assistant Professor at Warsaw University...
in the 1930s. Later, Tarski and his American students (whose ranks include Don Pigozzi) went on to discover cylindric algebra
Cylindric algebra
The notion of cylindric algebra, invented by Alfred Tarski, arises naturally in the algebraization of first-order logic with equality. This is comparable to the role Boolean algebras play for propositional logic. Indeed, cylindric algebras are Boolean algebras equipped with additional...
, which algebraizes all of classical first-order logic
First-order logic
First-order logic is a formal logical system used in mathematics, philosophy, linguistics, and computer science. It goes by many names, including: first-order predicate calculus, the lower predicate calculus, quantification theory, and predicate logic...
, and revived relation algebra
Relation algebra
In mathematics and abstract algebra, a relation algebra is a residuated Boolean algebra expanded with an involution called converse, a unary operation...
, whose models
Model theory
In mathematics, model theory is the study of mathematical structures using tools from mathematical logic....
include all well-known axiomatic set theories.
Classical algebraic logic, which comprises all work in algebraic logic until about 1960, studied the properties of specific classes of algebras used to "algebraize" specific logical systems of particular interest to specific logical investigations. Generally, the algebra associated with a logical system was found to be a type of lattice
Lattice (order)
In mathematics, a lattice is a partially ordered set in which any two elements have a unique supremum and an infimum . Lattices can also be characterized as algebraic structures satisfying certain axiomatic identities...
, possibly enriched with one or more unary operation
Unary operation
In mathematics, a unary operation is an operation with only one operand, i.e. a single input. Specifically, it is a functionf:\ A\to Awhere A is a set. In this case f is called a unary operation on A....
s other than lattice complementation
Complemented lattice
In the mathematical discipline of order theory, a complemented lattice is a bounded lattice in which every element a has a complement, i.e. an element b satisfying a ∨ b = 1 and a ∧ b = 0....
.
Abstract algebraic logic is a modern subarea of algebraic logic that emerged in Poland during the 1950s and 60s with the work of Helena Rasiowa
Helena Rasiowa
Helena Rasiowa was a Polish mathematician. She worked in the foundations of mathematics and algebraic logic.-Early years:...
, Roman Sikorski
Roman Sikorski
Roman Sikorski was a Polish mathematician.Sikorski was from 1952 until 1982 professor at the Warsaw University...
, Jerzy Łoś, and Roman Suszko (to name but a few). It reached maturity in the 1980s with the seminal publications of the Polish logician Janusz Czelakowski, the Dutch logician Wim Blok and the American logician Don Pigozzi. The focus of AAL shifted from the study of specific classes of algebras associated with specific logical systems (the focus of classical algebraic logic), to the study of:
- Classes of algebras associated with classes of logical systems whose members all satisfy certain abstract logical properties;
- The process by which a class of algebras becomes the "algebraic counterpart" of a given logical system;
- The relation between metalogical properties satisfied by a class of logical systems, and the corresponding algebraic properties satisfied by their algebraic counterparts.
The passage from classical algebraic logic to abstract algebraic logic may be compared to the passage from "modern" or abstract algebra
Abstract algebra
Abstract algebra is the subject area of mathematics that studies algebraic structures, such as groups, rings, fields, modules, vector spaces, and algebras...
(i.e., the study of groups
Group (mathematics)
In mathematics, a group is an algebraic structure consisting of a set together with an operation that combines any two of its elements to form a third element. To qualify as a group, the set and the operation must satisfy a few conditions called group axioms, namely closure, associativity, identity...
, rings
Ring (mathematics)
In mathematics, a ring is an algebraic structure consisting of a set together with two binary operations usually called addition and multiplication, where the set is an abelian group under addition and a semigroup under multiplication such that multiplication distributes over addition...
, modules
Module (mathematics)
In abstract algebra, the concept of a module over a ring is a generalization of the notion of vector space, wherein the corresponding scalars are allowed to lie in an arbitrary ring...
, fields
Field (mathematics)
In abstract algebra, a field is a commutative ring whose nonzero elements form a group under multiplication. As such it is an algebraic structure with notions of addition, subtraction, multiplication, and division, satisfying certain axioms...
, etc.) to universal algebra
Universal algebra
Universal algebra is the field of mathematics that studies algebraic structures themselves, not examples of algebraic structures....
(the study of classes of algebras of arbitrary similarity types (algebraic signature
Signature (logic)
In logic, especially mathematical logic, a signature lists and describes the non-logical symbols of a formal language. In universal algebra, a signature lists the operations that characterize an algebraic structure. In model theory, signatures are used for both purposes.Signatures play the same...
s) satisfying specific abstract properties).
The two main motivations for the development of abstract algebraic logic are closely connected to (1) and (3) above. With respect to (1), a critical step in the transition was initiated by the work of Rasiowa. Her goal was to abstract results and methods known to hold for the classical propositional calculus
Propositional calculus
In mathematical logic, a propositional calculus or logic is a formal system in which formulas of a formal language may be interpreted as representing propositions. A system of inference rules and axioms allows certain formulas to be derived, called theorems; which may be interpreted as true...
and Boolean algebras and some other closely related logical systems, in such a way that these results and methods could be applied to a much wider variety of propositional logics.
(3) owes much to the joint work of Blok and Pigozzi exploring the different forms that the well-known deduction theorem
Deduction theorem
In mathematical logic, the deduction theorem is a metatheorem of first-order logic. It is a formalization of the common proof technique in which an implication A → B is proved by assuming A and then proving B from this assumption. The deduction theorem explains why proofs of conditional...
of classical propositional calculus and first-order logic
First-order logic
First-order logic is a formal logical system used in mathematics, philosophy, linguistics, and computer science. It goes by many names, including: first-order predicate calculus, the lower predicate calculus, quantification theory, and predicate logic...
takes on in a wide variety of logical systems. They related these various forms of the deduction theorem to the properties of the algebraic counterparts of these logical systems.
Abstract algebraic logic has become a well established subfield of algebraic logic, with many deep and interesting results. These results explain many properties of different classes of logical systems previously explained only in a case by case basis or shrouded in mystery. Perhaps the most important achievement of AAL has been the classification of propositional logics in a hierarchy
Hierarchy (mathematics)
In mathematics, a hierarchy is a preorder, i.e. an ordered set. The term is used to stress a natural hierarchical relation among the elements. In particular, it is the preferred terminology for posets whose elements are classes of objects of increasing complexity. In that case, the preorder...
, called the abstract algebraic hierarchy or Leibniz hierarchy, whose different levels roughly reflect the strength of the ties between a logic at a particular level and its associated class of algebras. The position of a logic in this hierarchy determines the extent to which that logic may be studied using known algebraic methods and techniques. Once a logic is assigned to a level of this hierarchy, one may draw on the powerful arsenal of results, accumulated over the past 30-odd years, governing the algebras situated at the same level of the hierarchy.
The above terminology can be misleading. 'Abstract Algebraic Logic' is often used to indicate the approach of the Hungarian School including Hajnal Andréka, István Németi and others. What is termed 'Abstract Algebraic Logic' in the above paragraphs should be 'Algebraic Logic'. Algebraization of Gentzen systems by Ramon Jansana, J. Font and others is a significant improvement over 'algebraic logic'.
Examples
| Logical system | Algebraic counterpart |
| Propositional logic | Boolean algebras |
| Intuitionistic Intuitionistic logic Intuitionistic logic, or constructive logic, is a symbolic logic system differing from classical logic in its definition of the meaning of a statement being true. In classical logic, all well-formed statements are assumed to be either true or false, even if we do not have a proof of either... propositional logic |
Heyting algebra Heyting algebra In mathematics, a Heyting algebra, named after Arend Heyting, is a bounded lattice equipped with a binary operation a→b of implication such that ∧a ≤ b, and moreover a→b is the greatest such in the sense that if c∧a ≤ b then c ≤ a→b... s |
| Propositional modal logic Modal logic Modal logic is a type of formal logic that extends classical propositional and predicate logic to include operators expressing modality. Modals — words that express modalities — qualify a statement. For example, the statement "John is happy" might be qualified by saying that John is... |
Boolean algebras with operators |
| First-order logic First-order logic First-order logic is a formal logical system used in mathematics, philosophy, linguistics, and computer science. It goes by many names, including: first-order predicate calculus, the lower predicate calculus, quantification theory, and predicate logic... |
Cylindric algebra Cylindric algebra The notion of cylindric algebra, invented by Alfred Tarski, arises naturally in the algebraization of first-order logic with equality. This is comparable to the role Boolean algebras play for propositional logic. Indeed, cylindric algebras are Boolean algebras equipped with additional... s Polyadic algebra Polyadic algebra Polyadic algebras are algebraic structures introduced by Paul Halmos. They are related to first-order logic in a way analogous to the relationship between Boolean algebras and propositional logic .There are other ways to relate first-order logic to algebra, including Tarski's cylindric algebras... Predicate functor logic Predicate functor logic In mathematical logic, predicate functor logic is one of several ways to express first-order logic by purely algebraic means, i.e., without quantified variables. PFL employs a small number of algebraic devices called predicate functors that operate on terms to yield terms... |
| Set theory Set theory Set theory is the branch of mathematics that studies sets, which are collections of objects. Although any type of object can be collected into a set, set theory is applied most often to objects that are relevant to mathematics... |
Combinatory logic Combinatory logic Combinatory logic is a notation introduced by Moses Schönfinkel and Haskell Curry to eliminate the need for variables in mathematical logic. It has more recently been used in computer science as a theoretical model of computation and also as a basis for the design of functional programming... Relation algebra Relation algebra In mathematics and abstract algebra, a relation algebra is a residuated Boolean algebra expanded with an involution called converse, a unary operation... |
See also
- Abstract algebraAbstract algebraAbstract algebra is the subject area of mathematics that studies algebraic structures, such as groups, rings, fields, modules, vector spaces, and algebras...
- Algebraic logicAlgebraic logicIn mathematical logic, algebraic logic is the study of logic presented in an algebraic style.What is now usually called classical algebraic logic focuses on the identification and algebraic description of models appropriate for the study of various logics and connected problems...
- Abstract model theoryAbstract model theoryIn mathematical logic, abstract model theory is a generalization of model theory which studies the general properties of extensions of first-order logic and their models....
- Hierarchy (mathematics)Hierarchy (mathematics)In mathematics, a hierarchy is a preorder, i.e. an ordered set. The term is used to stress a natural hierarchical relation among the elements. In particular, it is the preferred terminology for posets whose elements are classes of objects of increasing complexity. In that case, the preorder...
- Model theoryModel theoryIn mathematics, model theory is the study of mathematical structures using tools from mathematical logic....
- Variety (universal algebra)Variety (universal algebra)In mathematics, specifically universal algebra, a variety of algebras is the class of all algebraic structures of a given signature satisfying a given set of identities. Equivalently, a variety is a class of algebraic structures of the same signature which is closed under the taking of homomorphic...
- Universal logicUniversal logicUniversal logic is the field of logic that is concerned with giving an account of what features are common to all logical structures. Universal logic aims to be to logic what universal algebra is to algebra; currently there is no universally accepted notion of logic...
External links
- Stanford Encyclopedia of PhilosophyStanford Encyclopedia of PhilosophyThe Stanford Encyclopedia of Philosophy is a freely-accessible online encyclopedia of philosophy maintained by Stanford University. Each entry is written and maintained by an expert in the field, including professors from over 65 academic institutions worldwide...
: "Propositional Consequence Relations and Algebraic Logic" -- by Ramon Jansana.