logo SBA

ETD

Archivio digitale delle tesi discusse presso l’Università di Pisa

Tesi etd-02112024-183216


Tipo di tesi
Tesi di dottorato di ricerca
Autore
DI GIORGIO, ALESSANDRO
URN
etd-02112024-183216
Titolo
Diagrammatic Algebras of Relations
Settore scientifico disciplinare
INF/01
Corso di studi
INFORMATICA
Relatori
tutor Prof. Bonchi, Filippo
Parole chiave
  • Calculus of relations
  • Category theory
  • String diagrams
Data inizio appello
16/02/2024
Consultabilità
Completa
Riassunto
The calculus of relations was introduced by De Morgan and Peirce during the second half of the 19th century. Later developments on quantification theory by Frege and Peirce himself, paved the way to what is known today as first-order logic, causing the calculus of relations to be long forgotten.

This was until 1941, when Tarski raised the question on the existence of a complete axiomatisation for it. Such question found only negative answers: there is no finite axiomatisation for the calculus of relations and many of its fragments, as shown later by several no-go theorems.

In this thesis we show that -- by moving from traditional syntax (cartesian) to a diagrammatic one (monoidal) -- it is possible to have complete axiomatisations for the full calculus and some of its fragments. The no-go theorems are circumvented by the fact that our calculi are more expressive than the calculus of relations and, actually, as expressive as (the coherent fragment and full) first-order logic.
Our axiomatisations emerge through the interplay of cartesian bicategories with other algebraic structures, giving rise to finite biproduct cartesian bicategories and first-order bicategories.
File