Strongly representable atom structures of relation algebras
The atom structure \(\alpha\) of an atomic relation algebra is said to be strongly representable if the complex algebra of \(\alpha\) is a representable relation algebra. This paper proves that the class of strongly representable atom structures of atomic relation algebras is not closed under the formation of ultraproducts, and therefore not an elementary class. This result solves a problem posed by the reviewer in ``Some varieties containing relation algebras [Trans. Am. Math. Soc. 272, 501-526 (1982; Zbl 0515.03039)]. The heart of the proof is the construction, from any symmetric irreflexive binary relation \(\Gamma\), of an atom structure \(\alpha(\Gamma)\) with the remarkable property that \(\alpha(\Gamma)\) is strongly representable if and only if the chromatic number of \(\Gamma\) is infinite. Using a result of Erdös, that there exist finite graphs with arbitrarily large girth and chromatic number, the authors construct, for each positive integer \(r\), a graph \(\Gamma_r\) with girth greater than \(r\) and infinite chromatic number. Every \(\alpha(\Gamma_r)\) is strongly representable, but every non-principal ultraproduct of the atom structures \(\alpha(\Gamma_r)\) has infinite girth, consequently has chromatic number 2, and is therefore not strongly representable.
- Weakly representable atom structures that are not strongly representable, with an application to first order logic
- scientific article; zbMATH DE number 38327
- scientific article; zbMATH DE number 5539272
- First-order axiomatisations of representable relation algebras need formulas of unbounded quantifier depth
- Completely Representable Relation Algebras
- Bifunctional-elementary relation algebras
- Various notions of represetability for cylindric and polyadic algebras
- A note on atom structures of relation and cylindric algebras
- A representation theorem for measurable relation algebras
- On the complexity of modal axiomatisations over many-dimensional structures
- A sequent calculus for relation algebras
- Atom structures and Sahlqvist equations
- Atom structures of cylindric algebras and relation algebras
- Complete representations in algebraic logic
- Complexity of equations valid in algebras of relations. I: Strong non-finitizability
- Cylindric algebras. Part I. With an introductory chapter: General theory of algebras. 2nd printing
- Every two elementarily equivalent models have isomorphic ultrapowers
- Graph Theory and Probability
- scientific article; zbMATH DE number 67032 (Why is no real title available?)
- scientific article; zbMATH DE number 67035 (Why is no real title available?)
- scientific article; zbMATH DE number 3078993 (Why is no real title available?)
- Model theory.
- Nonfinite axiomatizability results for cylindric and relation algebras
- Nonfinitizability of classes of representable cylindric algebras
- On representable relation algebras
- Some sufficient conditions for the representability of relation algebras
- Some Varieties Containing Relation Algebras
- Step by step – Building representations in algebraic logic
- The representation of relation algebras. II
- The representation of relational algebras
- Varieties of complex algebras
- Subcompletions of representable relation algebras
- Existence of certain finite relation algebras implies failure of omitting types for \(L_n\)
- Term algebras of elementarily equivalent atom structures
- On the variety generated by completions of representable relation algebras
- Strongly representable atom structures of cylindric algebras
- Weakly representable atom structures that are not strongly representable, with an application to first order logic
- scientific article; zbMATH DE number 38327 (Why is no real title available?)
- Erdős Graphs Resolve Fine's Canonicity Problem
- Atom-canonicity in varieties of cylindric algebras with applications to omitting types in multi-modal logic
- Tarskian Classical Relevant Logic
- Omitting types for finite variable fragments and complete representations of algebras
- Canonical varieties with no canonical axiomatisation
- Algebraic Logic, Where Does it Stand Today?
- The Complexity of Network Satisfaction Problems for Symmetric Relation Algebras with a Flexible Atom
- On Complete Representations and Minimal Completions in Algebraic Logic, Both Positive and Negative Results
- Comer schemes, relation algebras, and the flexible atom conjecture
- Network satisfaction problems solved by k-consistency
This page was built for publication: Strongly representable atom structures of relation algebras
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2781354)
