Undecidability of Linear Logics without Weakening
Jun Suzuki, Katsuhiko Sano · 2025
Read Undecidability of Linear Logics without Weakening by Jun Suzuki, Katsuhiko Sano (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2509-00644.txt.
Introduction
Jun Suzuki and Katsuhiko Sano prove a negative result in logic. They show two linear logics without weakening are undecidable. Undecidable means no algorithm can always settle provability. A sequent is the formal claim whose proof is in question. Their systems drop the weakening rule for an exponential modality. The base system is Girard's classical linear logic. That logic tracks how resources are used.
The first system, CLLR, is shown undecidable by reduction. The reduction ties it to the known result for the full logic. Two unit elements let them simulate the missing weakening rule. The second system, CLLRR, drops those units as well. For it, they simulate any two-counter machine. Two-counter machines are a simple model of full computation.
Catalog record
| CREATOR | Jun Suzuki, Katsuhiko Sano |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 50 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2509-00644
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Undecidability of Linear Logics without Weakening Jun Suzuki, Katsuhiko Sano Abstract . The goal of this paper is to establish that it remains undecidable whether a sequent is provable in two systems in which a weakening rule for an exponential modality is completely omitted from classical propositional linear logic 𝐂𝐋𝐋 \mathbf{CLL} introduced by Girard (1987), which is shown to be undecidable by Lincoln et al. (1992). We introduce two logical systems, 𝐂𝐋𝐋𝐑 \mathbf{CLLR} and 𝐂𝐋𝐋𝐑𝐑 \mathbf{CLLRR} . The first system, 𝐂𝐋𝐋𝐑 \mathbf{CLLR} , is obtained by omitting the weakening rule for the exponential modality of 𝐂𝐋𝐋 \mathbf{CLL} . The system 𝐂𝐋𝐋𝐑 \mathbf{CLLR} has been studied by several authors, including Melliès-Tabareau (2010), but its undecidability was unknown. This paper shows the undecidability of 𝐂𝐋𝐋𝐑 \mathbf{CLLR} by reducing it to the undecidability of 𝐂𝐋𝐋 \mathbf{CLL} , where the units 𝟏 \mathbf{1} and ⊥ \bot play a crucial role in simulating the weakening rule. We also omit these units from the syntax and inference rules of 𝐂𝐋𝐋𝐑 \mathbf{CLLR} in order to define the second system, 𝐂𝐋𝐋𝐑𝐑 \mathbf{CLLRR} . The undecidability of 𝐂𝐋𝐋𝐑𝐑 \mathbf{CLLRR} is established by showing that the system can simulate any two-counter machine proposed by Minsky (1961). 1. Introduction The goal of this paper is to establish that it remains undecidable whether a sequent is provable in two systems in which a weakening rule for an exponential modality is completely omitted from classical propositional linear logic. Linear logic, introduced by Girard [ 3 ] , is a logical system in which the structural rules of weakening and contraction, representing discard and copy, respectively, are restricted. Because of this restriction, formulas cannot be freely copied and discarded, so that formulas in the antecedent of a sequent can be considered as resources. However, we can apply weakening and contraction to a formula in the antecedent prefixed with the exponential modality “ \oc ”. Resources with “ \oc ” can be freely copied and discarded. What then if we restrict the structural rules of the exponential modality? This paper studies systems obtained by omitting the weakening rules of the exponential modality and shows their undecidability. Structural rules and decidability of proof systems have a subtle relationship. Table 1 summarizes whether linear logic systems with added or excluded structural rules are decidable. Classical propositional linear logic \mathbf{CLL} , in which weakening and contraction apply only to formulas with exponential modalities, is undecidable (Lincoln et al. [ 11 , Theorem 3.7] ). If one removes the restriction of weakening and contraction in \mathbf{CLL} , i.e., adds unlimited weakening and unlimited contraction to \mathbf{CLL} , then the system becomes equivalent to a propositional modal logic \mathbf{S4} , which is decidable. The system obtained by adding only unlimited weakening to \mathbf{CLL} is also decidable (Kopylov [ 8 , Theorem 3] ). Similarly, \mathbf{CLL} with unlimited contraction is decidable (Okada-Terui [ 16 , Corollary 1] ). What if one omits structural rules for exponential modalities? For example, \mathbf{MALL} , classical propositional linear logic without exponential modalities, which does have neither weakening nor contraction, is decidable (Lincoln et al. [ 11 , Theorem 2.2] ). However, non-commutative classical propositional linear logic, which we can regard as \mathbf{CLL} without the third structural rule exchange , is undecidable (Lincoln et al. [ 11 , Theorem 4.8] ). Non-commutative \mathbf{CLL} is so complex that it is undecidable if one omits units and additive connectives. Furthermore, non-commutative propositional linear logic without weakening is also undecidable. This system is still undecidable if one omits units \mathbf{1} and \bot from its language. These undecidabilities can be deduced by a theorem and a corollary about non-commutative subexponential linear logic in Kanovich et al. [ 7 , Theorem 8, Corollary 14] . Subexponential linear logic is explained below. Table 1. Structural Rules and Decidability System +/- Structural rules Decidable or Undecidable \mathbf{S4} \mathbf{CLL} + {Weak, Cont} Decidable cf. Blackburn et al. [ 1 , Corollary 6.8] CLLW \mathbf{CLL} + Weakening Decidable Kopylov [ 8 , Theorem 3] CLLC \mathbf{CLL} + Contraction Decidable Okada-Terui [ 16 , Corollary 1] \mathbf{CLL} \mathbf{CLL} Undecidable Lincoln et al. [ 11 , Theorem 3.7] NCCLL \mathbf{CLL} - Exchange Undecidable Lincoln et al. [ 11 , Theorem 4.8] \mathbf{CLLR} \mathbf{CLL} - Weakening Undecidable Theorem 11 of this paper \mathbf{CLLRR} \mathbf{CLL} - Weakening Lang: \mathbf{CLL}-\{\mathbf{1},\bot\} Undecidable Theorem 19 of this paper \mathbf{CLL}-\{\text{Weak, Exch}\} Undecidable Kanovich et al. [ 7 , Theorem 8] \mathbf{CLL} - {Weak, Exch} Language: \mathbf{CLL}-\{\mathbf{1},\bot\} Undecidable Kanovich et al. [ 7 , Corollary 14] MALL Language: \mathbf{CLL} - { \oc,\wn } Decidable Lincoln et al. [ 11 , Theorem 2.2] Then it is not obvious whether classical propositional linear logic without only weakening is decidable. In this paper, we introduce two systems, \mathbf{CLLR} and \mathbf{CLLRR} , and show that both of them are undecidable. The first system, \mathbf{CLLR} , is obtained by omitting weakening for the exponential modality of \mathbf{CLL} . This system was introduced by Melliès-Tabareau [ 12 ] 1 1 1 Melliès-Tabareau refer to Jacobs [ 5 ] as previous research ( [ 12 , p. 636] ), but a sequent calculus that Jacobs introduced is different from that of Melliès-Tabareau and ours. and studied for its game semantics and categorical interpretation, but its decidability has been still open. As we will see in Section 3 , since \mathbf{CLLR} can simulate weakening, the undecidability of \mathbf{CLLR} can be reduced to that of \mathbf{CLL} . In this simulation, the logical units \mathbf{1} and \bot play a crucial role. Therefore, we remove them from the syntax, along with the associated rules of \mathbf{CLLR} , in order to define a new system, \mathbf{CLLRR} . In this system, the simulation is impossible. Formally, our main results are as follows. (1) The problem of whether a sequent is provable in \mathbf{CLLR} is undecidable. (2) The problem of whether a sequent is provable in \mathbf{CLLRR} is undecidable. We consider linear logic systems in which contraction is restricted only to formulas in the antecedent prefixed with “ \oc ” (and dually in the succedent prefixed with “ \wn ”), while weakening is not allowed at all. This system is capable of representing resources that can be freely copied but not discarded. A study of logics restricting structural rules of exponential modalities is initiated by Danos et al. [ 2 , Section 5] . The system introduced by them, called subexponential linear logic after Nigam-Miller [ 14 ] , indexes exponential modalities and control whether structural rules can be applied. Our system, in which there is no modality that allows weakening at all, is a special case of subexponential linear logic. Danos et al. [ 2 , Proposition 5.2] proves cut-elimination theorem for subexponential linear logic, which yields cut-elimination of our systems, \mathbf{CLLR} and \mathbf{CLLRR} . However, the paper [ 2 ] did not address the question of whether the two systems are decidable. We can also use our arguments to demonstrate the undecidability of the intuitionistic variants of \mathbf{CLLR} and \mathbf{CLLRR} . This paper is structured as follows. Section 2 introduces syntax and proof systems of ordinary classical linear logic. Since we apply a semantic argument to prove the undecidability of \mathbf{CLLRR} , we also introduce phase semantics, a standard algebraic semantics of linear logic. In Section