Skip to main content

Über dieses Buch

This monograph details several different methods for constructing simple relation algebras, many of which are new with this book. By drawing these seemingly different methods together, all are shown to be aspects of one general approach, for which several applications are given. These tools for constructing and analyzing relation algebras are of particular interest to mathematicians working in logic, algebraic logic, or universal algebra, but will also appeal to philosophers and theoretical computer scientists working in fields that use mathematics.

The book is written with a broad audience in mind and features a careful, pedagogical approach; an appendix contains the requisite background material in relation algebras. Over 400 exercises provide ample opportunities to engage with the material, making this a monograph equally appropriate for use in a special topics course or for independent study. Readers interested in pursuing an extended background study of relation algebras will find a comprehensive treatment in author Steven Givant’s textbook, Introduction to Relation Algebras (Springer, 2017).



Rectangular and Equivalence Semiproducts


Chapter 1. Rectangular Semiproducts

An important technique for analyzing the structure of a subalgebra of a simple relation algebra is to break that structure into smaller pieces, analyze those pieces, and then describe how the overall structure of the algebra—its elements and operations—can be recovered from the pieces. This chapter provides a framework for a method of breaking the structure into smaller pieces using rectangles. A different method that uses equivalence elements is described in the next chapter.
Steven Givant, Hajnal Andréka

Chapter 2. Equivalence Semiproducts

In this chapter, we develop the framework for a method of breaking the structure of a simple relation algebra into smaller pieces using reflexive equivalence elements. The method is motivated by the following question (see [14] and Chapter 5): if one relativizes a simple relation algebra \(\mathfrak{S}\) to a reflexive equivalence element e, what subalgebra of \(\mathfrak{S}\) does the relativization \(\mathfrak{S}(e)\) generate?
Steven Givant, Hajnal Andréka

Diagonal Semiproducts, Semipowers, Simple Closures, and Quasi-bijective Relation Algebras


Chapter 3. Diagonal Semiproducts

In this chapter, we discuss a semiproduct construction that was introduced by Jónsson in [27] (under the name “semiproducts”). The underlying idea is easy to describe.
Steven Givant, Hajnal Andréka

Chapter 4. Semipowers

In the semipower construction, a single simple relation algebra \(\mathfrak{B}\) and a power I are given, and bijections are used to make copies of \(\mathfrak{B}\) in every component of a corresponding rectangular system; see Figure 4.1. The construction is applied in Chapter 6 to described various classes of relation algebras for which representation theorems exist in the literature. It also serves as a paradigm for a more general and more intricate semiproduct construction that will be investigated in Chapter 8
Steven Givant, Hajnal Andréka

Chapter 5. Simple Closures

Every relation algebra can be constructed from simple relation algebras, because every relation algebra is isomorphic to a subdirect product of simple relation algebras. The task of understanding arbitrary relation algebras therefore reduces, in some sense, to the task of understanding simple relation algebras. Rather unexpectedly, it turns out that simple relation algebras are no easier to understand than arbitrary relation algebras. In fact, every relation algebra is a relativization of some (and usually many) simple relation algebras. In other words, for every relation algebra \(\mathfrak{B}\), there is a simple relation algebra \(\mathfrak{A}\) and a reflexive equivalence element e in \(\mathfrak{A}\) such that \(\mathfrak{A}(e) = \mathfrak{B}\). Among the various algebras that might satisfy this condition, it is natural to look for the smallest ones. This minimality condition translates into the requirement that the universe B generate \(\mathfrak{A}\). The goal of this chapter is to analyze the ways in which an arbitrary relation algebra \(\mathfrak{B}\) can be realized as a relativization (to a reflexive equivalence element) of a simple relation algebra that it generates. We shall call such algebras simple closures of \(\mathfrak{B}\).
Steven Givant, Hajnal Andréka

Chapter 6. Quasi-Bijective Relation Algebras

One of the principal focuses of research in the theory of relation algebras during the last sixty years has been on representation theorems, theorems which state that every relation algebra satisfying certain conditions is representable. A typical example is the theorem of Jónsson-Tarski [31] that every atomic relation algebra in which the atoms are all functional is representable; there is also an accompanying structural description of these algebras in terms of the complex algebras of Brandt groupoids.
Steven Givant, Hajnal Andréka

Quotient Algebras and Quotient Semiproducts


Chapter 7. Quotient Relation Algebras and Equijections

The semipower construction of Chapter 4 builds a simple relation algebra from a given simple base algebra by using bijections to copy the base algebra to each component of a rectangular system. A much more general and interesting construction is possible. Instead of copying the base algebra to each component, it is possible to copy various quotients of the base algebra, and even various quotients from a coordinated system of base algebras. This chapter investigates two critical components of the construction that are of independent interest: quotient relation algebras and equijections. Some historical remarks are gathered together at the end of the chapter.
Steven Givant, Hajnal Andréka

Chapter 8. Quotient Semiproducts

Quotient semiproducts constitute a substantial generalization of the semipower construction of Chapter 4 In the latter, a single simple relation algebra is given, and bijections are used to make isomorphic copies of this base algebra in every component of a corresponding rectangular system. In the quotient semiproduct construction, there is not a single base algebra, but rather a system of base algebras, and equijections are used to make isomorphic copies, not of the base algebras, but of quotients of the base algebras. (A base algebra can, itself, be such a quotient, namely the quotient by the identity element.) Moreover, the various copies of a given base algebra need not be copies of the same quotient. This provides a good deal of flexibility in the construction, and allows for a much greater variety of structure within and between the various components of the final semiproduct than is possible in the semipower construction (Figure 8.1).
Steven Givant, Hajnal Andréka

Chapter 9. Group and Geometric Quotient Semiproducts

This chapter presents two concrete examples of the quotient semiproduct construction from Chapter 8 In the first example, the base algebras are algebras of subsets, or complexes, of groups under the usual set-theoretic Boolean operations and the relative operations induced by the group operations on complexes. I n the second example, the base algebras are algebras of complexes of projective geometries (augmented by an identity element) under the set-theoretic Boolean operations and the relative operations induced by the collinearity relation. In both cases, it is shown that a quotient semiproduct system can always be reduced to a corresponding system consisting of groups and group quotient isomorphisms, or geometries and geometric quotient isomorphisms, respectively. This reduction leads to substantial simplifications in terminology and notation.
Steven Givant, Hajnal Andréka

Insertion Semiproducts and 2–Quasi–Bijective Relation Algebras


Chapter 10. Insertion Semiproducts

We now describe a way of inserting new elements into a given simple relation algebra \(\mathfrak{B}\). The location of the insertion is determined by a reflexive equivalence element e, while the blueprint for the insertion is determined by a relation algebra \(\mathfrak{C}\). The portion of \(\mathfrak{B}\) that is below e—which is just the relativization \(\mathfrak{B}(e)\)—is enlarged by adjoining copies of the elements of \(\mathfrak{C}\) (see Figure 10.1).
Steven Givant, Hajnal Andréka

Chapter 11. Two-Quasi-Bijective Relation Algebras

We now apply the insertion semiproduct construction of Chapter 10 to extend some of the results in Chapter 6 concerning quasi-bijective relation algebras. Recall that a relation algebra is said to be quasi-bijective relation if it is atomic and if each rectangle with atomic sides is above at most one non-bijective atom. A complete description of these algebras is given in Structure Theorem 6.10, and a consequence of the description is that quasi-bijective relation algebras are always completely representable (see Representation Theorem 6.11).
Steven Givant, Hajnal Andréka


Weitere Informationen

Premium Partner

BranchenIndex Online

Die B2B-Firmensuche für Industrie und Wirtschaft: Kostenfrei in Firmenprofilen nach Lieferanten, Herstellern, Dienstleistern und Händlern recherchieren.



Best Practices für die Mitarbeiter-Partizipation in der Produktentwicklung

Unternehmen haben das Innovationspotenzial der eigenen Mitarbeiter auch außerhalb der F&E-Abteilung erkannt. Viele Initiativen zur Partizipation scheitern in der Praxis jedoch häufig. Lesen Sie hier  - basierend auf einer qualitativ-explorativen Expertenstudie - mehr über die wesentlichen Problemfelder der mitarbeiterzentrierten Produktentwicklung und profitieren Sie von konkreten Handlungsempfehlungen aus der Praxis.
Jetzt gratis downloaden!