Lorenzo Rossi

PLEXUS Workshop on Substructural and Non-Classical Logics

Description

The workshop aims at bringing together philosophers, computer scientists, and mathematicians working on substructural, many-valued, and more generally non-classical logics.

Practical Info

Dates: June 27 and 28, 2024

Venue: Sala Lauree, Complesso Aldo Moro, Via Giuseppe Verdi, 10123 Torino

Speakers:

Program:

June 27:

  • 9:00 – 12:30 PLEXUS Meeting
  • 12:30- 14:00 Lunch break
  • 14:00 – 15:00 Alessandra Palmigiano: Non-distributive logics: from semantics to meaning
  • 15:00 – 15:30 Damian Szmuc: Non-deterministic matrices for semi-cocanonical deduction systems
  • 15:30 – 16:15 Coffee break
  • 16:15 – 16:45 Agustina Borzi: A Substructural Approach to Content Inclusion
  • 16:45 – 17:15 Peter Verdeé: A reason-based hyperintensional semantics for substructural logics without weakening
  • 17:15 – 18:15 Guillermo Badia: Logic, Databases and Semirings

June 28:

  • 9:30 – 10:30 George Metcalfe: Substructural logics with minimally true tautologies
  • 10:30 – 11:00 Paolo Baldi: KE-style tableaux for Intuitionistic Propositional Logic
  • 11:00 – 12:00 Coffee break
  • 12:00 – 13:00 Matteo Tesi: Ways to infinity in structural proof theory
  • 13:00- 14:30 Lunch break
  • 14:30 – 15:00 Javier Viñeta García, Isabel Grábalos, Martina Zirattu: On a Generalization of all Strong Kleene Generalizations of Classical Logic
  • 15:00 – 16:00 Guendalina Righetti: Combining Concepts: Integrating Logical and Cognitive Theories of Concepts
  • 16:00 – 16:45 Coffee break
  • 16:45 – 17:15: Quentin Blomet: Tarskian Closure and its Dual
  • 17:15 – 18:15 Elia Zardini: Paradox and Substructurality

Schedule of the PLEXUS Meeting:

  • 9:00-9:15 Welcome
  • 9:15-9:30 Introduction: Project Officer (Aleksandra Schoetz-Sobczak) & Project Coordinator (Pablo Cobreros)
  • 9:30-9:45: Scientific Progress. Work Package 1 (Paul Egré)
  • 9:45-10:00: Scientific Progress. Work Package 2 (Lorenzo Rossi)
  • 10:00-10:15 Scientific Progress. Work Package 3 (Pablo Cobreros)
  • 10:15-10:30 Implementation of secondments; training and networking activities; publications (Pablo Cobreros)
  • 10:30-11:00: Coffee break
  • 11:00-11:15: Work Package 4: Dissemination and Communication, Work Package 5: Management (Pablo Cobreros)
  • 11:15-12:00: Meeting Seconded Staff (all available secondees, and the Project Officer)
  • 12:00-12:30: Feedback, questions, any other business and close of meeting

Titles and abstracts:

Guillermo Badia (Queensland): Logic, Databases and Semirings

(joint work with Phokion Kolaitis and Carles Noguera)

There are typically two kinds of formal languages that are used to query data: "procedural" languages where we are told how to construct the set of tuples that satisfy a certain property, and "declarative" languages where we define such set by means of a property that we can write in the formal language.  The most prominent example of the first is known as "relational algebra" which consists of a group of operations to build relations, whereas the most prominent example of declarative languages is relational calculus (aka first-order logic).  Codd's theorem is a fundamental result in the database literature showing the equivalence between relational algebra, calculus with the active domain interpretation and domain independent calculus.
 
Commercial query languages, such as SQL, use bag semantics, instead of set semantics, to evaluate relational database queries, which means that the semiring of the natural numbers is used to annotate tuples in the input and output relations.  Thus in recent years, there has been an ever growing body of work studying database theory in the context of semiring annotated databases.  In this talk we make some proposals for query languages that generalize relational algebra and calculus to databases annotated by semirings with certain properties.  In this case the expressions of relational algebra and calculus must be given a semantics on these semirings, and things begin to connect with algebraic logic.  In particular, we make a proposal on how to interpret expressions involving negation or set theoretic difference as well as universal quantification and the operation of division from relational algebra.  Our central result is a very general version of Codd's theorem applying to a large class of semirings.

Paolo Baldi (Salento): KE-style tableaux for Intuitionistic Propositional Logic

(joint work with Ricardo O. Rodriguez and Alejandro Solares-Rojas)

We generalize to intuitionistic propositional logic (IPL) the system KE, which is a variant of tableaux but essentially more efficient. The generalization is made possible by the expressive power of labels, and the resulting system closely mimics countermodel construction in the relational semantics. We further endow our system with free-variables to improve on proof-search, and  show its basic properties: soundness, completeness and termination. Finally, we provide ideas towards the development of tractable approximations of IPL on the basis of our system.

Quentin Blomet (Paris): Tarskian Closure and its Dual

(joint work with Bruno Da Ré)

It is known that classical logic is the least logic that extends both Kleene’s logic K3 and the logic of paradox LP, that Kleene’s logic of order KO is the greatest logic that both of them extend, and that each of them is incomparable to the other (see e.g. [4]). However, the inclusion order over their sets of valid inferences fails to form a lattice: while KO is the intersection of LP and K3, classical logic cannot be identified with their union (as noted in [5]).
Drawing on [2], which proves that the composition of K3 and LP is the logic ST, we show that given any pair of the aforementioned logics, their join coincides with the transitive closure of their union. In particular, we shall see that once closed under transi- tivity, the union of K3 and LP is classical logic. Then we define an operator dual to the transitive closure operator, which, when applied to the intersection of K3 and LP, yields the non-reflexive logic TS. In general, given a logic L, the dual transitive closure operator extracts all and only the theorems and antitheorems of L. This enables the construction of the lattice of sets of theorems and antitheorems of classical logic, K3, LP and TS.
These results are ultimately extended in three directions. Firstly, it is shown that the transitive closure operator can be turned into a Tarskian closure operator that transforms any logical consequence into a reflexive, transitive and monotonic one. Symmetrically, its dual can be turned into a dual Tarskian closure operator: applying the operator to any logic will yield a non-Tarskian logic. Secondly, we extend these results to logics neighboring K3 and LP, founded on Boolean normal monotonic schemes and ss and tt consequence relations (cf. [3]). Thirdly, it is shown that these results can be transposed at any level of the metainferential hierarchy defined in [1].

[1]  Eduardo Barrio, Federico Pailos, and Damian Szmuc. A hierarchy of classical and paraconsistent logics. Journal of Philosophical Logic, 49:93–120, 2020.

[2]  Quentin Blomet and Paul Égré. ST and TS as product and sum. Manuscript submitted for publication, 2024. https://doi.org/10.48550/arXiv.2401.03436.

[3]  Bruno Da Ré, Damian Szmuc, Emmanuel Chemla, and Paul Égré. On three-valued presentations of classical logic. The Review of Symbolic Logic, pages 1–26, 2023.

[4]  Adam Prenosil. Cut elimination, identity elimination, and interpolation in super-Belnap logics. Studia Logica, 105(6):1255–1289, 2017.

[5] Stefan Wintein. On all strong Kleene generalizations of classical logic. Studia Logica, 104:503–545, 2016.

Agustina Borzi (Buenos Aires, CONICET): A Substructural Approach to Content Inclusion

(joint work with Martina Zirattu)

In this talk, we critically discuss what has become known as logics of variable inclusion (or content
inclusion): logical systems where validity requires that the propositional variables occurring in the
conclusion are included among those appearing in the premises (right variable inclusion), or vice
versa (left variable inclusion). One notable example is given by Paraconsistent Weak Kleene and its
Paracomplete counterpart (or WK logics for short), which are known to be, respectively, the left
and right variable inclusion companions of Classical Logic (CL).

The main goal of this talk is to set forth refined versions of the variable inclusion companions for
CL, which we will call the analytic and synthetic companions of CL. We will characterize them
proof-theoretically, via a two-sided sequent calculus. The main feature of the refinements we are
proposing is that they are substructural: they both share the same rules for the connectives as the WK logics, but in each case we impose linguistic constraints on the application of Weakening. In
exchange for losing monotonicity, each of the companions we present gets to keep all classical
anti-theorems (theorems) along with unconditional right (left, resp.) variable inclusion.

Javier Viñeta García (Navarra): On a Generalization of all Strong Kleene Generalizations of Classical Logic

(joint work with Pablo Cobreros, Isabel Grábalos, Joaquín Toranzo Calderón, and Martina Zirattu)

In his 2016 article On all Strong Kleene generalizations of Classical Logic, Stefan Wintein provides a detailed and comprehensive semantic and tableau-based analysis of the consequence relations that can be defined over the four-valued Belnap-Dunn semantics. These include familiar consequence relations like FDE, which takes {t, b} as the set of designated values, but also much less familiar relations that don't follow the designated-value strategy. It turns out that many of the interesting features of these relations are made evident at the level of metainferences and, although Wintein discusses some aspects of metainferences, his work does not provide a systematic way to decide on the validity of metainferences for these logics. In this paper, we extend Wintein's tableaux from inferences to metainferences. The paper ends with an intriguing dilemma about metainference validity.

George Metcalfe (Bern): Substructural logics with minimally true tautologies

The tautologies of propositional classical logic are always interpreted by the same (greatest) element in a Boolean algebra, but such uniformity is typically lacking in "weakening-free" substructural logics. In particular, a tautology "A implies A" may be mapped to a value in a structure for the logic that is strictly greater than the element t representing minimal truth; that is, "A implies A" is a tautology of the logic, but it is not the case that "A implies A" is equivalent to t. Several weakening-free substructural logics may be found in the literature, however, that have “minimally true” tautologies: notably, the logics of Iseki’s BCI-algebras and Raftery and van Alten’s sircomonoids, and the comparative logics of Casari, including Abelian logic, introduced independently by Meyer and Slaney. In this talk, based on a joint paper with José Gil-Férez and Frederik Lauridsen [1], I will explain how proof theory and decidability results can be obtained for these logics by adding a restricted form of weakening, justified by a Glivenko-style property, to suitable sequent calculi.

[1] J. Gil-Férez,  F. Lauridsen, and G. Metcalfe. Integrally Closed Residuated Lattices. Studia Logica 108 (2020), 1063-1086.

Alessandra Palmigiano (VU Amsterdam): Non-distributive logics: from semantics to meaning

In this talk, I will discuss an ongoing line of research in the relational (non topological) semantics of non-distributive logics (aka LE-logics, i.e. those logics canonically associated with varieties of normal lattice expansions). The developments we consider are technically rooted in dual characterization results and insights from unified correspondence theory. However, these developments also have broader, conceptual ramifications for the intuitive meaning of non-distributive logics. Specifically, I will discuss two types of relational semantics for non-distributive logics: one based on polarities, or formal contexts from FCA, and another based on reflexive graphs. I will argue that the polarity-based semantics supports the recognition of non-distributive logics as the logics of categories or concepts, and the graph-based semantics supports their recognition as hyper-constructive logics of evidential truth.

Guendalina Righetti (Oslo): Combining Concepts: Integrating Logical and Cognitive Theories of Concepts

How do human minds represent, and then combine, concepts? Research in experimental and cognitive psychology has extensively pursued to answer the question of the nature of concepts, giving rise to complex representation models. Unfortunately, these models often lack a clear or complete formalisation, making it difficult to capture them precisely in computational models. Knowledge Representation aims to represent knowledge about the world in a format suitable for re-use in computational systems, with the general goal of advancing Artificial Intelligence. Cognitive models of human conceptualisation are thus of pivotal importance for the field. Nevertheless, formal work in AI and Knowledge Representation does not always consider these models and the cognitive adequacy of computational systems is frequently sacrificed in favour of better performance.


In this talk, we endeavour to bridge the gap between computational and cognitive models of concepts, to provide a more cognitively adequate modelling of concept and concept combination in Knowledge Representation and Artificial Intelligence. To do so, we leverage a representation of concepts motivated by theories of concepts in cognitive psychology, combining logical methods with insights from statistical learning.

Damian Szmuc (Buenos Aires, CONICET): Non-deterministic matrices for semi-cocanonical deduction systems

This article aims to dualize several results that Lahav has proved concerning various types (including possibly Cut-free and Identity-free systems) of canonical sequent calculi, systems equipped with well-behaved forms of left and right introduction rules for logical expressions. Instead, we focus on such kinds but rather of co-canonical sequent calculi, systems equipped with well-behaved forms of left and right elimination rules for logical expressions---which, simply put, proceed from sequents featuring complex formulae to their component sub-formulas. Furthermore, this work aims to explore combinations of canonical and co-canonical rules within a sequent calculus. Our main goals, are to prove soundness and completeness results for the target systems' consequence relation in terms of their characteristic 3- or 4-valued non-deterministic matrices. These results will, incidentally, affect the potential repercussion of adding structural rules such as Cut or Identity to these calculi---phenomena usually described as Cut-admissibility and Identity-anti-admissibility, respectively.

Matteo Tesi (TU Vienna): Ways to infinity in structural proof theory

In the present talk we provide an overview of the expressive power of infinitary logics in classical and non-classical settings from a proof-theoretic point of view. In particular, we focus on sequent calculi for infinitary logics with sequents built from infinite multisets of formulas. Derivations in such systems are well-founded rooted trees in which every node is occupied by a sequent with possibly countably many formulas. We introduce a new cut-elimination procedure for such systems and we show that working with infinite sequents in a substructural environment strongly enhances the expressivity of the system, contrary to what happens in intuitionistic and classical logics.

Peter Verdée (Louvain): A reason-based hyperintensional semantics for substructural logics without weakening

In this talk we present a generic semantics for substructural logics without Weakening, based on a formalization of abstract reasons there may be for or against sentences. The semantics is based on a mereologically structured set of states, called reasons, for or against formulas, some of which are marked as exactly incoherent, based on the sequents valid in the substructural logic. It is supposed to capture the hyperintensional intuition that two sentences express the same proposition iff they can be true for the same reasons. We prove that, at least for a non-transitive relevantization (let a relevantization of a consequence relation L be a consequence relation without Weakening such that, when Weakening is added, full L is obtained) of classical logic called NTR, this reason-based semantics can be defined on the basis of Kit Fine’s bilateral exact truthmaker semantics for classical logic, by requiring that the fusion of a falsity-maker and a reason for a formula, on the one hand, and the fusion of a truth-maker and a reason against a formula, on the other hand, be exactly incoherent reasons.  We argue that this establishes a deep relation between the exactness of semantic relations and the relevance of consequence relations.

Elia Zardini (Madrid): Paradox and Substructurality

First, I’ll introduce some of the main paradoxes in philosophy of logic: the paradoxes of self-reference, the paradoxes of vagueness and the paradoxes of relevance. Then, I’ll present the principal substructural approaches to those paradoxes and explain their advantages over structural nonclassical approaches: that they often revise classical logic without revising the fundamental principles governing logical operations, that they often provide a unified solution to the paradoxes of a certain kind; that they often afford the only way to uphold certain compelling principles concerning the original notions with their intended force. It is common to assume that such advantages accrue to substructural approaches because the structural level is more fundamental than the operational one. However, I’ll explore the opposite hypothesis according to which the operational rules of a logic ground its structural rules: a logic’s denial of a classical structural rule is due to its denial of some classical rule concerning conjunction, disjunction or the conditional. Finally, I’ll argue that such a hypothesis naturally leads to a re-conceptualisation of a large class of substructural logics and of the corresponding substructural approaches to paradox as unusually centering on logical operations (conjunction and disjunction) whose arguments are all upwards monotonic—that is, in effect, logical operations of positive composition.

Call for Abstracts: 

PLEXUS Workshop on Substructural and Non-Classical Logics, University of Turin, Italy, June 27 and 28, 2024. 

The workshop aims at bringing together philosophers, computer scientists, and mathematicians working on substructural, many-valued, and non-classical logic. Confirmed speakers include Guillermo Badia, Alessandra Palmigiano, George Metcalfe, Guendalina Righetti, and Elia Zardini. The workshop is held under the auspices of the PLEXUS research program. 

Any paper related to the topic of the workshop is welcome, including (but not limited to): 

  1. Many-valued logics (including proof-theoretic and algebraic aspects)
  2. Substructural logics (linear logics, non-transitive logics, non-reflexive logics, non-monotonic logics, and more)
  3. Paraconsistent and paracomplete logics
  4. Meta-inferential logics
  5. Applications of substructural and non-classical logics (e.g. in philosophy of language and mind, epistemology, linguistics, and more)

Extended abstracts (max 1,000 words) should be sent to lo.rossi@unito.it by May 7. Decisions will be notified by May 15. 

Depending on the budget, we may be able to offer bursaries to help mitigate the expenses of contributing speakers.

Should you have any questions, please feel free to write to lo.rossi@unito.it.

Sponsor: Research Grant MSCA Staff Exchanges 2021 (HORIZON-MSCA-2021-SE-01) no. 1010866295 “PLEXUS: Philosophical, Logical, and Experimental Routes to Substructurality”