Relation Algebras Compatible with $\mathbb{Z}_2$-sets

We provide a characterization of those relation algebras which are isomorphic to the algebras of compatible relations of some $\Z_2$-set. We further prove that this class is finitely axiomatizable in first-order logic in the language of relation algebras.

Logic, Reasoning, and Knowledge Advanced Algebra and Logic Formal Methods in Verification

Source

Paper

Similar papers

Permutations, substitutions and finite axiomatizabilityHajnal Andréka, Zalán Gyenis, Istvàn Németi2025 · arXiv (Cornell University) In Library

Representable and diagonally representable weakening relation algebrasPeter Jipsen, Jaš Šemrl2023 · arXiv (Cornell University) In Library

Some results on relation algebra reducts: Residuated and semilattice-ordered semigroupsDaniel Rogozin2022 · Journal of Logic and Computation In Library

Non-Axiomatizability of the Equational Theories of Positive Relation Algebras (Invited Talk)Amina Doumane2021 · DROPS (Schloss Dagstuhl – Leibniz Center for Informatics) In Library

FIRST-ORDER AXIOMATISATIONS OF REPRESENTABLE RELATION ALGEBRAS NEED FORMULAS OF UNBOUNDED QUANTIFIER DEPTHRob Egrot, Robin Hirsch2021 · Journal of Symbolic Logic In Library

The Algebras for Automatic RelationsRémi Morvan2024 · arXiv (Cornell University) In Library

Algebraic Reasoning over Relational StructuresJan Jurka, Stefan Milius, Henning Urbat2024 · Electronic Notes in Theoretical Informatics and Computer Science In Library

First-order axiomatisations of representable relation algebras need\n formulas of unbounded quantifier depthRob Egrot, Robin Hirsch2020 · arXiv (Cornell University) In Library

Implication Algebras and Implication Semigroups of Binary RelationsAndrew Lewis-Smith Jaš Šemrl2023 · arXiv (Cornell University) In Library

Substitutions of variables are finitely axiomatizable over quantifications and permutationsHajnal Andréka, Zalán Gyenis, Istvàn Németi2025 · arXiv (Cornell University) In Library

Patents near this paper

SYSTEMS AND METHODS FOR DATA STORAGE AND RETRIEVAL USING ALGEBRAIC OPTIMIZATIONUS 7,769,754 · XSPRADA CORPORATION · 2010 SYSTEMS AND METHODS FOR PROVIDING DATA SETS USING A STORE OF ALBEGRAIC RELATIONSUS 7,613,734 · XSPRADA CORPORATION · 2009 METHOD FOR PERFORMING A DISJUNCTIVE PROOF FOR TWO RELATIONSUS 11,496,309 · INTERNATIONAL BUSINESS MACHINES CORPORATION · 2022 MAPPING COMPOSITION USING ALGEBRAIC OPERATORSUS 7,539,663 · MICROSOFT CORPORATION · 2009 POLICY ALGEBRA AND COMPATIBILITY MODELUS 7,584,499 · MICROSOFT CORPORATION · 2009

Source of record

OpenAlex