On Conditional Axioms and Associated Inference Rules

Abstract

In the present paper, we address the following general question in the framework of classical first-order logic. Assume that a certain mathematical principle can be formalized in a first-order language by a set E of conditional formulas of the form α(v)→β(v). Given a base theory T, we can use the set of conditional formulas E to extend the base theory in two natural ways. Either we add to T each formula in E as a new axiom (thus obtaining a theory denoted by T+E) or we extend T by using the formulas in E as instances of an inference rule (thus obtaining a theory denoted by T+E–Rule). The theory T+E will be stronger than T+E–Rule, but how much stronger can T+E be? More specifically, is T+E conservative over T+E–Rule for theorems of some fixed syntactical complexity Γ? Under very general assumptions on the set of conditional formulas E, we obtain two main conservation results in this regard. Firstly, if the formulas in E have low syntactical complexity with respect to some prescribed class of formulas Π and in the applications of E–Rule side formulas from the class Π and can be eliminated (in a certain precise sense), then T+E is ∀B(Π)-conservative over T+E–Rule. Secondly, if, in addition, E is a finite set with m conditional sentences, then nested applications of E–Rule of a depth at most of m suffice to obtain ∀B(Π) conservativity. These conservation results between axioms and inference rules extend well-known conservation theorems for fragments of first-order arithmetics to a general, purely logical framework.

Keywords

• first-order inference rules
• conservative extensions
• existentially closed models