Gentzen's three consistency proofs for elementary number theory have a common aim that originates from Hilbert's Program, namely, the aim to justify the application of classical reasoning to quantified propositions in elementary number theory. In addition to this common aim, Gentzen gave a “finitist” interpretation to every number-theoretic proposition with his 1935 and 1936 consistency proofs. In the present paper, we investigate the relationship of this interpretation with intuitionism in terms of the debate between the Hilbert School and the Brouwer (...) School over the significance of consistency proofs. First, we argue that the interpretation had the role of responding to a Brouwer-style objection against the significance of consistency proofs. Second, we propose a way of understanding Gentzen's response to this objection from an intuitionist perspective. (shrink)

Drawing upon Martin-Löf’s semantic framework for his constructive type theory, semantic values are assigned also to natural-deduction derivations, while observing the crucial distinction between consequence among propositions and inference among judgements. Derivations in Gentzen’s format with derivable formulae dependent upon open assumptions, stand, it is suggested, for proof-objects, whereas derivations in Gentzen’s sequential format are proof-acts.

The aim of this essay is a criticism of reductionism ? both in its ?static? interpretation (usually referred to as the layer model or level?picture of science) and in its ?dynamic? interpretation (as a theory of the growth of scientific knowledge), with emphasis on the latter ? from the point of view of Popperian fallibilism and Feyerabendian pluralism, but without being committed to the idiosyncrasies of these standpoints. In both aspects of criticism, the rejection is based on the proposal of (...) a global alternative. Hummell and Opp's research programme for the reduction of sociology to psychology is used as a starting?point and taken as the primary object of criticism. Following the introductory Section I, Section II analyses the three crucial notions of Hummell and Opp's research programme ? their explications of the notions of ?sociology?, ?psychology? and the concept of reduction itself ? and criticizes the authors? deficient ?logic of reduction?. Although the ?local? shortcomings of our authors? ?logic of reduction? do not affect reductionism as such, i.e. logically sound versions of reductionism as devised by Kemeny, Nagel, Oppenheim, Putnam, Woodger et al., it is argued that the logical soundness of sophisticated reductionism cannot compensate for its additional epistemological and methodological deficiencies. Section III analyses the ?dynamic? interpretation of reductionism as a particular developmental pattern of scientific growth. It is argued that even reductionism at its best can produce only cumulative progress, thus ?a priori? excluding scientific revolutions which are inevitably counter?inductive as well as counter?reductive. Section IV discusses the philosophical background of modern reductionism, and examines the effects both of reductionism and of anti?reductionistic pluralism on the autonomy of scientific fields. It is argued that pluralistic anti?reductionism undermines spurious claims for autonomy much more effectively than reductionism. As a ?local? improvement of the reductionistic research programme, the replacement of the predominant one?way reductionism by a less restrictive many?way reductionism is proposed. It is argued that the appropriate treatment for an allegedly backward science (say sociology) is not its reduction to an allegedly more advanced science (say psychology) but its non?reductive replacement by new theories (of the same or of another field) that do not incorporate the older ones. As a ?global? alternative to the reduction of sociology to psychology, the frontier?crossing direct application of psychological theories to sociological phenomena is proposed. A plea is made for a pluralistic science without reduction, based on intra? and interscientific criticism as the proper method for the advancement of knowledge. (shrink)

On the basis of a wide range of historical examples various features of axioms are discussed in relation to their use in mathematical practice. A very general framework for this discussion is provided, and it is argued that axioms can play many roles in mathematics and that viewing them as self-evident truths does not do justice to the ways in which mathematicians employ axioms. Possible origins of axioms and criteria for choosing axioms are also examined. The distinctions introduced aim at (...) clarifying discussions in philosophy of mathematics and contributing towards a more refined view of mathematical practice. (shrink)

Logical inferentialism claims that the meaning of the logical constants should be given, not model-theoretically, but by the rules of inference of a suitable calculus. It has been claimed that certain proof-theoretical systems, most particularly, labelled deductive systems for modal logic, are unsuitable, on the grounds that they are semantically polluted and suffer from an untoward intrusion of semantics into syntax. The charge is shown to be mistaken. It is argued on inferentialist grounds that labelled deductive systems are as syntactically (...) pure as any formal system in which the rules define the meanings of the logical constants. (shrink)

This paper is a study of the opening section of Gentzen’s first publication of 1932,Über die Existenz unabhängiger Axiomensysteme zu unendlichen Satzsystemen, a text which shows the relevance of Hertz’s work of the 1920’s for the young Gentzen. In fact, Gentzen borrowed from Hertz the analysis of the notion of consequence, which was given in terms of the rules of thinning (Verdünnung) and cut (Schnitt) on sequents (there called “sentences”(Sätze)). Moreover, following Hertz again, he also judged it necessary to justify (...) the forms of inference of the system by providing a semantics for them, so that it became possible to make precise the informal notion of consequence, and to show that the inference rules adopted are correct and sufficient. (shrink)

Gerhard Gentzen was born on 24 November 1909. In 1929 he moved to Göttingen where he wrote his doctoral thesis, Untersuchungen über das logische Schliessen, under the supervision of P. Bernays. The...

In this note, we will study four implicational logicsB, BI, BB and BBI. In [5], Martin and Meyer proved that a formula is provable inBB if and only if is provable inBBI and is not of the form of » . Though it gave a positive solution to theP - W problem, their method was semantical and not easy to grasp. We shall give a syntactical proof of the syntactical relation betweenBB andBBI logics. It also includes a syntactical proof of (...) Powers and Dwyer's theorem that is proved semantically in [5]. Moreover, we shall establish the same relation betweenB andBI logics asBB andBBI logics. This relation seems to say thatB logic is meaningful, and so we think thatB logic is the weakest among meaningful logics. Therefore, by Theorem 1.1, our Gentzentype system forBI logic may be regarded as the most basic among all meaningful logics. It should be mentioned here that the first syntactical proof ofP - W problem is given by Misao Nagayama [6]. (shrink)

The ancient Greek method of analysis has a rational reconstruction in the form of the tableau method of logical proof. This reconstruction shows that the format of analysis was largely determined by the requirement that proofs could be formulated by reference to geometrical figures. In problematic analysis, it has to be assumed not only that the theorem to be proved is true, but also that it is known. This means using epistemic logic, where instantiations of variables are typically allowed only (...) with respect to known objects. This requirement explains the preoccupation of Greek geometers with questions as to which geometrical objects are ?given?, that is, known or ?data?, as in the title of Euclid's eponymous book. In problematic analysis, constructions had to rely on objects that are known only hypothetically. This seems strange unless one relies on a robust idea of ?unknown? objects in the same sense as the unknowns of algebra. The Greeks did not have such a concept, which made their grasp of the analytic method shaky. (shrink)

“The confusion of a logical with a real predicate,” according to the Critique of Pure Reason, “is almost beyond correction”. Kant did not assert that existence is no predicate, but that it is only a “logical” one, and not a “real” one. Much the same thing has been said about identity, although Kant himself thought it is real and not logical. We have long lacked a rigorous criterion to distinguish real from logical predicates, and hence have not been able to (...) say why the difference matters. This paper has two objects. First it provides a demarcation between real and logical predicates that confirms Kant's dictum that existence is only “logical.” Secondly it states the theory of a “logical” relation of identity. Perhaps this is not the only identity relation. I show only that once it has been precisely defined in the right setting, there are definite answers to a number of disputed questions about identity. Maybe there are other concepts of identity for which different answers are to be given, but I shall not discuss that disagreeable prospect here. A third application concerns the ontological argument. (shrink)

A two-stage procedure is described which induces type-logical grammar lexicons from sentences annotated with skeletal terms of the simply typed lambda calculus. First, a generalized formulae-as-types correspondence is exploited to obtain all the type-logical proofs of the sample sentences from their lambda terms. The resulting lexicons are then optimally unified. The first stage constitutes the semantic bootstrapping (Pinker, Language Learnability and Language Development, Harvard University Press, 1984), while the unification procedure of Buszkowski and Penn represents a first attempt at structure-dependent (...) distributional learning of the syntactic and semantic categories. This effort extends earlier induction procedures (Buszkowski and Penn, 1990, Studia Logica 49, 431–454; Kanazawa, 1998, CSLI Publications and the European Association for Logic, Language and Information) for classical categorial grammar to at first the non-associative Lambek calculus, and then to a large class of type logics enriched by modal operators and structural rules. (shrink)

A two-stage procedure is described which induces type-logical grammar lexicons from sentences annotated with skeletal terms of the simply typed lambda calculus. First, a generalized formulae-as-types correspondence is exploited to obtain all the type-logical proofs of the sample sentences from their lambda terms. The resulting lexicons are then optimally unified. The first stage constitutes the semantic bootstrapping (Pinker, Language Learnability and Language Development, Harvard University Press, 1984), while the unification procedure of Buszkowski and Penn represents a first attempt at structure-dependent (...) distributional learning of the syntactic and semantic categories. This effort extends earlier induction procedures (Buszkowski and Penn, 1990, Studia Logica 49, 431–454; Kanazawa, 1998, CSLI Publications and the European Association for Logic, Language and Information) for classical categorial grammar to at first the non-associative Lambek calculus, and then to a large class of type logics enriched by modal operators and structural rules. (shrink)

A method is described for inducing a type-logical grammar from a sample of bare sentence trees which are annotated by lambda terms, called term-labelled trees . Any type logic from a permitted class of multimodal logics may be specified for use with the procedure, which induces the lexicon of the grammar including the grammatical categories. A first stage of semantic bootstrapping is performed, which induces a general form lexicon from the sample of term-labelled trees using Fulop’s (J Log Lang Inf (...) 14(1):49–86, 2005) procedure. Next we present a two-stage procedure for performing distributional learning by unifying the lexical types that are initially discovered. The first structural unification algorithm in essence unifies the initial family of sets of types so that the resulting grammar will generate all term-labelled trees that follow the usage patterns evident from the learning sample. Further altering the lexical categories to generate a recursively extended language can be accomplished by a second unification. The combined unification algorithm is shown to yield a new type-logical lexicon that extends the learning sample to a possibly infinite (and possibly context-sensitive) language in a principled fashion. Finally, the complete learning strategy is analyzed from the perspective of algorithmic learning theory; the range of the procedure is shown to be a class of term-labelled tree languages which is finitely learnable from good examples (Lange et al in Algorithmic learning theory, Vol 872 of lecture notes in artificial intelligence, Springer, Berlin, pp 423–437), and so is identifiable in the limit as a corollary. (shrink)

The papers where Gerhard Gentzen introduced natural deduction and sequent calculi suggest that his conception of logic differs substantially from the now dominant views introduced by Hilbert, Gödel, Tarski, and others. Specifically, (1) the definitive features of natural deduction calculi allowed Gentzen to assert that his classical system nk is complete based purely on the sort of evidence that Hilbert called ?experimental?, and (2) the structure of the sequent calculi li and lk allowed Gentzen to conceptualize completeness as a question (...) about the relationships among a system's individual rules (as opposed to the relationship between a system as a whole and its ?semantics?). Gentzen's conception of logic is compelling in its own right. It is also of historical interest, because it allows for a better understanding of the invention of natural deduction and sequent calculi. (shrink)

The idea of an ?inversion principle?, and the name itself, originated in the work of Paul Lorenzen in the 1950s, as a method to generate new admissible rules within a certain syntactic context. Some fifteen years later, the idea was taken up by Dag Prawitz to devise a strategy of normalization for natural deduction calculi (this being an analogue of Gentzen's cut-elimination theorem for sequent calculi). Later, Prawitz used the inversion principle again, attributing it with a semantic role. Still working (...) in natural deduction calculi, he formulated a general type of schematic introduction rules to be matched ? thanks to the idea supporting the inversion principle ? by a corresponding general schematic Elimination rule. This was an attempt to provide a solution to the problem suggested by the often quoted note of Gentzen. According to Gentzen ?it should be possible to display the elimination rules as unique functions of the corresponding introduction rules on the basis of certain requirements?. Many people have since worked on this topic, which can be appropriately seen as the birthplace of what are now referred to as ?general elimination rules?, recently studied thoroughly by Sara Negri and Jan von Plato. In this study, we retrace the main threads of this chapter of proof-theoretical investigation, using Lorenzen's original framework as a general guide. (shrink)

In this paper it is shown that addition of certain reductions to the standard cut removing reductions of deductions in prepositional logic makes prepositional logic non-normalizable. From this follows that some provable propositions in prepositional logic has no direct proof.

ABSTRACT This work presents the concepts of translation and conservative translation between logics. By using algebraic semantics we introduce several conservative translations involving the classical propositional calculus and the many-valued calculi of Post and Lukasiewicz.

The connection between the rules and derivations of Gentzen’s calculiNJandLJwill be explained by several steps (i.e., systems), and an analysis of the well-known problems of the connection between reduction steps of normalization and cut elimination, from Zucker (1974) and Urban (2014), will be given.

We introduce new proof systems for propositional logic, simple deduction Frege systems, general deduction Frege systems, and nested deduction Frege systems, which augment Frege systems with variants of the deduction rule. We give upper bounds on the lengths of proofs in Frege proof systems compared to lengths in these new systems. As applications we give near-linear simulations of the propositional Gentzen sequent calculus and the natural deduction calculus by Frege proofs. The length of a proof is the number of lines (...) in the proof. A general deduction Frege proof system provides at most quadratic speedup over Frege proof systems. A nested deduction Frege proof system provides at most a nearly linear speedup over Frege system where by "nearly linear" is meant the ratio of proof lengths is O) where α is the inverse Ackermann function. A nested deduction Frege system can linearly simulate the propositional sequent calculus, the tree-like general deduction Frege calculus, and the natural deduction calculus. Hence a Frege proof system can simulate all those proof systems with proof lengths bounded by O). Also we show that a Frege proof of n lines can be transformed into a tree-like Frege proof of O lines and of height O. As a corollary of this fact we can prove that natural deduction and sequent calculus tree-like systems simulate Frege systems with proof lengths bounded by O. (shrink)

This paper briefly overviews some of the results and research directions. In the area of substructural logics from the last couple of decades. Substructural logics are understood here to include relevance logics, linear logic, variants of Lambek calculi and some other logics that are motivated by the idea of omitting some structural rules or making other structural changes in LK, the original sequent calculus for classical logic.

In a series of papers Ladyman and Presnell raise an interesting challenge of providing a pre-mathematical justification for homotopy type theory. In response, they propose what they claim to be an informal semantics for homotopy type theory where types and terms are regarded as mathematical concepts. The aim of this paper is to raise some issues which need to be resolved for the successful development of their types-as-concepts interpretation.

One of the most important contributions of A. Church to logic is his invention of the lambda calculus. We present the genesis of this theory and its two major areas of application: the representation of computations and the resulting functional programming languages on the one hand and the representation of reasoning and the resulting systems of computer mathematics on the other hand.

Equally surprisingly, Descartes’s paranoid belief was shared by several contemporary mathematicians, among them Isaac Barrow, John Wallis and Edmund Halley. (Huxley 1959, pp. 354-355.) In the light of our fuller knowledge of history it is easy to smile at Descartes. It has even been argued by Netz that analysis was in fact for ancient Greek geometers a method of presenting their results (see Netz 2000). But in a deeper sense Descartes perceived something interesting in the historical record. We are looking (...) in vain in the writings of Greek mathematicians for a full explanation of what this famous method was. And I will argue for an answer to the question why this lacuna is there: Not because Greek geometers wanted to hide this method, but because they did not fully understand it. It is instructive to note the ambivalent attitude of the most rigorous mathematician of the period, Isaac Newton, to the method of analysis. He used it himself in his own mathematical work and in the expositions of that work. Yet when the mathematical push came to physical and cosmological shove, he formulated his Principia entirely in.. (shrink)