Groups and algebras of binary relations

Bulletin of Symbolic Logic 8 (1):38-64 (2002)
  Copy   BIBTEX

Abstract

In 1941, Tarski published an abstract, finitely axiomatized version of the theory of binary relations, called the theory of relation algebras, He asked whether every model of his abstract theory could be represented as a concrete algebra of binary relations. He and Jonsson obtained some initial, positive results for special classes of abstract relation algebras. But Lyndon showed, in 1950, that in general the answer to Tarski's question is negative. Monk proved later that the answer remains negative even if one adjoins finitely many new axioms to Tarski's system. In this paper we describe a far-reaching generalization of the positive results of Jonsson and Tarski, as well as of some later, related results of Maddux. We construct a class of concrete models of Tarski's axioms-called coset relation algebras-that are very close in spirit to algebras of binary relations, but are built using systems of groups and cosets instead of elements of a base set. The models include all algebras of binary relations, and many non-representable relation algebras as well, We prove that every atomic relation algebra satisfying a certain measurability condition-a condition generalizing the conditions imposed by Jonsson and Tarski-is essentially isomorphic to a coset relation algebra. The theorem raises the possibility of providing a positive solution to Tarski's problem by using coset relation algebras instead of the standard algebras of binary relations

Other Versions

No versions found

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 103,343

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

Similar books and articles

Universal classes of simple relation algebras.Steven Givant - 1999 - Journal of Symbolic Logic 64 (2):575-589.
Undecidable semiassociative relation algebras.Roger D. Maddux - 1994 - Journal of Symbolic Logic 59 (2):398-418.
A mereotopology based on sequent algebras.Dimiter Vakarelov - 2017 - Journal of Applied Non-Classical Logics 27 (3-4):342-364.
An algebraic study of well-foundedness.Robert Goldblatt - 1985 - Studia Logica 44 (4):423 - 437.
Distributed Relation Logic.Gerard Allwein, William L. Harrison & Thomas Reynolds - 2017 - Logic and Logical Philosophy 26 (1):19-61.
Binary Relations and Permutation Groups.Hajnal Andréka & Ivo Düntsch - 1995 - Mathematical Logic Quarterly 41 (2):197-216.
Undecidability of representability as binary relations.Robin Hirsch & Marcel Jackson - 2012 - Journal of Symbolic Logic 77 (4):1211-1244.
Relation algebras of every dimension.Roger D. Maddux - 1992 - Journal of Symbolic Logic 57 (4):1213-1229.

Analytics

Added to PP
2009-01-28

Downloads
56 (#401,341)

6 months
9 (#328,796)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

A representation theorem for measurable relation algebras.Steven Givant & Hajnal Andréka - 2018 - Annals of Pure and Applied Logic 169 (11):1117-1189.
The variety of coset relation algebras.Steven Givant & Hajnal Andréka - 2018 - Journal of Symbolic Logic 83 (4):1595-1609.

Add more citations

References found in this work

On the calculus of relations.Alfred Tarski - 1941 - Journal of Symbolic Logic 6 (3):73-89.

Add more references