Back to Search
Start Over
The Thins Ordering on Relations
- Publication Year :
- 2024
-
Abstract
- Earlier papers \cite{VB2022,VB2023a,VB2023b} introduced the notions of a core and an index of a relation (an index being a special case of a core). A limited form of the axiom of choice was postulated -- specifically that all partial equivalence relations (pers) have an index -- and the consequences of adding the axiom to axiom systems for point-free reasoning were explored. In this paper, we define a partial ordering on relations, which we call the \textsf{thins} ordering. We show that our axiom of choice is equivalent to the property that core relations are the minimal elements of the \textsf{thins} ordering. We also characterise the relations that are maximal with respect to the \textsf{thins} ordering. Apart from our axiom of choice, the axiom system we employ is paired to a bare minimum and admits many models other than concrete relations -- we do not assume, for example, the existence of complements; in the case of concrete relations, the theorem is that the maximal elements of the \textsf{thins} ordering are the empty relation and the equivalence relations. This and other properties of \textsf{thins} provide further evidence that our axiom of choice is a desirable means of strengthening point-free reasoning on relations.<br />Comment: The open problem posed in the first-submitted version of this paper has been successfully resolved. As a consequence, the additional axiom is no longer required
- Subjects :
- Computer Science - Logic in Computer Science
F.3.1
F.4.1
Subjects
Details
- Database :
- arXiv
- Publication Type :
- Report
- Accession number :
- edsarx.2401.16888
- Document Type :
- Working Paper