The Epsilon Calculus and Herbrand Complexity

Hilbert's ε-calculus is based on an extension of the language of predicate logic by a term-forming operator e _x . Two fundamental results about the ε-calculus, the first and second epsilon theorem, play a rôle similar to that which the cut-elimination theorem plays in sequent calculus. In particular, Herbrand's Theorem is a consequence of the epsilon theorems. The paper investigates the epsilon theorems and the complexity of the elimination procedure underlying their proof, as well as the length of Herbrand disjunctions of existential theorems obtained by this elimination procedure.     

Choice and Logic

There is a little known paradox the solution to which is a guide to a much more thoroughgoing solution to a whole range of classic paradoxes. This is shown in this paper with respect to Berrys Paradox, Heterologicality, Russells Paradox, and the Paradox of Predication, also the Liar and the Strengthened Liar, using primarily the epsilon calculus. The solutions, however, show not only that the first-order predicate calculus derived from Frege is inadequate as a basis for a clear science, and should be replaced with Hilbert and Bernays conservative extension. Standard second-order logic, and quantified propositional logic also must be substantially modified, to incorporate, in the first place, nominalizations of predicates, and whole sentences. And further modifications must be made, so as to insist that predicates are parts of sentences rather than forms of them, and that truth is a property of propositions rather than their sentential expressions. In all, a thorough reworking of what has been called logic in recent years must be undertaken, to make it more fit for use.Portions of this paper have previously been published in Logical Studies, vol. 9, http://www.logic.ru/LogStud/09/No9-06.html, and the Australasian Journal of Logic, vol. 2, http://www.philosophy.unimelb.edu.au/ajl/2004/2004_4.pdf.     

Harmonious logic: Craig’s interpolation theorem and its descendants

Though deceptively simple and plausible on the face of it, Craig’s interpolation theorem (published 50 years ago) has proved to be a central logical property that has been used to reveal a deep harmony between the syntax and semantics of first order logic. Craig’s theorem was generalized soon after by Lyndon, with application to the characterization of first order properties preserved under homomorphism. After retracing the early history, this article is mainly devoted to a survey of subsequent generalizations and applications, especially of many-sorted interpolation theorems. Attention is also paid tomethodological considerations, since the Craig theorem and its generalizations were initially obtained by proof-theoretic arguments while most of the applications are model-theoretic in nature. The article concludes with the role of the interpolation property in the quest for “reasonable” logics extending first-order logic within the framework of abstract model theory. For Bill Craig, with great appreciation for his fundamental contributions to our subject, and for his perennially open, welcoming attitude and fine personality that enhances every encounter.     

Hilbert's epsilon as an operator of indefinite committed choice

Hilbert and Bernays avoided overspecification of Hilbert's ε-operator. They axiomatized only what was relevant for their proof-theoretic investigations. Semantically, this left the ε-operator underspecified. After briefly reviewing the literature on semantics of Hilbert's epsilon operator, we propose a new semantics with the following features: We avoid overspecification (such as right-uniqueness), but admit indefinite choice, committed choice, and classical logics. Moreover, our semantics for the ε simplifies proof search and is natural in the sense that it mirrors some cases of referential interpretation of indefinite articles in natural language.     

Completeness Theorems via the Double Dual Functor

The aim of this paper is to apply properties of the double dual endofunctor on the category of bounded distributive lattices and some extensions thereof to obtain completeness of certain non-classical propositional logics in a unified way. In particular, we obtain completeness theorems for Moisil calculus, n-valued Łukasiewicz calculus and Nelson calculus. Furthermore we show some conservativeness results by these methods. This revised version was published online in June 2006 with corrections to the Cover Date.     

Characterization Classes Defined without Equality

In this paper we mainly deal with first-order languages without equality and introduce a weak form of equality predicate, the so-called Leibniz equality. This equality is characterized algebraically by means of a natural concept of congruence; in any structure, it turns out to be the maximum congruence of the structure. We show that first-order logic without equality has two distinct complete semantics (fll semantics and reduced semantics) related by the reduction operator. The last and main part of the paper contains a series of Birkhoff-style theorems characterizing certain classes of structures defined without equality, not only full classes but also reduced ones.