💻 computer science

A Sequent Calculus for General Inductive Definitions

This paper introduces SCFO(ID), a new sequent calculus that extends the existing LKID system to support formal proofs for general non-monotone inductive definitions in FO(ID) by adapting principles from stable semantics to overcome previous syntactic limitations.

Original authors: Robbe Van den Eede, Marc Denecker

Published 2026-04-22

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Robbe Van den Eede, Marc Denecker

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to teach a robot how to understand the world. You give it a set of rules to build knowledge, like "If it's a bird, it flies" or "If it's a parent, it has a child." This is easy. But what if you want to teach it something trickier, like "If it's not a bird, it doesn't fly"? Or even weirder, "If it's not a liar, it tells the truth"?

These "negative" rules (using "not") are called non-monotone definitions. They are powerful but dangerous. If you aren't careful, they can create logical loops that make the robot's brain spin forever, like a dog chasing its own tail. This is the problem of paradoxes (like the famous "This sentence is false").

For a long time, computer scientists had to put strict guardrails on these rules to keep the robot safe. They said, "You can only use 'not' if you follow a very specific, boring order." This kept the robot from crashing, but it also stopped it from learning many natural and useful things.

The Big Idea: A New Rulebook

The authors of this paper, Robbe Van den Eede and Marc Denecker, have written a new rulebook (a "Sequent Calculus" called SCFO(ID)) for teaching robots these tricky, non-monotone rules without the boring guardrails.

Think of their new rulebook as a smart construction manual.

1. The Construction Site (The Logic)

Imagine building a house.

Old Way (Monotone): You lay a brick, then another on top. Once a brick is there, it stays there. You can never remove it. This is safe but limited.
New Way (Non-Monotone): You might say, "If there is no wall here, build a window." But if you build the wall later, the window must disappear. This is more flexible but risky. If you aren't careful, you might end up in a loop where you keep building and tearing down the same wall forever.

The authors' new system allows the robot to handle this "building and tearing down" safely. It uses a concept called Stable Semantics, which is like a "reality check." It asks: "If I assume this is true, does it stay true? If I assume it's false, does it stay false?" If the answer is "no, it flips back and forth," the system recognizes it as a paradox and stops the construction, rather than crashing.

2. The Magic Tool: The Induction Hypothesis

The core of their new rulebook is a special tool called the Induction Rule.

Imagine you are trying to prove that every student in a school is wearing a uniform.

The Standard Proof: You check the first student. Then you say, "If Student A is wearing a uniform, then Student B (who comes after A) must be too." You keep doing this down the line.
The Problem with "Not": What if the rule is "If a student is not wearing a uniform, they get detention"? To prove someone gets detention, you have to prove they are not wearing a uniform. But to prove they are not wearing a uniform, you have to be sure no one else forced them to wear one. It gets messy.

The authors' trick is simple but brilliant: Only look at the "Yes" parts when making your guess.
When they make a guess (an "Induction Hypothesis") about what the robot should believe, they only replace the "Yes" (positive) parts of the rules with their guess. They leave the "No" (negative) parts alone.

Analogy: Imagine you are trying to solve a maze. You draw a path on the map. If you hit a wall (a negative condition), you don't try to redraw the wall; you just acknowledge the wall exists and keep going. By ignoring the "No" parts in your guess, you avoid getting trapped in a loop where your guess changes the wall, which changes your guess, which changes the wall...

3. Why This Matters

Before this paper, if you wanted to prove something about a complex, self-referential system (like a computer program that checks its own code, or a legal system that defines its own exceptions), you often couldn't do it formally. You had to rely on intuition.

With SCFO(ID), you can now:

Prove things formally: You can mathematically show that a complex set of rules works correctly.
Catch paradoxes: The system can formally prove why a set of rules is broken (non-total). For example, it can prove that the "Liar Paradox" has no solution, rather than just saying "the robot is confused."
Handle real-world logic: It allows for definitions that look like how humans actually think, including exceptions and negations, without forcing them into a rigid, unnatural structure.

The Catch (The "Gödel" Limit)

The authors are honest about the limits. They say, "We can't prove everything."
This is due to a famous math rule (Gödel's Incompleteness Theorem) which says that in any system complex enough to count numbers, there will always be some true statements that you can't prove.
So, while their new rulebook is much stronger than previous ones, it's not magic. It can't solve every possible puzzle. However, it solves many more than before, and it does so in a way that is mathematically sound.

Summary

Think of this paper as upgrading the operating system for logical reasoning.

Before: The system was like a strict teacher who only let you ask questions if you followed a rigid script. It was safe, but it couldn't handle complex, real-life situations.
Now: The system is like a wise mentor. It lets you ask complex, tricky questions involving "what if" and "not." It has a special safety mechanism (the induction rule) that prevents you from falling into logical traps, and it can even tell you when a question is unanswerable because the question itself is a paradox.

This allows computer scientists to build more robust, intelligent systems that can reason about the messy, contradictory, and complex nature of the real world.

1. Problem Statement

Inductive definitions are fundamental to mathematics and computer science, used to define concepts like natural numbers, transitive closures, and satisfaction relations. While classical First-Order Logic (FO) cannot express these concepts directly, FO(ID) (First-Order Logic with Inductive Definitions) extends FO with a language construct for general inductive definitions.

The core challenge addressed in this paper is the lack of a robust proof system (sequent calculus) for FO(ID) that supports general non-monotone definitions.

Existing Limitations: Previous proof systems (e.g., LKID by Brotherston and Simpson) were restricted to monotone (positive) definitions or stratified definitions. These restrictions exclude many natural and useful definitions found in logic programming and knowledge representation, such as those involving negation in rule bodies that are not stratified (e.g., the definition of even numbers via structural induction or the satisfaction relation for propositional logic).
The Gap: There was no formal deductive system capable of handling the full generality of FO(ID), including non-monotone rules where the application of a rule depends on the absence of certain facts, potentially leading to paradoxes or non-total definitions.

2. Methodology

The authors propose SCFO(ID), a new sequent calculus designed to handle general inductive definitions. The methodology involves extending the existing sequent calculus LKID (which handles monotone definitions) by adapting the induction rule to accommodate non-monotonicity.

Key Technical Components:

Extension of LKID: The calculus retains the standard structural and logical rules of classical first-order logic (SCFO) and the rules for equality.
The Induction Rule (def L): The central innovation is the left introduction rule for defined atoms.
- In standard induction (for monotone definitions), the induction hypothesis replaces all occurrences of the defined predicate in the rule body.
- In SCFO(ID), the induction hypothesis replaces only the positive occurrences of defined predicates in the rule body. Negative occurrences are left untouched.
- Rationale: This asymmetry is inspired by the Stable Semantics (from Answer Set Programming) and the Well-Founded Semantics. The authors argue that replacing negative occurrences would lead to unsoundness, as induction hypotheses act as upper bounds on the defined set; negating an upper bound does not necessarily provide a valid lower bound.
Right Introduction Rule (def R): Allows deriving the head of a rule from its body, similar to standard implication introduction but specific to definitional rules.
Handling Non-Totality: The system is designed to handle definitions that may not yield a unique two-valued model (e.g., the "Liar paradox" definition $P \leftarrow \neg P$ ). It can formally prove the non-totality of such definitions.

3. Key Contributions

The paper makes several theoretical and practical contributions:

SCFO(ID) Calculus: The formal definition of a sequent calculus that supports general non-monotone inductive definitions without syntactic restrictions like stratification.
Soundness: The authors prove that SCFO(ID) is sound with respect to three major semantics:
- The Well-Founded Semantics (the standard semantics for FO(ID)).
- The Stable Semantics (common in Logic Programming/ASP).
- The Henkin Semantics (a generalization of stable semantics for first-order logic).
- Significance: This ensures that any theorem provable in SCFO(ID) is valid under these standard interpretations.
Correspondence Theorem: The authors establish a correspondence between SCFO(ID) and a first-order sequent calculus (SCFO). They show that a regular sequent involving definitions is provable in SCFO(ID) if and only if the corresponding sequent, where definitions are replaced by their first-order approximations (Material Implications + Induction Schemes), is provable in standard first-order logic.
Completeness Results:
- Propositional Fragment: SCFO(ID) is complete for the propositional fragment of FO(ID) with respect to the Stable Semantics.
- First-Order Fragment: It is complete for a first-order fragment with respect to the Henkin Semantics.
- Note: Due to Gödel's First Incompleteness Theorem, the system cannot be complete with respect to the standard Well-Founded or Stable semantics for the full first-order language (as it captures Peano Arithmetic).
Cut-Elimination and Cut-Restriction:
- General Case: Cut-elimination does not hold for general FO(ID) sequents (counterexamples provided).
- Positive Definitions: Cut-elimination holds for definitions consisting only of positive rules.
- Stratified Definitions: A weakened cut-elimination (called Cut-Restriction) is proven for stratified definitions. In this case, cuts are allowed but restricted to specific formulas (e.g., $Q(\bar{y}) \lor \neg Q(\bar{y})$ ), narrowing the search space for proof search.

4. Results and Examples

The paper validates the calculus through various examples:

Natural Numbers: Proving properties of standard monotone definitions.
Even/Odd Numbers: Proving properties of mutually defined predicates.
Non-Monotone Definitions: Formal proofs for the satisfaction relation of propositional logic (involving negation) and distance in graphs.
Paradoxes and Non-Totality: The system successfully derives the negation of paradoxical definitions (e.g., $\{P \leftarrow \neg P\}$ ), proving they have no two-valued models. This provides a proof-theoretical analysis of ill-formed definitions.
Access Control: A complex example involving delegation and blocking, demonstrating the system's ability to handle non-stratified, non-monotone rules in a realistic scenario.

5. Significance

Theoretical Unification: SCFO(ID) bridges the gap between the constructive nature of inductive definitions and declarative logical reasoning. It provides a formal foundation for reasoning about general inductive definitions, which were previously difficult to handle in a proof-theoretic setting.
Logic Programming Integration: By being sound with respect to both Well-Founded and Stable semantics, SCFO(ID) can be used to verify logic programs (including those with negation) and fragments thereof.
Proof Logging and Verification: The calculus is suitable for implementation in proof assistants and proof logging algorithms. This allows combinatorial search algorithms to generate certifiable proofs for properties involving complex inductive definitions.
Handling Paradoxes: Unlike many systems that require definitions to be stratified to avoid paradoxes, SCFO(ID) can formally analyze and prove the non-totality of paradoxical definitions, offering a tool to distinguish "sensible" definitions from "ill-formed" ones.

In conclusion, the paper presents SCFO(ID) as a theoretically substantiated, sound, and practically applicable proof system that significantly extends the capabilities of existing logics to cover the full spectrum of general inductive definitions found in computer science and mathematics.