A Short and Readable Proof of Cut Elimination for Two First-Order Modal Logics

Feng Gao, George TourlakisBulletin 2015 · DOI

TL;DR

This paper provides a significantly simplified and more accessible proof of "cut elimination"—a cornerstone of proof theory—for two specific first-order modal logics, $M^3$ and $ML^3$. By adapting a recent streamlined technique originally designed for propositional logic, the authors replace notoriously dense and complex proofs with a version that is much easier for researchers to follow and verify.

What Problem Does This Paper Address?

In the world of formal logic, "cut elimination" is a bit like showing that if you have a shortcut in a mathematical proof, you could have written the proof without that shortcut from the start. This property is vital because it guarantees that a logic is consistent and makes it much easier to build automated theorem provers.

While cut elimination is well-understood for basic propositional logic, it becomes a nightmare when you add "modalities" (concepts like necessity or provability, denoted by $\Box$) and "quantifiers" (like "for all" $\forall$).

The "natural" first-order extension of the famous provability logic (GL), known as $QGL$, actually fails to support cut elimination. To fix this, logicians developed alternative systems called $M^3$ and $ML^3$. However, the existing proofs that these systems support cut elimination were "extremely complex," spanning many pages of dense, difficult-to-parse induction. The authors set out to provide a "short and readable" alternative.

Methods

The authors utilize a Gentzen-style sequent calculus, a framework where logical arguments are represented as "sequents" (e.g., "if these hypotheses are true, then one of these conclusions must be true").

The core innovation isn't a new logic, but a new proof strategy. They adapt a 2015 technique by Jude Brighton, which was originally used to simplify the proof for the propositional version of GL.

Key technical aspects include:

  • Ordinal Induction: Instead of a standard induction on the height of a proof tree, they use a more sophisticated induction based on an ordinal ($\alpha = \omega^2 \cdot C + \omega \cdot RR + m$). This allows them to account for the complexity of the formula ($C$), the "reducibility rank" ($RR$), and the order of derivation ($m$) simultaneously.
  • Syntactic Restrictions: The proof relies on the specific "opaque" nature of $M^3$ and $ML^3$, where the formula $\Box A$ is treated as a sentence (containing no free variables), which prevents the variables from "clashing" in ways that break cut elimination in other systems.

Datasets

Not discussed in the paper. As a theoretical work in mathematical logic and proof theory, this paper relies on formal definitions and symbolic proofs rather than empirical data or benchmarks.

Key Insights and Ideas

  • The "Opaque" Box is Key: The reason $QGL$ fails cut elimination while $M^3/ML^3$ succeed is how they handle variables inside the $\Box$ operator. By ensuring $\Box A$ is always a sentence, the authors maintain a "clean" environment for the cut rule to be eliminated.
  • Proof Architecture Matters: The "aha moment" is that the legendary complexity of previous proofs (like Valentini’s) wasn't necessarily a property of the logic itself, but a result of the specific inductive tools used. By switching to Brighton’s "regress process" approach, the most difficult part of the proof—handling the "diagonal formula" in modal rules—becomes significantly more manageable.
  • Unified Approach: The authors show that the same simplified strategy works for both $M^3$ (via the $GTKS$ system) and $ML^3$ (via the $GLTS$ system), demonstrating the robustness of the method.

Key Results

  • Admissibility of Cut: The paper successfully proves that the "Cut" rule is admissible in both $GTKS$ and $GLTS$. This means any theorem proven with the cut rule can also be proven without it.
  • Simplification: The authors successfully reduced a "complex and lengthy" proof into one that is "short and easy to read," making the metatheory of these logics accessible to a wider audience of computer scientists and logicians.
  • Formal Equivalence: The work reinforces the equivalence between these Gentzen-style systems and their original Hilbert-style formulations, solidifying the proof-theoretical foundation of $M^3$ and $ML^3$.

Limitations and Future Work

  • Specific Syntax: The proof is highly dependent on the specific syntactic constraints of $M^3$ and $ML^3$ (the "opaque" box). It does not provide a path to "restore" cut elimination to more "transparent" logics like $QGL$, where the property is known to be impossible.
  • Complexity of Quantifiers: While shorter than previous versions, the proof is still "slightly complicated by the presence of quantification."
  • Future Directions: The authors suggest that these simplified proofs could make it easier to explore other properties of these logics, such as Craig interpolation or the disjunction property, and potentially lead to more efficient automated reasoning tools for provability logic.

Summary updated

Abstract

A well established technique toward developing the proof theory of a Hilbert-style modal logic is to introduce a Gentzen-style equivalent (a Gentzenisation), then develop the proof theory of the latter, and finally transfer the metatheoretical results to the original logic (e.g., [1, 6, 8, 18, 10, 12]). In the first-order modal case, on one hand we know that the Gentzenisation of the straightforward first-order extension of GL, the logic QGL, admits no cut elimination (if the rule is included as primitive; or, if not included, then the rule is not admissible [1]). On the other hand the (cut-free) Gentzenisations of the first-order modal logics M3 and ML3 of [10, 12] do have cut as an admissible rule. The syntactic cut admissibility proof given in [18] for the Gentzenisation of the propositional provability logic GL is extremely complex, and it was the basis of the proofs of cut admissibility of the Gentzenisations of M3 and ML3, where the presence of quantifiers and quantifier rules added to the complexity and length of the proof. A recent proof of cut admissibility in a cut-free Gentzenisation of GL is given in [5] and is quite short and easy to read. We adapt it here to revisit the proofs for the cases of M3 and ML3, resulting to similarly short and easy to read proofs, only slightly complicated by the presence of quantification and its relevant rules.
BibTeX
@article{gao2015short,
  author = {Feng Gao and George Tourlakis},
  title = {{A Short and Readable Proof of Cut Elimination for Two First-Order Modal Logics}},
  journal = {Bulletin},
  year = {2015},
  doi = {10.18778/0138-0680.44.3.4.03},
}
Figure