Cylindric-like Algebras and Algebraic Logic

The theory of cylindric algebras (CAs) and Tarskian algebraic logic have been immensely successful in, e.g., applications to such a diversity of fields as logic, mathematics, computer science, artificial intelligence, linguistics and even relativity theory. In some of the applications one has to transcend (a little) the original definition of CAs but not its spirit. For example, the emphasis shifted to relativized CAs and to adding extra operations such as, e.g., substitutions (s_τ s). To keep the original Tarskian spirit of CAs, in this volume we consider only quasi-polyadic operations (e.g., substitutions where τ is finite) as opposed to Halmos’ polyadic ones (e.g., substitutions with all infinite τs). These and similar generalizations are the reason for “cylindric-like” algebras in the title in place of simply CAs.

Alfred Tarski in 1953 formalized set theory in the equational theory of relation algebras [Tar,53a, Tar,53b]. Why did he do so? Because the equational theory of relation algebras (RA) corresponds to a logic without individual variables, in other words, to a propositional logic. This is why the title of the book [Tar-Giv,87] is “Formalizing set theory without variables”. Tarski got the surprising result that a propositional logic can be strong enough to “express all of mathematics”, to be the arena for mathematics. The classical view before this result was that propositional logics in general were weak in expressive power, decidable, uninteresting in a sense. By using the fact that set theory can be built up in it, Tarski proved that the equational theory of RA is undecidable. This was the first propositional logic shown to be undecidable.

In this chapter we survey recent developments in the theory of twodimensional cylindric algebras. In particular, we will deal with varieties of two-dimensional diagonal-free cylindric algebras and with varieties of two-dimensional cylindric algebras with the diagonal. It is well known that two-dimensional diagonal-free cylindric algebras correspond to the two variable equality-free fragment of classical first-order logic FOL, whereas two-dimensional cylindric algebras with the diagonal correspond to the two variable fragment of FOL with equality. It is also well known that one-dimensional cylindric algebras, also called Halmos monadic algebras, provide algebraic completeness for the one variable fragment of FOL. For a systematic discussion on the connection between various fragments of FOL and classes of (cylindric) algebras that correspond to these fragments we refer to [And-Nem-Sai,01].

The title of this chapter indicates a rather technical topic, but it can also be thought of as a foundational issue in logic. The question to be considered is this: to what extent can we use an abstract mathematical language to express and reason about relations? Going back at least as far as Augustus de Morgan [Mor,60], a relation can be defined explicitly, as a set of tuples of some fixed length. This allows us to focus on the mathematical aspects of relations and ignore other more problematic features that might arise from other approaches, such as a linguistic analysis of the use of relations in natural language. In order to treat relations algebraically, we consider them abstractly, identify certain relational operations (e.g., the operation of taking the converse of a binary relation) and write down some equational axioms which are sound for the chosen kind of relations (e.g., a binary relation is equal to the converse of its converse). Ideally, our set G of equations will be equationally complete, so that any equation valid over fields of relations of a certain rank equipped with the chosen set-theoretically definable operators will be entailed by Γ.

The amalgamation property (for classes of models), since its discovery, has played a dominant role in algebra and model theory. Algebraic logic is the natural interface between universal algebra and logic (in our present context a variant of first order logic). Indeed, in algebraic logic amalgamation properties in classes of algebras are proved to be equivalent to interpolation results in the corresponding logic. In algebra, the properties of epimorphisms (in the categorial sense) being surjective is well studied. In algebraic logic, this property is strongly related to the famous Beth definability property [Hen-Mon-Tar,85] 5.6.10. Pigozzi [Pig,71] is a milestone for working out such equivalences for cylindric algebras, see also [Mad-Say,07], [And-Nem-Sai,01]. In first order logic, Craig interpolation theorem is equivalent to Beth definability theorem; however this equivalence no longer holds for certain modifications of first order logic, be it reducts or expansions, like L _n (first order logic restricted to finitely many n variables) and the extensions of first order logic studied in [Hen-Mon-Tar,85] Sec. 4.3, which are essentially finitary but have an infinitary flavour.

An important central concept introduced in [Hen-Mon-Tar,85] is that of neat reducts, and the related one of neat embeddings. The notion of neat reducts is due to Leon Henkin, and one can find that the discussion of this notion is comprehensive and detailed in [Hen-Mon-Tar,85] (closer to the end of the book). This notion proved useful in at least two respects. Analyzing the number of variables appearing in proofs of first order formulas [Hir-Hod,02c], and characterizing the class of representable algebras; those algebras that are isomorphic to genuine algebras of relations. In fact, several open problems that appeared in [Hen-Mon-Tar,85] are on neat reducts, some of which appeared in part 1, and (not yet resolved) appeared again in part 2. This paper, among other things, surveys the status of these problems 40 years after they first appeared. Long proofs are omitted, except for one, which gives the gist of techniques used to solve such kind of problems.

Representation theorems. As is known, cylindric algebras are not representable in the classical sense (as a subdirect product of cylindric set algebras), in general. But, the Resek-Thompson theorem states that if the system of cylindric axioms is extended by a new axiom, by the merry-goround property (MGR, for short), then the cylindric-like algebra obtained is representable by a cylindric relativized set algebra. Furthermore, if, in additional, axiom (C₄) is weakened (only the commutativity of the single substitutions is assumed) then it is representable by an algebra in D_α, (see [And-Tho,88] and [Fer,07a]). This style of representation theorem is closely connected with the completeness theorems based on the Henkin style semantics in mathematical logic. By an r-representation of a cylindric-like algebra we mean a representation by a cylindric-like relativized set algebra.

Had the class of cylindric set algebras turned out to be finitely (and/or nicely) axiomatizable, algebraic logic would have evolved along a markedly different path than it did in the past 40 years. Among other things, it would have probably spelled the end of the “abstract” class CA_α as a separate subject of research; after all, why bother with abstract algebras, if a few nice extra equations can get us from there to concrete algebras of relations. As it is, Monk’s 1969 result (and its various improvements by algebraic logicians from Andréka to Venema), stating that for α > 2, RCA_α is not axiomatizable finitely, meant, among other things, that CA_α was here to stay, and its “distance” from RCA_α became an important research topic. To mention just one example of how this distance can be measured, we refer to the representation theory of CAs, where sufficient conditions for a CA to be representable are sought. This line of research is typical: the question one asks here is “what is missing from CAs to be representable?”. But Henkin (himself a prolific contributor to representation theory) turned around this question and instead of asking how much CAs needed to be representable, he asked how much set algebras needed to be “distorted” to provide representations for all CAs. Now, if the answer is “very much”, then we haven’t got closer to understanding either CAs or the possible causes of their non-representability.

The equationally expressible properties of the cylindrifications and the diagonals in finite-dimensional representable cylindric algebras can be divided into two groups:

Algebraic logic arose as a subdiscipline of algebra mirroring constructions and theorems of mathematical logic. It is similar in this respect to such fields as algebraic geometry and algebraic topology, where the main constructions and theorems are algebraic in nature, but the main intuitions underlying them are respectively geometric and topological. The main intuitions underlying algebraic logic are, of course, those of formal logic. Investigations in algebraic logic can proceed in two conceptually different, but often (and unexpectedly) closely related ways. First one tries to investigate the algebraic essence of constructions and results in logic, in the hope of gaining more insight that one could add to his understanding, thus to his knowledge. Second, one can study certain “particular” algebraic structures (or simply algebras) that arise in the course of his first kind of investigations as objects of interest in their own right and go on to discuss questions which naturally arise independently of any connection with logic. But often such purely algebraic results have impact on the logic side. Examples are the undecidability of the representation problem for finite relation algebras [Hir-Hod,01d] that led to deep results concerning undecidability of product modal logics [Hir-Hod-Kur,02a] answering problems of Gabbay and Shehtman.

According to J. Donald Monk, one of the authors of ‘Cylindric Algebras’, the basic monograph on algebraic logic, the fact that the sets of all \( \phi ^\mathfrak{M} \)’s consisting of sequences satisfying the first order formula φ in the model \( \mathfrak{M} \) constitutes the universe of a cylindric set algebra is ‘the main motivating force for […] the whole topic of algebraic logic.’ (cf. [Mon,00] p. 453). Therefore, the investigation of cylindric set algebras from the point of view of their close links to first order models has a distinguished role in algebraic logic. In the course of this investigation, the specific properties of models (e.g. universality, homogeneity, saturatedness) become algebraic ones, and the various connections between models correspond to different kinds of isomorphisms between the cylindric set algebras concerned (see e.g. [Hen-Mon-Tar,85] 4.3.68(7) and (10), [Hen-Mon-Tar,85] pp. 37 and 45, [Mon,00] Sections 5 and 6).

Back and forth between algebra and model theory. Algebra and model theory are complementary stances in the history of logic, and their interaction continues to spawn new ideas, witness the interface of First-Order Logic and Cylindric Algebra. This chapter is about a more specialized contact: the flow of ideas between algebra and modal logic through ‘guarded fragments’ restricting the range of quantification over objects. Here is some general background for this topic. For a start, the connection between algebra and model theory is rather tight, since we can view universal algebra as the equational logic part of standard first-order model theory. As an illustration, van Benthem [Ben,88] has a purely model-theoretic proof of Jónsson’s Theorem characterizing the equational varieties with distributive lattices of congruence relations, a major tool of algebraists. Deeper connections arise in concrete cases with categorial dualities, such as that between BAOs and the usual relational models of modal logic. An important example is the main theorem in Goldblatt and Thomason [Gol-Tho,74] characterizing the elementary modally definable frame classes through their closure under taking generated sub-frames, disjoint unions, p-morphic images, and anti-closure under ultrafilter extensions. Its original proof goes back and forth between algebras and frames, in order to apply Birkhoff’s characterization of equational varieties.

Sometimes it is not enough to prove that a formula φ(x) is satisfied or not by an element a ∈ A in the model \( \mathfrak{A} \) we are interested in. It may happen that we are looking for the quantity of those a ∈ A for which φ[a] is true. Of course, the mathematical discipline for these considerations is probability theory. The logic suitable for this kind of reasoning was introduced by H. J. Keisler in 1976. This logic has formulas similar to those of L _A ⊆ L _ω1ω (A is a countable admissible set), except that the quantifiers (Px ≥ r) (r ∈ A ∪ [0, 1] is a real number) are used instead of the usual quantifiers (∀x) and (∃x). A model for this logic is a pair \( \left\langle {\mathfrak{A},\mu } \right\rangle \), where \( \mathfrak{A} \) is a classical structure and μ is a probability measure defined in such a way that definable subsets of the universe A are measurable. The quantifiers are interpreted in the natural way, i.e.

Independence-friendly logic (IF logic) [Hin,96, Hin-San,89] is a conservative extension of first-order logic that can be viewed as a generalization of Henkin’s branching quantifiers [Hen,61]. For example, in the branching quantifier sentence

Polyadic algebras were introduced and intensively studied by Halmos, after having studied cylindric algebras in Tarski’s seminar in Berkeley; we refer to Section 5.4 of [Hen-Mon-Tar,85], see also [Hal,62]. This class of algebras can be regarded as an alternative approach to algebraize first order logic. After a thorough reformulation of Henkin, Monk, and Tarski, polyadic algebras also can be regarded as certain generalizations of cylindric algebras. On one hand, polyadic algebras have nice representation properties, on the other, their languages are rather large (in the ω-dimensional case the cardinality of their set of operations is continuum), which makes their equational theory recursively undecidable for trivial reasons. This is undesirable from metalogical point of view, hence, during the last decades, certain countable (even finite) reducts of polyadic algebras have also been intensively studied. The goal of this research direction is to find a countable reduct of polyadic algebras which has nice representation properties, and, at the same time, their equational theory is recursively enumerable.

Besides Universal Logic (J-Y. Béziau [Bez,10], [Bez,05]) we focus on its predecessor Universal Algebraic Logic going back to the 70’s ([And-Ger-Nem,77], [And-Ger-Nem,73]) and originating with Tarski’s school, cf. [Hen-Mon-Tar,85, Part II, Sec. 5.6, p. 255].