Any intermediate propositional logic can be extended to a calculus with epsilon- and tau-operators and critical formulas. For classical logic, this results in Hilbert’s $\varepsilon $ -calculus. The first and second $\varepsilon $ -theorems for classical logic establish conservativity of the $\varepsilon $ -calculus over its classical base logic. It is well known that the second $\varepsilon $ -theorem fails for the intuitionistic $\varepsilon $ -calculus, as prenexation is impossible. The paper investigates the effect of adding critical $\varepsilon $ - (...) and $\tau $ -formulas and using the translation of quantifiers into $\varepsilon $ - and $\tau $ -terms to intermediate logics. It is shown that conservativity over the propositional base logic also holds for such intermediate ${\varepsilon \tau }$ -calculi. The “extended” first $\varepsilon $ -theorem holds if the base logic is finite-valued Gödel–Dummett logic, and fails otherwise, but holds for certain provable formulas in infinite-valued Gödel logic. The second $\varepsilon $ -theorem also holds for finite-valued first-order Gödel logics. The methods used to prove the extended first $\varepsilon $ -theorem for infinite-valued Gödel logic suggest applications to theories of arithmetic. (shrink)

We give examples of calculi that extend Gentzen’s sequent calculusLKby unsound quantifier inferences in such a way that derivations lead only to true sequents, and proofs therein are nonelementarily shorter thanLK-proofs.

Rudolf Carnap’s mature work on the logical reconstruction of scientific theories consists of two components. The first is the elimination of the theoretical vocabulary of a theory in terms of its Ramsification. The second is the reintroduction of the theoretical terms through explicit definitions in a language containing an epsilon operator. This paper investigates Carnap’s epsilon-reconstruction of theories in the context of pure mathematics. The main objective here is twofold: first, to specify the epsilon logic underlying his suggested definition of (...) theoretical terms and a suitable choice semantics for it. Second, to analyze whether Carnap’s approach is compatible with a structuralist conception of mathematics. (shrink)

In this paper we show some non-elementary speed-ups in logic calculi: Both a predicative second-order logic and a logic for fixed points of positive formulas are shown to have non-elementary speed-ups over first-order logic. Also it is shown that eliminating second-order cut formulas in second-order logic has to increase sizes of proofs super-exponentially, and the same in eliminating second-order epsilon axioms. These are proved by relying on results due to P. Pudlák.

The epsilon operator is a term-forming operator which replaces quantifiers in ordinary predicate logic. The application of this undervalued formalism has been hampered by the absence of well-behaved proof systems on the one hand, and accessible presentations of its theory on the other. One significant early result for the original axiomatic proof system for the epsilon-calculus is the first epsilon theorem, for which a proof is sketched. The system itself is discussed, also relative to possible semantic interpretations. The problems facing (...) the development of proof-theoretically well-behaved systems are outlined. (shrink)

This paper compares Hilbert’s -terms and Russell’s approach to indefinite descriptions, Russell’s indefinites for short. Despite the fact that both accounts are usually taken to express indefinite descriptions, there is a number of dissimilarities. Specifically, it can be shown that Russell indefinites - expressed in terms of a logical ρ-operator - are not directly representable in terms of their corresponding -terms. Nevertheless, there are two possible translations of Russell indefinites into epsilon logic. The first one is given in a language (...) with classical -terms. The second translation is based on a refined account of epsilon terms, namely indexed -terms. In what follows we briefly outline these approaches both syntactically and semantically and discuss their respective connections; in particular, we establish two equivalence results between the epsilon calculus and the proposed ρ-term approach to Russell’s indefinites. (shrink)

The $$\varepsilon $$ -elimination method of Hilbert’s $$\varepsilon $$ -calculus yields the up-to-date most direct algorithm for computing the Herbrand disjunction of an extensional formula. A central advantage is that the upper bound on the Herbrand complexity obtained is independent of the propositional structure of the proof. Prior (modern) work on Hilbert’s $$\varepsilon $$ -calculus focused mainly on the pure calculus, without equality. We clarify that this independence also holds for first-order logic with equality. Further, we provide upper bounds analyses (...) of the extended first $$\varepsilon $$ -theorem, even if the formalisation incorporates so-called $$\varepsilon $$ -equality axioms. (shrink)

We aim at a conceptually clear and technically smooth investigation of Ackermann’s substitution method [W. Ackermann, Zur Widerspruchsfreiheit der Zahlentheorie, Math. Ann. 117 162–194]. Our analysis provides a direct classification of the provably recursive functions of , i.e. Peano Arithmetic framed in the ε-calculus.

We formulate Hilbert’s epsilon calculus in the context of expansion proofs. This leads to a simplified proof of the epsilon theorems by disposing of the need for prenexification, Skolemisation, and their respective inverse transformations. We observe that the natural notion of cut in the epsilon calculus is associative.

It is known that an epsilon-invariant sentence has a first-order reformulation, although it is not in an explicit form, since, the proof uses the non-constructive interpolation theorem. We make an attempt to describe the explicit meaning of sentences containing epsilon-terms, adopting the strong assumption of their first-order reformulability. We will prove that, if a monadic predicate is syntactically independent from an epsilon-term and if the sentence obtained by substituting the variable of the predicate with the epsilon-term is epsilon-invariant, then the (...) sentence has an explicit first-order reformulation. Finally, we point out that the formula gives a contextual-quantificational meaning for the indefinite descriptions, provided that one accepts Kneebone’s read of epsilon-terms. (shrink)