16 found
Sort by:
  1. Robin Hirsch & Marcel Jackson (2012). Undecidability of Representability as Binary Relations. Journal of Symbolic Logic 77 (4):1211-1244.
    In this article we establish the undecidability of representability and of finite representability as algebras of binary relations in a wide range of signatures. In particular, representability and finite representability are undecidable for Boolean monoids and lattice ordered monoids, while representability is undecidable for Jónsson's relation algebra. We also establish a number of undecidability results for representability as algebras of injective functions.
    Direct download (5 more)  
     
    My bibliography  
     
    Export citation  
  2. Robin Hirsch, Ian Hodkinson & Roger D. Maddux (2011). Weak Representations of Relation Algebras and Relational Bases. 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 (4 more)  
     
    My bibliography  
     
    Export citation  
  3. Robin Hirsch & Szabolcs Mikulás (2011). Positive Fragments of Relevance Logic and Algebras of Binary Relations. Review of Symbolic Logic 4 (1):81-105.
    We prove that algebras of binary relations whose similarity type includes intersection, union, and one of the residuals of relation composition form a nonfinitely axiomatizable quasivariety and that the equational theory is not finitely based. We apply this result to the problem of the completeness of the positive fragment of relevance logic with respect to binary relations.
    No categories
    Direct download (6 more)  
     
    My bibliography  
     
    Export citation  
  4. Robin Hirsch & Ian Hodkinson (2009). Strongly Representable Atom Structures of Cylindric Algebras. Journal of Symbolic Logic 74 (3):811-828.
    A cylindric algebra atom structure is said to be strongly representable if all atomic cylindric algebras with that atom structure are representable. This is equivalent to saying that the full complex algebra of the atom structure is a representable cylindric algebra. We show that for any finite n >3, the class of all strongly representable n-dimensional cylindric algebra atom structures is not closed under ultraproducts and is therefore not elementary. Our proof is based on the following construction. From an arbitrary (...)
    Direct download (5 more)  
     
    My bibliography  
     
    Export citation  
  5. Robin Hirsch (2007). Relation Algebra Reducts of Cylindric Algebras and Complete Representations. 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 (4 more)  
     
    My bibliography  
     
    Export citation  
  6. Robin Hirsch, Ian Hodkinson & Roger D. Maddux (2002). Provability with Finitely Many Variables. Bulletin of Symbolic Logic 8 (3):348-379.
    For every finite n ≥ 4 there is a logically valid sentence φ n with the following properties: φ n contains only 3 variables (each of which occurs many times); φ n contains exactly one nonlogical binary relation symbol (no function symbols, no constants, and no equality symbol): φ n has a proof in first-order logic with equality that contains exactly n variables, but no proof containing only n - 1 variables. This result was first proved using the machinery of (...)
    Direct download (9 more)  
     
    My bibliography  
     
    Export citation  
  7. Robin Hirsch, Ian Hodkinson & Roger D. Maddux (2002). Relation Algebra Reducts of Cylindric Algebras and an Application to Proof Theory. 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 3 variables (each of which (...)
    Direct download (6 more)  
     
    My bibliography  
     
    Export citation  
  8. Robin Hirsch & Ian Hodkinson (2001). Relation Algebras From Cylindric Algebras, I. Annals of Pure and Applied Logic 112 (2-3):225-266.
    Direct download (3 more)  
     
    My bibliography  
     
    Export citation  
  9. Robin Hirsch & Ian Hodkinson (2001). Relation Algebras From Cylindric Algebras, II. Annals of Pure and Applied Logic 112 (2-3):267-297.
    No categories
    Direct download (2 more)  
     
    My bibliography  
     
    Export citation  
  10. Robin Hirsch & Ian Hodkinson (2000). Relation Algebras with -Dimensional Relational Bases. Annals of Pure and Applied Logic 101 (2-3):227-274.
    Direct download (3 more)  
     
    My bibliography  
     
    Export citation  
  11. Robin Hirsch (1999). A Finite Relation Algebra with Undecidable Network Satisfaction Problem. Logic Journal of the Igpl 7 (4):547-554.
    Direct download  
     
    My bibliography  
     
    Export citation  
  12. Robin Hirsch & Ian Hodkinson (1999). Mosaics and Step-by-Step| Remarks onA Modal Logic of Relations' by Venema & Marx. In E. Orłowska (ed.), Logic at Work. Heidelberg.
    No categories
    Direct download  
     
    My bibliography  
     
    Export citation  
  13. Robin Hirsch, Ian Hodkinson, Maarten Marx, Szabolsc Mikulás & Mark Reynolds (1999). Mosaics and Step-by-Step. Remarks on “A Modal Logic of Relations”. In E. Orłowska (ed.), Logic at Work. Heidelberg.
    No categories
     
    My bibliography  
     
    Export citation  
  14. Robin Hirsch & Ian Hodkinson (1997). Complete Representations in Algebraic Logic. Journal of Symbolic Logic 62 (3):816-847.
    A boolean algebra is shown to be completely representable if and only if it is atomic, whereas it is shown that neither the class of completely representable relation algebras nor the class of completely representable cylindric algebras of any fixed dimension (at least 3) are elementary.
    Direct download (7 more)  
     
    My bibliography  
     
    Export citation  
  15. Robin Hirsch & Ian Hodkinson (1997). Step by Step-Building Representations in Algebraic Logic. Journal of Symbolic Logic 62 (1):225-279.
    We consider the problem of finding and classifying representations in algebraic logic. This is approached by letting two players build a representation using a game. Homogeneous and universal representations are characterized according to the outcome of certain games. The Lyndon conditions defining representable relation algebras (for the finite case) and a similar schema for cylindric algebras are derived. Finite relation algebras with homogeneous representations are characterized by first order formulas. Equivalence games are defined, and are used to establish whether an (...)
    Direct download (7 more)  
     
    My bibliography  
     
    Export citation  
  16. Robin Hirsch (1994). From Points to Intervals. Journal of Applied Non-Classical Logics 4 (1):7-27.
    Direct download (4 more)  
     
    My bibliography  
     
    Export citation