Abstract An inductive proof can be represented as a proof schema, i.e. as a parameterized sequence of proofs defined in a primitive recursive way. A corresponding cut-elimination method, called schematic cut-elimination by resolution, can be used to analyse these proofs, and to extract their (schematic) Herbrand sequents, even though Herbrand’s theorem in general does not hold for proofs with induction inferences. This work focuses on the most crucial part of the schematic cut-elimination method, which is to construct a refutation of a schematic formula that represents the cut-structure of the original proof schema. We develop a new framework for schematic substitutions and define a unification algorithm for resolution schemata. Moreover, we introduce a new calculus for the refutation of formula schemata that is simpler and more expressive than previous formalisms. Finally, we show that this new formalism allows the extraction of a structure from the refutation schema, called a Herbrand system, which represents its Herbrand sequent.

In this paper we present the proof that there is no elementary translation from cut- free derivations in the sequent calculus variant of the epsilon calculus to LK-proofs with bounded cut-complexity. This is a partial answer to a question by Toshiyasu Arai. Fur- thermore, we show that the intuitionistic format of the sequent calculus variant of the epsilon calculus is not sound for intuitionistic logic, due to the presence of all classical quantifier-shift rules.

An inductive proof can be represented as a proof schema, i.e. as a parameterized sequence of proofs defined in a primitive recursive way. A corresponding cut-elimination method, called schematic CERES, can be used to analyze these proofs, and to extract their (schematic) Herbrand sequents, even though Herbrand’s theorem in general does not hold for proofs with induction inferences. This work focuses on the most crucial part of the schematic cut-elimination method, which is to construct a refutation of a schematic formula that represents the cut-structure of the original proof schema. Moreover, we show that this new formalism allows the extraction of a structure from the refutation schema, called a Herbrand schema, which represents its Herbrand sequent.

Abstract Choice logics constitute a family of propositional logics and are used for the representation of preferences, with especially qualitative choice logic (QCL) being an established formalism with numerous applications in artificial intelligence. While computational properties and applications of choice logics have been studied in the literature, only few results are known about the proof-theoretic aspects of their use. We propose a sound and complete sequent calculus for preferred model entailment in QCL, where a formula F is entailed by a QCL-theory T if F is true in all preferred models of T. The calculus is based on labeled sequent and refutation calculi, and can be easily adapted for different purposes. For instance, using the calculus as a cornerstone, calculi for other choice logics such as conjunctive choice logic (CCL) and lexicographic choice logic (LCL) can be obtained in a straightforward way.

This paper focuses on globally sound but possibly locally unsound analytic sequent calculi for quantifier macros defined by sequences of quantifiers. It is demonstrated that no locally sound analytic representation based on the usual eigenvariable condition exists. In consequence, representations by globally sound but possibly locally unsound analytic sequent calculi are used. Cut-elimination is shown by translating proofs into LK and retranslating cut-free proofs into the desired format. Finally, criteria are given for sequents to be proved without reference to the extended eigenvariable conditions.

Abstract Proof schemata are infinite sequences of proofs which are defined inductively. In this paper we present a general framework for schemata of terms, formulas and unifiers and define a resolution calculus for schemata of quantifier-free formulas. The new calculus generalizes and improves former approaches to schematic deduction. As an application of the method we present a schematic refutation formalizing a proof of a weak form of the pigeon hole principle.

Abstract This paper presents a methodology to construct globally sound but possibly locally unsound analytic calculi for partial theories of Henkin quantifiers. It is demonstrated that usual locally sound analytic calculi do not exist for any reasonable fragment of the full theory of Henkin quantifiers. This is due to the combination of strong and weak quantifier inferences in one quantifier rule.

Abstract We present a new method of computing Herbrand disjunctions. The up-to-date most direct approach to calculate Herbrand disjunctions is based on Hilbert’s epsilon formalism (which is in fact also the oldest framework for proof theory). The algorithm to calculate Herbrand disjunctions is an integral part of the proof of the extended first epsilon theorem. This paper introduces a more abstract form of epsilon proofs, the function variable proofs. This leads to a computational improved version of the extended first epsilon theorem, which allows a nonelementary speed up of the computation of Herbrand disjunctions. As an application, sequent calculus proofs are translated into function variable proofs and a variant of the axiom of global choice is shown to be removable from proofs in Neumann–Bernays–Gödel set theory.

We define a new method for proof mining by CERES (cut-elimination by resolution) that is concerned with the extraction of expansion trees in first-order logic (see Miller in Stud Log 46(4):347-370, 1987) with equality. In the original CERES method expansion trees can be extracted from proofs in normal form (proofs without quantified cuts) as a post-processing of cut-elimination. More precisely they are extracted from an ACNF, a proof with at most atomic cuts. We define a novel method avoiding proof normalization and show that expansion trees can be extracted from the resolution refutation and the corresponding proof projections. We prove that the new method asymptotically outperforms the standard method (which first computes the ACNF and then extracts an expansion tree). Finally we compare an implementation of the new method with the old one; it turns out that the new method is also more efficient in our experiments.

First-order interpolation properties are notoriously hard to determine, even for logics where propositional interpolation is more or less obvious. One of the most prominent examples is first-order G ̈odel logic. Lyndon interpolation is a strengthening of the interpolation property in the sense that propositional variables or predicate symbols are only allowed to occur positively (negatively) in the interpolant if they occur positively (negatively) on both sides of the implication. Note that Lyndon interpolation is difficult to establish for first-order logics as most proof-theoretic methods fail. In this paper we provide general derivability conditions for a first-order logic to admit Lyndon interpolation for the prenex ⊃ prenex fragment and apply the arguments to the prenex ⊃ prenex fragment of first-order Go ̈del logic.