Results for 'Relation algebras'

1000+ found
Order:
  1.  6
    Weakly Associative Relation Algebras with Projections.Agi Kurucz - 2009 - Mathematical Logic Quarterly 55 (2):138-153.
    Built on the foundations laid by Peirce, Schröder, and others in the 19th century, the modern development of relation algebras started with the work of Tarski and his colleagues [21, 22]. They showed that relation algebras can capture strong first-order theories like ZFC, and so their equational theory is undecidable. The less expressive class WA of weakly associative relation algebras was introduced by Maddux [7]. Németi [16] showed that WA's have a decidable universal theory. (...)
    Direct download (4 more)  
     
    Export citation  
     
    My bibliography   3 citations  
  2.  3
    A Simple Construction of Representable Relation Algebras with Non‐Representable Completions.Tarek Sayed Ahmed - 2009 - Mathematical Logic Quarterly 55 (3):237-244.
    We give a simple new construction of representable relation algebras with non-representable completions. Using variations on our construction, we show that the elementary closure of the class of completely representable relation algebras is not finitely axiomatizable.
    Direct download (3 more)  
     
    Export citation  
     
    My bibliography  
  3.  10
    Relation Algebras of Every Dimension.Roger D. Maddux - 1992 - Journal of Symbolic Logic 57 (4):1213-1229.
    Conjecture (1) of [Ma83] is confirmed here by the following result: if $3 \leq \alpha < \omega$, then there is a finite relation algebra of dimension α, which is not a relation algebra of dimension α + 1. A logical consequence of this theorem is that for every finite α ≥ 3 there is a formula of the form $S \subseteq T$ (asserting that one binary relation is included in another), which is provable with α + 1 (...)
    Direct download (8 more)  
     
    Export citation  
     
    My bibliography   5 citations  
  4.  12
    Atom Structures of Cylindric Algebras and Relation Algebras.Ian Hodkinson - 1997 - Annals of Pure and Applied Logic 89 (2):117-148.
    For any finite n 3 there are two atomic n-dimensional cylindric algebras with the same atom structure, with one representable, the other, not.Hence, the complex algebra of the atom structure of a representable atomic cylindric algebra is not always representable, so that the class RCAn of representable n-dimensional cylindric algebras is not closed under completions. Further, it follows by an argument of Venema that RCAn is not axiomatisable by Sahlqvist equations, and hence nor by equations where negation can (...)
    Direct download (3 more)  
     
    Export citation  
     
    My bibliography   9 citations  
  5.  96
    Relevance Logics and Relation Algebras.Katalin Bimbó, J. Michael Dunn & Roger D. Maddux - 2009 - Review of Symbolic Logic 2 (1):102-131.
    Relevance logics are known to be sound and complete for relational semantics with a ternary accessibility relation. This paper investigates the problem of adequacy with respect to special kinds of dynamic semantics (i.e., proper relation algebras and relevant families of relations). We prove several soundness results here. We also prove the completeness of a certain positive fragment of R as well as of the first-degree fragment of relevance logics. These results show that some core ideas are shared (...)
    Direct download (7 more)  
     
    Export citation  
     
    My bibliography   3 citations  
  6.  10
    Nonfinite Axiomatizability Results for Cylindric and Relation Algebras.Roger D. Maddux - 1989 - Journal of Symbolic Logic 54 (3):951-974.
    The set of equations which use only one variable and hold in all representable relation algebras cannot be derived from any finite set of equations true in all representable relation algebras. Similar results hold for cylindric algebras and for logic with finitely many variables. The main tools are a construction of nonrepresentable one-generated relation algebras, a method for obtaining cylindric algebras from relation algebras, and the use of relation (...) in defining algebraic semantics for first-order logic. (shrink)
    Direct download (7 more)  
     
    Export citation  
     
    My bibliography   10 citations  
  7.  57
    The Origin of Relation Algebras in the Development and Axiomatization of the Calculus of Relations.Roger D. Maddux - 1991 - Studia Logica 50 (3-4):421 - 455.
    The calculus of relations was created and developed in the second half of the nineteenth century by Augustus De Morgan, Charles Sanders Peirce, and Ernst Schröder. In 1940 Alfred Tarski proposed an axiomatization for a large part of the calculus of relations. In the next decade Tarski's axiomatization led to the creation of the theory of relation algebras, and was shown to be incomplete by Roger Lyndon's discovery of nonrepresentable relation algebras. This paper introduces the calculus (...)
    Direct download (5 more)  
     
    Export citation  
     
    My bibliography   7 citations  
  8.  2
    Relation Algebras From Cylindric and Polyadic Algebras.I. Nemeti & A. Simon - 1997 - Logic Journal of the IGPL 5 (4):575-588.
    This paper is a survey of recent results concerning connections between relation algebras , cylindric algebras and polyadic equality algebras . We describe exactly which subsets of the standard axioms for RA are needed for axiomatizing RA over the RA-reducts of CA3's, and we do the same for the class SA of semi-associative relation algebras. We also characterize the class of RA-reducts of PEA3's. We investigate the interconnections between the RA-axioms within CA3 in more (...)
    Direct download  
     
    Export citation  
     
    My bibliography   7 citations  
  9.  37
    A Proof System for Contact Relation Algebras.Ivo Düntsch & Ewa Orłowska - 2000 - Journal of Philosophical Logic 29 (3):241-262.
    Contact relations have been studied in the context of qualitative geometry and physics since the early 1920s, and have recently received attention in qualitative spatial reasoning. In this paper, we present a sound and complete proof system in the style of Rasiowa and Sikorski (1963) for relation algebras generated by a contact relation.
    Direct download (9 more)  
     
    Export citation  
     
    My bibliography   5 citations  
  10.  6
    Relation Algebras with N-Dimensional Relational Bases.Robin Hirsch & Ian Hodkinson - 2000 - Annals of Pure and Applied Logic 101 (2-3):227-274.
    We study relation algebras with n-dimensional relational bases in the sense of Maddux. Fix n with 3nω. Write Bn for the class of non-associative algebras with an n-dimensional relational basis, and RAn for the variety generated by Bn. We define a notion of relativised representation for algebras in RAn, and use it to give an explicit equational axiomatisation of RAn, and to reprove Maddux's result that RAn is canonical. We show that the algebras in Bn (...))
    Direct download (3 more)  
     
    Export citation  
     
    My bibliography   5 citations  
  11.  47
    Weak Representations of Relation Algebras and Relational Bases.Robin Hirsch, Ian Hodkinson & Roger D. Maddux - 2011 - Journal of Symbolic Logic 76 (3):870 - 882.
    It is known that for all finite n ≥ 5, there are relation algebras with n-dimensional relational bases but no weak representations. We prove that conversely, there are finite weakly representable relation algebras with no n-dimensional relational bases. In symbols: neither of the classes RA n and wRRA contains the other.
    Direct download (6 more)  
     
    Export citation  
     
    My bibliography  
  12.  19
    The Lattice of Varieties of Representable Relation Algebras.Hajnal Andréka, Steven Givant & István Németi - 1994 - Journal of Symbolic Logic 59 (2):631-661.
    We shall show that certain natural and interesting intervals in the lattice of varieties of representable relation algebras embed the lattice of all subsets of the natural numbers, and therefore must have a very complicated lattice-theoretic structure.
    Direct download (7 more)  
     
    Export citation  
     
    My bibliography   2 citations  
  13.  23
    Finite, Integral, and Finite-Dimensional Relation Algebras: A Brief History.Roger D. Maddux - 2004 - Annals of Pure and Applied Logic 127 (1-3):117-130.
    Relation algebras were invented by Tarski and his collaborators in the middle of the 20th century. The concept of integrality arose naturally early in the history of the subject, as did various constructions of finite integral relation algebras. Later the concept of finite-dimensionality was introduced for classifying nonrepresentable relation algebras. This concept is closely connected to the number of variables used in proofs in first-order logic. Some results on these topics are presented in chronological (...)
    Direct download (3 more)  
     
    Export citation  
     
    My bibliography  
  14.  16
    Łukasiewicz-Moisil Relation Algebras.Andrei Popescu - 2005 - Studia Logica 81 (2):167-189.
    We introduce Łukasiewicz-Moisil relation algebras, obtained by considering a relational dimension over Łukasiewicz-Moisil algebras. We prove some arithmetical properties, provide a characterization in terms of complex algebras, study the connection with relational Post algebras and characterize the simple structures and the matrix relation algebras.
    Direct download (5 more)  
     
    Export citation  
     
    My bibliography  
  15.  12
    Undecidable Semiassociative Relation Algebras.Roger D. Maddux - 1994 - Journal of Symbolic Logic 59 (2):398-418.
    If K is a class of semiassociative relation algebras and K contains the relation algebra of all binary relations on a denumerable set, then the word problem for the free algebra over K on one generator is unsolvable. This result implies that the set of sentences which are provable in the formalism Lwx is an undecidable theory. A stronger algebraic result shows that the set of logically valid sentences in Lwx forms a hereditarily undecidable theory in Lwx. (...)
    Direct download (8 more)  
     
    Export citation  
     
    My bibliography   1 citation  
  16.  33
    Weakly Associative Relation Algebras with Polyadic Composition Operations.Vera Stebletsova - 2000 - Studia Logica 66 (2):297-323.
    In this paper we introduced various classes of weakly associative relation algebras with polyadic composition operations. Among them is the class RWA of representable weakly associative relation algebras with polyadic composition operations. Algebras of this class are relativized representable relation algebras augmented with an infinite set of operations of increasing arity which are generalizations of the binary relative composition. We show that RWA is a canonical variety whose equational theory is decidable.
    Direct download (7 more)  
     
    Export citation  
     
    My bibliography  
  17.  5
    Representations for Small Relation Algebras.Hajnal Andréka & Roger D. Maddux - 1994 - Notre Dame Journal of Formal Logic 35 (4):550-562.
    There are eighteen isomorphism types of finite relation algebras with eight or fewer elements, and all of them are representable. We determine all the cardinalities of sets on which these algebras have representations.
    Direct download  
     
    Export citation  
     
    My bibliography   1 citation  
  18.  12
    On Canonicity and Completions of Weakly Representable Relation Algebras.Ian Hodkinson & Szabolcs Mikulás - 2012 - Journal of Symbolic Logic 77 (1):245-262.
    We show that the variety of weakly representable relation algebras is neither canonical nor closed under Monk completions.
    Direct download (7 more)  
     
    Export citation  
     
    My bibliography  
  19.  20
    Inequivalent Representations of Geometric Relation Algebras.Steven Givant - 2003 - Journal of Symbolic Logic 68 (1):267-310.
    It is shown that the automorphism group of a relation algebra ${\cal B}_P$ constructed from a projective geometry P is isomorphic to the collineation group of P. Also, the base automorphism group of a representation of ${\cal B}_P$ over an affine geometry D is isomorphic to the quotient of the collineation group of D by the dilatation subgroup. Consequently, the total number of inequivalent representations of ${\cal B}_P$ , for finite geometries P, is the sum of the numbers ${\mid (...)
    Direct download (8 more)  
     
    Export citation  
     
    My bibliography  
  20.  2
    A Simple Construction of Representable Relation Algebras with Non-Representable Completions.Tarek Sayed Ahmed - 2009 - Mathematical Logic Quarterly 55 (3):237-244.
    We give a simple new construction of representable relation algebras with non-representable completions. Using variations on our construction, we show that the elementary closure of the class of completely representable relation algebras is not finitely axiomatizable.
    Direct download (2 more)  
     
    Export citation  
     
    My bibliography  
  21.  10
    Relation Algebras From Cylindric Algebras, I.Robin Hirsch & Ian Hodkinson - 2001 - Annals of Pure and Applied Logic 112 (2-3):225-266.
    We characterise the class S Ra CA n of subalgebras of relation algebra reducts of n -dimensional cylindric algebras by the notion of a ‘hyperbasis’, analogous to the cylindric basis of Maddux, and by representations. We outline a game–theoretic approximation to the existence of a representation, and how to use it to obtain a recursive axiomatisation of S Ra CA n.
    Direct download (3 more)  
     
    Export citation  
     
    My bibliography   4 citations  
  22.  14
    Lower Level Connections Between Representations of Relation Algebras.György Serény - 1986 - Bulletin of the Section of Logic 15 (3):123-125.
    The algebra of all binary relations on a given set is the most important example of a relation algebra . In this note we will examine the possible isomorphisms within some subclasses of a closely related class ; A is a relation set algebra with base U if its Boolean reduct is a field of sets with unit element 2 U, its universe A contains the identity relation on U and it is closed under the operations −1 (...)
    Direct download  
     
    Export citation  
     
    My bibliography  
  23.  5
    A Representation Theorem for Measurable Relation Algebras.Steven Givant & Hajnal Andréka - forthcoming - Annals of Pure and Applied Logic.
    Direct download (2 more)  
     
    Export citation  
     
    My bibliography  
  24. Relation Algebra Reducts of Cylindric Algebras and an Application to Proof Theory.Robin Hirsch, Ian Hodkinson & Roger D. Maddux - 2002 - Journal of Symbolic Logic 67 (1):197-213.
    We confirm a conjecture, about neat embeddings of cylindric algebras, made in 1969 by J. D. Monk, and a later conjecture by Maddux about relation algebras obtained from cylindric algebras. These results in algebraic logic have the following consequence for predicate logic: for every finite cardinal α ≥ 3 there is a logically valid sentence X, in a first-order language L with equality and exactly one nonlogical binary relation symbol E, such that X contains only (...)
    Direct download (7 more)  
     
    Export citation  
     
    My bibliography   6 citations  
  25.  9
    A Sequent Calculus for Relation Algebras.Roger Maddux - 1983 - Annals of Pure and Applied Logic 25 (1):73-101.
    Direct download (2 more)  
     
    Export citation  
     
    My bibliography   14 citations  
  26.  9
    Weakly Associative Relation Algebras Hold the Key to the Universe.Tomasz Kowalski - 2007 - Bulletin of the Section of Logic 36 (3/4):145-157.
  27.  7
    Relation Algebras From Cylindric Algebras, II.Robin Hirsch & Ian Hodkinson - 2001 - Annals of Pure and Applied Logic 112 (2-3):267-297.
    We prove, for each 4⩽ n ω , that S Ra CA n+1 cannot be defined, using only finitely many first-order axioms, relative to S Ra CA n . The construction also shows that for 5⩽n S Ra CA n is not finitely axiomatisable over RA n , and that for 3⩽m S Nr m CA n+1 is not finitely axiomatisable over S Nr m CA n . In consequence, for a certain standard n -variable first-order proof system ⊢ m (...)
    Direct download (2 more)  
     
    Export citation  
     
    My bibliography   4 citations  
  28.  12
    Distributive and Modular Laws in the Arithmetic of Relation Algebras.Louise H. Chin & Alfred Tarski - 1953 - Journal of Symbolic Logic 18 (1):72-72.
  29.  23
    Lyndon R. C.. Relation Algebras and Projective Geometry. The Michigan Mathematical Journal, Vol. 8 , Pp. 21–28.Thomas Frayne - 1967 - Journal of Symbolic Logic 32 (2):275-276.
    Direct download (3 more)  
     
    Export citation  
     
    My bibliography  
  30. Elimination of Quantifiers in the Semantics of Natural Language by Use of Extended Relation Algebras.Patrick Suppes - 1976 - Revue Internationale de Philosophie 30 (3/4=117/118):243-259.
     
    Export citation  
     
    My bibliography   5 citations  
  31.  17
    Lyndon Roger C.. The Representation of Relation Algebras, II. Annals of Mathematics, Ser. 2 Vol. 63 , Pp. 294–307.J. Donald Monk - 1974 - Journal of Symbolic Logic 39 (2):337.
  32.  18
    Review: Donald Monk, On Representable Relation Algebras[REVIEW]Thomas Frayne - 1966 - Journal of Symbolic Logic 31 (3):508-508.
  33.  5
    Axiomatising Various Classes of Relation and Cylindric Algebras.Robin Hirsch & Ian Hodkinson - 1997 - Logic Journal of the IGPL 5 (2):209-229.
    We outline a simple approach to axiomatising the class of representable relation algebras, using games. We discuss generalisations of the method to cylindric algebras, homogeneous and complete representations, and atom structures of relation algebras.
    Direct download (2 more)  
     
    Export citation  
     
    My bibliography   1 citation  
  34.  20
    Review: Roger C. Lyndon, The Representation of Relation Algebras, II. [REVIEW]J. Donald Monk - 1974 - Journal of Symbolic Logic 39 (2):337-337.
  35.  20
    Review: R. C. Lyndon, Relation Algebras and Projective Geometry. [REVIEW]Thomas Frayne - 1967 - Journal of Symbolic Logic 32 (2):275-276.
  36. REVIEWS-Relation Algebras by Games.R. Hirsh, I. Hodkinson & Roger D. Maddux - 2003 - Bulletin of Symbolic Logic 9 (4):515-519.
     
    Export citation  
     
    My bibliography   1 citation  
  37.  7
    Universal Classes of Simple Relation Algebras.Steven Givant - 1999 - Journal of Symbolic Logic 64 (2):575-589.
  38.  13
    Monk Donald. On Representable Relation Algebras. The Michigan Mathematical Journal, Vol. 11 (1964), Pp. 207–210.Thomas Frayne - 1996 - Journal of Symbolic Logic 31 (3):508-508.
  39.  13
    Review: Frank Harary, On Complete Atomic Proper Relation Algebras[REVIEW]R. C. Lyndon - 1951 - Journal of Symbolic Logic 16 (1):74-74.
  40.  9
    On Complete Atomic Proper Relation Algebras.Frank Harary - 1950 - Journal of Symbolic Logic 15 (3):197-198.
  41.  6
    Harary Frank. On Complete Atomic Proper Relation Algebras.R. C. Lyndon - 1951 - Journal of Symbolic Logic 16 (1):74.
  42.  8
    Representations for Small Relation Algebras.Hajnal Andr Eka & Roger D. Maddux - 1994 - Notre Dame Journal of Formal Logic 35 (4).
  43.  3
    An Undecidability Result for Relation Algebras.Wolfgang Schönfeld - 1979 - Journal of Symbolic Logic 44 (1):111-115.
  44.  2
    Two Axiom Systems for Relation Algebras.Chris Brink - 1979 - Notre Dame Journal of Formal Logic 20 (4):909-914.
  45.  3
    Amalgamation in Relation Algebras.Maarten Marx - 1998 - Journal of Symbolic Logic 63 (2):479-484.
    Direct download  
     
    Export citation  
     
    My bibliography  
  46. Review: Alfred Tarski, Equationally Complete Rings and Relation Algebras[REVIEW]Jerzy Los - 1958 - Journal of Symbolic Logic 23 (1):57-57.
  47.  10
    Relation Algebra Reducts of Cylindric Algebras and Complete Representations.Robin Hirsch - 2007 - Journal of Symbolic Logic 72 (2):673 - 703.
    We show, for any ordinal γ ≥ 3, that the class RaCAγ is pseudo-elementary and has a recursively enumerable elementary theory. ScK denotes the class of strong subalgebras of members of the class K. We devise games, Fⁿ (3 ≤ n ≤ ω), G, H, and show, for an atomic relation algebra A with countably many atoms, that Ǝ has a winning strategy in Fω(At(A)) ⇔ A ∈ ScRaCAω, Ǝ has a winning strategy in Fⁿ(At(A)) ⇐ A ∈ ScRaCAn, (...)
    Direct download (5 more)  
     
    Export citation  
     
    My bibliography  
  48.  3
    REVIEWS-Decision Problems for Equational Theories of Relation Algebras.H. Andreka, S. Givant, I. Nemeti & Roger D. Maddux - 2003 - Bulletin of Symbolic Logic 9 (1):37-38.
  49.  5
    Amalgamation in Relation Algebras.Maarten Marx - 1998 - Journal of Symbolic Logic 63 (2):479-484.
  50. Equationally Complete Rings and Relation Algebras.Alfred Tarski - 1958 - Journal of Symbolic Logic 23 (1):57-57.
1 — 50 / 1000