Papers for

logic system designers

Papers whose findings have a practical use for this group, as judged from the abstract. Open a paper to read what it means in practice.

Tableaux rules clarify definite descriptions in free logic theories

Tableaux Rules for Theories of Definite Descriptions in Positive Free Logic with Some Philosophical Remarks

Abstract: While Russell's theory of definite descriptions, expressions of the form 'the F', is almost incontrovertible in classical logic, in free logic matters stand differently. Several alternatives have been proposed. In Lambert's hierarchy, the weakest theory is his minimal free theory of definite descriptions (MFD), which only says that anything is the F iff it is the unique existing F, the strongest one is a chosen object theory in which all improper definite descriptions refer to the same object (FD2). Intermediate is Lambert's FD1, which adds ix(x = t) = t as an axiom to MFD. MFD is very weak. FD2 is very strong. One might hope to find intermediate systems in which ix(x = t) = t is provable from more fundamental principles. The present paper considers one avenue where one might hope to find them and closes it. Two theories, FDA and FDH, will be considered that are motivated by considerations from proof-theoretic semantics. The former turns out to be equivalent to FD2, the latter to have unreasonable consequences. A third theory, similarly motivated, is also not viable. The philosophical upshot of this is briefly discussed.

Thu 29 OctLogic in Computer Science
The gist
Definite descriptions are phrases like 'the F' that talk about unique things. While these work well in classical logic, they are tricky in free logic where some things may not exist. The authors study different logical theories that try to handle these phrases, focusing on intermediate versions between very weak and very strong theories. They show that some promising middle-ground theories don't work as hoped and discuss the philosophical reasons why. This helps clarify the limits of defining unique descriptions in these logical systems.
Open → 2610.40830v1

Cyclic logic extends full nonassociative lambek calculus with constants

Cyclic Nonassociative Bilinear Logic With Additive Constants as Extension of Full Nonassociative Lambek Calculus

Abstract: Cyclic Linear Logic (CyMALL, CyBL) is a compromise between Commutative Linear Logic (MALL) and Noncommutative Linear Logic (Bilinear Logic, BL). We do not admit commutativity of the tensor, but we still admit only one De Morgan negation. MALL and its variants are natural extensions of Full Lambek Calculus (FL). Abrusci proved that CyBL is not a conservative extension of FL, if we admit additive constants in these logics. In this paper we show that Cyclic Nonassociative Bilinear Logic (CyNBL) with both additive constants is a strongly conservative extension of Full Nonassociative Lambek Calculus with only one additive constant - the upper bound - and that this holds even in the presence of an arbitrary set of nonlogical axioms.

Thu 29 OctLogic in Computer Science
The gist
The authors investigate a type of logic called Cyclic Nonassociative Bilinear Logic (CyNBL), which sits between two known forms of linear logic. They show that CyNBL can expand on Full Nonassociative Lambek Calculus (FL) by adding certain constants without changing FL’s original proofs, even when extra assumptions are added. This finding clarifies how these logical systems relate and ensures that adding constants keeps things consistent. It helps understand how combining these logics preserves essential properties.
Open → 2610.40817v1

Uniform non deterministic logic semantics extend paraconsistent hierarchy

Uniform Non-Deterministic Semantics for Ciuciura's $mbC^n$-Hierarchy

Abstract: We introduce a uniform non-deterministic semantics for the hierarchy of paraconsistent systems mbC^n introduced by Ciuciura. The proposed construction generalizes Omori's three-valued semantics for mbC^1 to all systems of the hierarchy. We prove soundness and completeness of the semantics with respect to the corresponding axiomatizations and show that the consequence relations of the systems mbC^n cannot be characterized by finite deterministic matrices.

Thu 29 OctLogic in Computer Science
The gist
Some logical systems can handle contradictions without breaking down, called paraconsistent logics. This paper deals with a family of such systems called mbC^n, created by Ciuciura, and introduces a new way to understand them using a type of logic that can give multiple possible truth values at once (non-deterministic semantics). The authors also show that their method fully matches the formal rules of these systems and prove that simpler, finite methods cannot capture their behavior.
Open → 2610.40797v1

Connecting semantics for intuitionistic and classical logic operators

Connecting Base-Extension Semantics, Beth Semantics, and Ecumenical Logic

Abstract: We investigate the relationship between base-extension semantics, Beth semantics, and Prawitz's ecumenical logic. We first present a base-extension semantics for the propositional fragment of Prawitz's system and prove that it is sound and complete. The semantics interprets intuitionistic and classical operators directly within a common proof-theoretic framework, without reducing the classical operators to their intuitionistic counterparts by means of a translation. We then analyse the effect of incorporating Beth-style clauses into base-extension semantics. When arbitrary bases are admitted and $\bot$ is governed by atomic explosion, these clauses trivialise. By contrast, when $\bot$ is treated as a basic sentence and attention is restricted to consistent bases, the Beth-style clauses for atoms and disjunction characterise, respectively, classical atoms and classical disjunction in Prawitz's system. We also obtain equivalent, path-independent formulations of the classical clauses for atoms, disjunction, and implication. These results reveal that the consistency constraint is not merely a technical restriction: within base-extension semantics, it transforms clauses originally associated with intuitionistic semantics into semantic characterisations of classical operators.

Wed 28 OctLogic in Computer Science
The gist
This paper explores how different ways of understanding logical statements relate to each other, particularly intuitionistic and classical logic. The authors show a way to interpret both types of logic operators within a single framework without converting one into the other. They also find conditions under which certain semantic rules identify classical logic features. Their work clarifies how adding certain rules changes the meaning of logical operators when interpretations are restricted to consistent scenarios.
Open → 2610.38871v1

Undecidability confirmed for simple logic with one relation

The Undecidability of FO3 and the Calculus of Relations with Just One Binary Relation

Abstract: The validity problem for first-order logic is a well-known undecidable problem. The undecidability also holds even for $\mathsf{FO}3$ and (equational formulas of) the calculus of relations. In this paper we tighten these undecidability results to the following: (1) $\mathsf{FO}3$ with just one binary relation is undecidable even without equality; and (2) the calculus of relations with just one character and with only composition, union, and complement is undecidable. Additionally we prove that the finite validity problem is also undecidable for the above two classes.

Mon 26 OctLogic in Computer Science
The gist
Figuring out whether certain simple logical statements are always true is impossible to do with a perfect method. The authors show this problem remains impossible even when using only one kind of relationship between things and limiting the complexity of the logic. They also prove this holds true when looking only at scenarios with a finite number of objects. This means some questions in logic cannot be fully answered even in very simplified settings.
Open → 2610.35770v1

Categorical logic reveals symmetry between logic and geometry

Logic vs doctrines, a mirror symmetry

Abstract: This paper studies doctrines in categorical logic and their relations to fragments of geometric logic. After a brief account of the historical context for the notion of doctrine in categorical logic, we propose our working definition. We then show that there is a Galois connection between the poset of doctrines and the poset of fragments of geometric logic as defined in the framework of Kan injectivity in the 2-category of topoi, recently developed by the first and third authors. Concretely, the connection is realised by a general construction of syntactic categories and classifying topoi which encompasses all well-known examples in categorical logic. This yields a mirror symmetry, between the algebraic world of doctrines and the geometric world of topoi: to provide evidence of this phenomenon, we prove a few symmetric results relating doctrines and logics by means of syntactic categories and classifying topoi. We conclude with a discussion on the theme of conceptual completeness.

Wed 21 OctLogic in Computer Science
The gist
This paper explores a deep connection between two ways of thinking in mathematics: logical rules and geometric structures. The authors study a concept called doctrines, which organize logical systems, and show how these doctrines mirror fragments of geometric logic. They find a precise mathematical relationship, called a Galois connection, linking these logical and geometric worlds. This symmetry helps unify understanding of logic and geometry, and the authors provide examples to illustrate their findings.
Open → 2610.29771v1

Modal logic extensions unify reasoning in generalized Nelson logics

Modal Extensions of Generalised Nelson Logics

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.

Wed 7 OctLogic in Computer Science
The gist
The authors study how to add modal reasoning—thinking about necessity and possibility—to a type of logic called RM, which models certain relevant relationships. They build on earlier work to create a system that accurately captures these modal ideas within RM and related Nelson logics. This work shows that the same rules used for the modal version of RM also work for other logics in this family, making it easier to handle modal concepts across different logical frameworks.
Open → 2610.10008v1

Cheq logic cannot be captured finitely and is undecidable

Non-finite Axiomatizability and Undecidability of $\mathsf{Cheq}$

Abstract: We prove that $\mathsf{Cheq}$ is not finitely axiomatizable, resolving a longstanding open problem in intermediate and modal logics. We further prove that the undecidability of Medvedev logic implies the undecidability of $\mathsf{Cheq}$.

Wed 30 SeptLogic in Computer Science
The gist
Some parts of logic are tricky to fully describe with a small set of rules. The authors showed that the system called Cheq cannot be captured with a finite list of axioms, which solves a question that has been open for a long time. They also found that if a related logic called Medvedev logic is impossible to decide automatically, then Cheq is also undecidable. This means certain logical problems in Cheq have no algorithm that always gives an answer.
Open → 2609.39577v1

Intuitionistic modal logic shown to have finite model property

Fine Selection for Intuitionistic Modal Logic

Abstract: We extend Fine's selection method to the setting of intuitionistic modal logic and use it to provide a model-theoretic proof that Fischer Servi-style intuitionistic $\sf K4$ has the finite model property.

Tue 22 SeptLogic in Computer Science
The gist
The paper deals with a complex type of logic called intuitionistic modal logic, which combines reasoning about truth and possibility in a certain constructive way. The authors extended a method originally developed by Fine to this type of logic. Using this extension, they provide a mathematical proof that a specific form of this logic called Fischer Servi-style intuitionistic K4 always has a finite model that fits it, which is important for understanding its behavior and how it can be computed or checked. This kind of finite model property is a desirable feature for logical systems.
Open → 2609.27078v1

Medvedev logic proven undecidable and extremely complex problem

Medvedev Logic is Not Decidable. It is π01 -complete. Who Would Have Guessed?

Abstract: This project began as an attempt to prove that Medvedev logic is decidable with the help of generative AI systems. The author (as well as the generative AI systems, or at least they claim to be since I have asked them) was surprised by its eventual conclusion. We prove that Medvedev logic ML, the intermediate logic of finite problems, is Pi-01-complete under computable many-one reductions. Consequently, ML is not recursively enumerable, a fortiori undecidable, and admits no recursively enumerable sound and complete proof calculus. The proof connects the periodic domino problem with intuitionistic formulas through a shared intermediate structure that we call a Wang-Medvedev pair. Such a pair consists of a finite partially ordered set of roles together with demands. Demands define the interaction between roles. A realization labels nonempty subsets of a finite set with these roles, respecting the order and satisfying the demands. We associate a pair with each finite Wang system and show that it has a realization iff the system tiles a finite torus. We then construct an intuitionistic formula that fails on some finite Medvedev frame iff the same pair is realizable. Realizability thus provides the link between periodic tilings and the countermodels.

Thu 10 SeptLogic in Computer Science
The gist
Medvedev logic is a type of logic used to understand finite computational problems. The authors found that this logic is undecidable, meaning no algorithm can fully determine its truths. They linked the logic’s complexity to a known hard mathematical tiling problem, showing it is deeply complex and cannot be simplified into a neat set of rules. This surprising discovery overturns previous hopes that Medvedev logic might be easier to decide using AI. The proof uses a new structure called a Wang-Medvedev pair to connect these concepts.
Open → 2609.11576v1

Different types of negation change how logical reasoning works

Modus Tollens and Counterfactuals and Counterfactual Reasoning Based on Three Types of Negation

Abstract: Modus Tollens (MT) is a classical logical inference rule, while counterfactuals are hypothetical statements that are contrary to facts, and counterfactual reasoning is a process of reasoning based on counterfactuals. Negation is an indispensable core concept in them. In this paper, based on the logical systems LCOI&PLCOI with contradictory negation, opposite negation and intermediary negation, we propose three variants of Modus Tollens corresponding to distinct negation types, namely MTC: Modus Tollens based on contradictory negation, MTO: Modus Tollens based on opposite negation, and MTI: Modus Tollens based on intermediary negation. We define the implications within MTC, MTO and MTI, provide the truth value algorithms of MTC, MTO and MTI, and discuss the reducibility of these algorithms. To incorporate these three types of negation into counterfactuals and counterfactual reasoning, we differentiate counterfactuals into two types based on whether they possess logical negation, thereby proposing three counterfactuals and counterfactuals reasoning based on different logical negations. In this paper, we further argue that the three counterfactuals reasoning based on different logical negations have the same inference form as MTC, MTO and MTI, respectively. In other words, they share the same inference structure. As a result, the truth value algorithms for MTC, MTO and MTI can be as the truth value algorithms for the three counterfactuals reasoning based on different logical negations. The algorithms indicates that if the first premise of the reasoning is true, the truth values of the reasoning conclusions are identical to the truth values of the three negative premises in the reasoning premises, respectively. This reflects the consistency and accuracy of the truth value algorithms.

Mon 7 SeptArtificial Intelligence
The gist
Logical reasoning often uses a rule called Modus Tollens to draw conclusions when statements are negated. This paper shows there are three different kinds of negation—contradictory, opposite, and intermediary—and each leads to a different way of applying Modus Tollens. The authors connect these forms of negation and reasoning to counterfactual statements, which imagine what would happen if things were different from reality. Their work provides algorithms that predict the truth values of conclusions depending on the kind of negation used, helping clarify how negations affect reasoning.
Open → 2609.07483v1