CS Paper Radar

A Catalogue of Properties of Binary Relations: Entailments, Incompatibilities, and Independence Results

Magnus Boman

cs.LO math.LO ·submitted 2026-09-10 18:41 UTC · v1

Abstract

We study fifteen properties of binary relations that have established uses in modal logic, order and preference theory, and relation algebra. The organising question is pragmatic: once some properties of a relation are known, which further properties follow, which combinations force degeneracy, and which properties remain independent? We give a proved Horn basis of elementary and compound entailments, explicit countermodels for non-entailments, and a relation-algebraic translation of all fifteen properties. The modal discussion includes the usual Scott--Lemmon correspondences and the logic of transitive dense frames studied by Ghilardi and Mints. Exhaustive finite enumeration and targeted model search are used for discovery, while the catalogue is certified in Lean. A kernel-checked coverage calculation ranges over all 2^15 = 32,768 antecedent sets and all fifteen possible consequents. Its 51-rule Horn manifest is coupled definitionally to Lean proofs of semantic soundness, and its 49 witness rows are coupled definitionally to Lean-certified finite or infinite relations. Consequently, over non-empty domains, the Horn closure is complete for positive entailment among the fifteen selected properties, and the consistency classification is complete for their positive combinations.

Comment
17 pages, 1 figure, 1 table

Closest papers

Nearest neighbours by meaning across the whole index.

A minimal intuitionistic public announcement logic

cs.LO ·2026-11-10 ·Philippe Balbiani, Hans van Ditmarsch, Cigdem Gencer, Clara Lerouvillois
similarity 0.66
Abstract

We introduce intuitionistic public announcement logics Lmin and Lequ determined by classes of birelational frames where the intuitionistic preorder and the modal accessibility relation do not need to satisfy the confluence conditions traditionally considered within the framework of IPAL. Our logics can be seen as generalisations of IPAL seeing that their language is based on a binary epistemic modality of "relativised knowledge" that allows us to define valid reduction axioms. Our main results are the soundness and completeness of Lmin with respect to the class of all birelational frames and the soundness and completeness of Lequ with respect to the class of all birelational frames where the modal accessibility relation is an equivalence relation.

0.24

Two-Variable Logic with Arbitrarily Many Successor Relations

cs.LO ·2026-10-07 ·Jakub Michaliszyn, Piotr Witkowski
theory similarity 0.63
Abstract

We study two-variable first-order logic with a finite, input-dependent number of distinguished successor relations and arbitrary additional unary and binary predicates. Each distinguished relation must be the exact immediate-successor relation of some linear order on the common domain; the orders themselves are not available in the language and may have arbitrary order types. We prove that satisfiability belongs to 2NEXPTIME, uniformly in the number of successors. The proof gives finite certificates for possibly infinite models. A closure operation separates local neighbourhood descriptions, called star types, into those of bounded multiplicity and those that can be realized infinitely often. The bounded part is represented explicitly. Outside it, integer height vectors allow overlapping successor requirements to be matched without creating cycles or unintended identifications. Ordering the resulting path components densely then recovers exact successor relations. Consistent assignments of the additional binary predicates handle witnesses involving the bounded part. The same certificates decide infinite satisfiability in 2NEXPTIME and give a doubly exponential threshold above which a finite model guarantees an infinite model. A doubly exponentially large finite core can be forced with only two successors and unary predicates. For finite models, we prove that satisfiability subject to a bound on the total number of reference adjacencies lost by the other orders is NEXPTIME-complete, even when the budget is encoded in binary and the number of successors is part of the input.

0.49

Decidability of Elementary Modal Logics is Undecidable

cs.LO ·2026-11-08 ·Jakub Michaliszyn
theory similarity 0.62
Abstract

We study the decidability of modal satisfiability over classes of Kripke frames defined by universal first-order sentences. Although some such classes yield undecidable satisfiability problems, decidability is guaranteed for wide families of frame conditions, including universal Horn sentences and universal sentences implying transitivity. A more than decade-old open problem asks a natural question: can decidable and undecidable cases be distinguished algorithmically? We prove that this is impossible, already for equality-free universal frame conditions over a single binary relation. More precisely, there is no algorithm that, given such a condition, decides whether its associated local modal satisfiability problem is decidable. We first establish the result for conditions with equality and then eliminate equality by passing to quotients of worlds with identical incoming and outgoing edges.

0.16

Look Here or Look Across: Unified Cardinality Constraints for N-ary Relationships

cs.DB ·2026-10-01 ·Huanyi Chen
similarity 0.62
Abstract · 16 pages, 8 figures

A cardinality constraint written on an edge of an entity-relationship diagram admits two opposite readings. Under the reading used by UML and by Chen's original model, the label is read with the entity set on the same side of the relationship; under the reading used by standard database textbooks, it is read with the entity set on the opposite side. The two readings are exact opposites, so a reader who assumes the wrong one takes away the opposite of what the designer meant. For binary relationships the difficulty is confined to interpretation, because the two constraints a binary relationship set admits can both be drawn. For relationships among three or more entity sets the picture is worse: a ternary relationship set admits twelve cardinality constraints, and a diagram with three edges can carry at most three of them. This paper presents a notation, Card(R; p; q) = (lower, upper), that removes the ambiguity without taking a side in it, and that is not limited to one constraint per edge. We give the number of constraints an n-ary relationship set admits, show which of them a design determines without ever writing them down, and state two inference rules, decomposition and augmentation, that derive one constraint from another, together with the side conditions under which each is sound. We close with a worked case study that turns three business requirements into three explicit constraints and nine more that the design decides on its own.

0.26

Merging and Evolution of Data Bases: A Many-Logic Approach

cs.LO cs.DB ·2026-10-29 ·Manuel A. Martins, Abilio Rodrigues
published similarity 0.61
Abstract · In Proceedings NCL'26, arXiv:2610.34489

A new approach to information-based logics using many-logic modal structures (MLMSs) was recently proposed by Martins et al. In such a setting, it is possible to have worlds with different underlying logics within the same frame, all anchored to a base lattice that contains the semantics of each logic as a down-complete sublattice. In this paper, we take the lattice L6, defined by the six-valued semantics of the logic of evidence and truth LET + K , as our base lattice. We also consider four-, three-, and two-valued formal systems associated with down-complete sublattices of L6. These logics are capable of representing paracomplete, paraconsistent, and classical contexts with six, four, three, and two informational scenarios, respectively. As applications of MLMSs, we will discuss the merging and temporal evolution of databases whose underlying logics are two-, three-, four-, and six-valued. We will also investigate inconsistency measures in this context.

0.47

Finite Dependence and Invariance Hierarchies for Finitely Supported Structures

cs.LO math.CTmath.LO ·2026-09-14 ·Gabriel Ciobanu
similarity 0.61
Abstract · 44 pages, 2 tables, no figures. Unified synthesis of finite-dependence profiles, invariance hierarchies, freshness, context composition, orb…

Finite support indicates that the dependence is limited, but not how each finite context controls what can be observed. For a data symmetry G \leq Sym(A) and a finitely supported G-set X, we study the finite-dependence profile X^S = {x : Fix_G(S) fixes x}, indexed by finite contexts S \subseteq A. For relations on A^n this yields Boolean algebras B^{(n)}_{G,S} = Inv_n(Fix_G(S)), forming the invariance hierarchy. The hierarchy separates several nominal principles. Its meet law is the relation-algebra form of the Bojanczyk-Klin-Lasota least-support criterion, while level injectivity is fungibility. The independent join law governs composition across unions of contexts; it holds for locally oligomorphic automorphism groups of ultrahomogeneous structures in purely relational languages of arity at most two, but can fail for unary observations over ternary data. Freshness remains valid sort by sort, and its unrestricted some/any form characterizes full equality symmetry among closed groups. With least supports, orbit-finiteness implies finite context levels and a uniform support bound; under local oligomorphicity the converse also holds. Pointwise closure does not change the profile, and standard atomic-site presentations show that suitable ultrahomogeneous structures with the same age have equivalent action topoi, even though their material FSS universes may retain different external cardinal data. Contextual orientability gives a complementary pointed invariant whose threshold is the least support size of choice from unordered pairs. For countable omega-categorical structures with degenerate algebraic closure, the meet law is equivalent to weak elimination of imaginaries.

0.48

Weighted First-Order Model Counting over Ordered Domains

cs.LO ·2026-08-11 ·Jan Tóth, Qipeng Kuang, Kuncheng Zou, Václav Kůla, Yuyi Wang +2 more
similarity 0.61
Abstract · Submitted to JAIR

The Weighted First-Order Model Counting Problem (WFOMC) asks for the weighted sum of models of a first-order logical sentence over a domain. It is a fundamental problem in statistical relational learning, with applications extending to enumerative combinatorics and graph polynomials. Computing WFOMC for the three-variable fragment is $\mathsf{\#P}_1$-hard, whereas polynomial-time algorithms exist for the two-variable fragment and its extensions by cardinality constraints and counting quantifiers. In this work, we explore computing WFOMC in polynomial time over linearly ordered domains, enabling tractable reasoning across inference scenarios and combinatorial problems involving sequences. Because encoding a linear order in standard first-order logic requires three variables, negating our polynomial-time aspirations, we add a linear order axiom directly to the language. This forces one predicate to impose a total ordering on domain elements. We first prove that WFOMC with the linear order axiom can be solved in time polynomial in the domain size. We then extend this result to ordered domains with access to successor relations. While this holds when successors are explicitly defined via the linear order, we demonstrate an alternative implicit approach where successor relations are part of the axiom. This implicit method exhibits significantly better performance on all tested instances, sometimes providing exponential runtime improvements. Finally, we analyze scenarios with two distinct linear orders. We show that WFOMC over the two-variable fragment with two linear orders is $\mathsf{\#P}_1$-hard. However, we develop a polynomial-time algorithm for WFOMC with one linear order and a successor relation of another, pushing the intractability barrier further, yet still leaving the question of how close to a second full linear order one can get.

0.35

Modal Extensions of Generalised Nelson Logics

cs.LO ·2026-10-07 ·Igor Sedlár, Pietro Vigiani
similarity 0.61
Abstract

Motivated by relevant epistemic logic, we extend Dunn's simple Kripke-style binary relational semantics for the semi-relevant logic RM to fit a modal extension of RM. It is shown that the modal axioms and rules that need to be added to RM to obtain a sound and complete axiomatisation of its modal extension give an axiomatisation of modal extensions of all logics in the family of generalised Nelson logics, also studied by Dunn.

0.31