Roland Backhouse ; Ed Voermans - The Index and Core of a Relation. With Applications to the Axiomatics of Relation Algebra

fi:12245 - Fundamenta Informaticae, December 27, 2025, Volume 195, Issues 1-4: Relational and Algebraic Methods in Computer Science 2024 - https://doi.org/10.46298/fi.12245
The Index and Core of a Relation. With Applications to the Axiomatics of Relation AlgebraArticle

Authors: Roland Backhouse ORCID; Ed Voermans ORCID

    We introduce the general notions of an index and a core of a relation. We postulate a limited form of the axiom of choice -- specifically that all partial equivalence relations have an index -- and explore the consequences of adding the axiom to standard axiom systems for point-free reasoning. Examples of the theorems we prove are that a core/index of a difunction is a bijection, and that the so-called ``all or nothing'' axiom used to facilitate pointwise reasoning is derivable from our axiom of choice.

    Fundamenta Informaticae, Volume 195, Issue 1-4, Article 2, 2025

    https://doi.org/10.46298/fi.12245
    Source: arXiv.org:2309.02017
    Volume: Volume 195, Issues 1-4: Relational and Algebraic Methods in Computer Science 2024
    Published on: December 27, 2025
    Accepted on: May 6, 2025
    Submitted on: September 7, 2023
    Keywords: Logic in Computer Science, F.3.1; F.4.1

    Share and export