This introduction to the basic ideas of structural proof theory contains a thorough discussion and comparison of various types of formalization of first-order logic. Examples are given of several areas of application, namely: the metamathematics of pure first-order logic (intuitionistic as well as classical); the theory of logic programming; category theory; modal logic; linear logic; first-order arithmetic and second-order logic. In each case the aim is to illustrate the methods in relatively simple situations and then apply (...) them elsewhere in much more complex settings. There are numerous exercises throughout the text. In general, the only prerequisite is a standard course in first-order logic, making the book ideal for graduate students and beginning researchers in mathematical logic, theoretical computer science and artificial intelligence. For the new edition, many sections have been rewritten to improve clarity, new sections have been added on cut elimination, and solutions to selected exercises have been included. (shrink)

Sequent calculi constitute an interesting and important category of proof systems. They are much less known than axiomatic systems or natural deduction systems are, and they are much less known than they should be. Sequent calculi were designed as a theoretical framework for investigations of logical consequence, and they live up to the expectations completely as an abundant source of meta-logical results. The goal of this book is to provide a fairly comprehensive view of sequent calculi -- including a (...) wide range of variations. The focus is on sequent calculi for various non-classical logics, from intuitionistic logic to relevance logic, through linear and modal logics. A particular version of sequent calculi, the so-called consecution calculi, have seen important new developments in the last decade or so. The invention of new consecution calculi for various relevance logics allowed the last major open problem in the area of relevance logic to be solved positively: pure ticket entailment is decidable. An exposition of this result is included in chapter 9 together with further new decidability results (for less famous systems). A series of other results that were obtained by J. M. Dunn and me, or by me in the last decade or so, are also presented in various places in the book. Some of these results are slightly improved in their current presentation. Obviously, many calculi and several important theorems are not new. They are included here to ensure the completeness of the picture; their original formulations may be found in the referenced publications. This book contains very little about semantics, in general, and about the semantics of non-classical logic in particular. (shrink)

I present an account of truth values for classical logic, intuitionistic logic, and the modal logic S5, in which truth values are not a fundamental category from which the logic is defined, but rather, an idealisation of more fundamental logical features in the proof theory for each system. The result is not a new set of semantic structures, but a new understanding of how the existing semantic structures may be understood in terms of a more fundamental notion of (...) logical consequence. (shrink)

An introduction to category theory as a rigorous, flexible, and coherent modeling language that can be used across the sciences. Category theory was invented in the 1940s to unify and synthesize different areas in mathematics, and it has proven remarkably successful in enabling powerful communication between disparate fields and subfields within mathematics. This book shows that category theory can be useful outside of mathematics as a rigorous, flexible, and coherent modeling language throughout the sciences. Information is inherently (...) dynamic; the same ideas can be organized and reorganized in countless ways, and the ability to translate between such organizational structures is becoming increasingly important in the sciences. Category theory offers a unifying framework for information modeling that can facilitate the translation of knowledge between disciplines. Written in an engaging and straightforward style, and assuming little background in mathematics, the book is rigorous but accessible to non-mathematicians. Using databases as an entry to category theory, it begins with sets and functions, then introduces the reader to notions that are fundamental in mathematics: monoids, groups, orders, and graphs—categories in disguise. After explaining the “big three” concepts of category theory—categories, functors, and natural transformations—the book covers other topics, including limits, colimits, functor categories, sheaves, monads, and operads. The book explains category theory by examples and exercises rather than focusing on theorems and proofs. It includes more than 300 exercises, with solutions. Category Theory for the Sciences is intended to create a bridge between the vast array of mathematical concepts used by mathematicians and the models and frameworks of such scientific disciplines as computation, neuroscience, and physics. (shrink)

Starting from a generalization of the standard axioms for a monoid we present a stepwise development of various, mutually equivalent foundational axiom systems for category theory. Our axiom sets have been formalized in the Isabelle/HOL interactive proof assistant, and this formalization utilizes a semantically correct embedding of free logic in classical higher-order logic. The modeling and formal analysis of our axiom sets has been significantly supported by series of experiments with automated reasoning tools integrated with Isabelle/HOL. We also (...) address the relation of our axiom systems to alternative proposals from the literature, including an axiom set proposed by Freyd and Scedrov for which we reveal a technical issue (when encoded in free logic where free variables range over defined and undefined objects): either all operations, e.g. morphism composition, are total or their axiom system is inconsistent. The repair for this problem is quite straightforward, however. (shrink)

This monograph is a follow up to the author's classic text Boolean-Valued Models and Independence Proofs in Set Theory, providing an exposition of some of the most important results in set theory obtained in the 20th century--the independence of the continuum hypothesis and the axiom of choice. Aimed at research students and academics in mathematics, mathematical logic, philosophy, and computer science, the text has been extensively updated with expanded introductory material, new chapters, and a new appendix on category (...) theory, and includes recent developments in the field. Numerous exercises, along with the enlarged and entirely updated background material, make this an ideal text for students in logic and set theory. (shrink)

When formalizing mathematics in constructive type theories, or more practically in proof assistants such as Coq or Agda, one is often using setoids. In this note we consider two categories of setoids with equality on objects and show, within intensional Martin-Löf type theory, that they are isomorphic. Both categories are constructed from a fixed proof-irrelevant family F of setoids. The objects of the categories form the index setoid I of the family, whereas the definition of arrows differs. (...) The first category has for arrows triples →F)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\,\rightarrow \,F)$$\end{document} where f is an extensional function. Two such arrows are identified if appropriate composition with transportation maps makes them equal. In the second category the arrows are triples 2)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$^2)$$\end{document} where R is a total functional relation between the subobjects F,F↪Σ\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$F, F \hookrightarrow \Sigma $$\end{document} of the setoid sum of the family. This category is simpler to use as the transportation maps disappear. Moreover we also show that the full image of a category along an E-functor into an E-category is a category. (shrink)

This is the first volume on category theory for a broad philosophical readership. It is designed to show the interest and significance of category theory for a range of philosophical interests: mathematics, proof theory, computation, cognition, scientific modelling, physics, ontology, the structure of the world.

The generality of a derivation is an equivalence relation on the set of occurrences of variables in its premises and conclusion such that two occurrences of the same variable are in this relation if and only if they must remain occurrences of the same variable in every generalization of the derivation. The variables in question are propositional or of another type. A generalization of the derivation consists in diversifying variables without changing the rules of inference. This paper examines in the (...) setting of categorial proof theory the conjecture that two derivations with the same premises and conclusions stand for the same proof if and only if they have the same generality. For that purpose generality is defined within a category whose arrows are equivalence relations on finite ordinals, where composition is rather complicated. Several examples are given of deductive systems of derivations covering fragments of logic, with the associated map into the category of equivalence relations of generality. This category is isomorphically represented in the category whose arrows are binary relations between finite ordinals, where composition is the usual simple composition of relations. This representation is related to a classical representation result of Richard Brauer. (shrink)

The generality of a derivation is an equivalence relation on the set of occurrences of variables in its premises and conclusion such that two occurrences of the same variable are in this relation if and only if they must remain occurrences of the same variable in every generalization of the derivation. The variables in question are propositional or of another type. A generalization of the derivation consists in diversifying variables without changing the rules of inference.This paper examines in the setting (...) of categorial proof theory the conjecture that two derivations with the same premises and conclusions stand for the same proof if and only if they have the same generality. For that purpose generality is defined within a category whose arrows are equivalence relations on finite ordinals, where composition is rather complicated. Several examples are given of deductive systems of derivations covering fragments of logic, with the associated map into the category of equivalence relations of generality.This category is isomorphically represented in the category whose arrows are binary relations between finite ordinals, where composition is the usual simple composition of relations. This representation is related to a classical representation result of Richard Brauer. (shrink)

Proof theory and category theory were first drawn together by Lambek some 30 years ago but, until now, the most fundamental notions of category theory have not been explained systematically in terms of proof theory. Here it is shown that these notions, in particular the notion of adjunction, can be formulated in such as way as to be characterised by composition elimination. Among the benefits of these composition-free formulations are syntactical and simple model-theoretical, geometrical (...) decision procedures for the commuting of diagrams of arrows. Composition elimination, in the form of Gentzen's cut elimination, takes in categories, and techniques inspired by Gentzen are shown to work even better in a purely categorical context than in logic. An acquaintance with the basic ideas of general proof theory is relied on only for the sake of motivation, however, and the treatment of matters related to categories is also in general self contained. Besides familiar topics, presented in a novel, simple way, the monograph also contains new results. It can be used as an introductory text in categorical proof theory. (shrink)

This is the third edition of a book originally published in the 1970s; it provides a systematic and nicely organized presentation of the elegant method of using Boolean-valued models to prove independence results. Four things are new in the third edition: background material on Heyting algebras, a chapter on ‘Boolean-valued analysis’, one on using Heyting algebras to understand intuitionistic set theory, and an appendix explaining how Boolean and Heyting algebras look from the perspective of category theory. The book (...) presents results from a number of set theorists and includes an insightful and informative foreword by Dana Scott. Bell's presentation is lively and pleasant to read, and the material is given in a nicely cohesive way.One obvious reason to be interested in independence proofs is that they concern the important question, what is the set-theoretic hierarchy like? The proofs in Bell's book cover some of the most basic and fundamental independence results, such as those concerning the size of the continuum, the independence of the Axiom of Choice from ZF, cardinal collapsing, Souslin's hypothesis, and Martin's Axiom.Since Gödel's incompleteness theorem, it has been known that for any serious candidate list of set-theoretic axioms, there will be statements neither provable nor disprovable from those axioms. What is really interesting, however, and what the independence proofs discussed here show, is how many of the most natural questions about sets are not decided by the standard axioms of ZFC, and how …. (shrink)

Provability, Computability and Reflection.

For more than 60 years, Jim Lambek has been a profoundly inspirational mathematician, with groundbreaking contributions to algebra, category theory, linguistics, theoretical physics, logic and proof theory. This Festschrift was put together on the occasion of his 90th birthday. The papers in it give a good picture of the multiple research areas where the impact of Jim Lambek's work can be felt. The volume includes contributions by prominent researchers and by their students, showing how Jim Lambek's ideas (...) keep inspiring upcoming generations of scholars. (shrink)

Proof Theory of Modal Logic is devoted to a thorough study of proof systems for modal logics, that is, logics of necessity, possibility, knowledge, belief, time, computations etc. It contains many new technical results and presentations of novel proof procedures. The volume is of immense importance for the interdisciplinary fields of logic, knowledge representation, and automated deduction.

In proof-theoretic semantics, model-theoretic validity is replaced by proof-theoretic validity. Validity of formulae is defined inductively from a base giving the validity of atoms using inductive clauses derived from proof-theoretic rules. A key aim is to show completeness of the proof rules without any requirement for formal models. Establishing this for propositional intuitionistic logic raises some technical and conceptual issues. We relate Sandqvist’s (complete) base-extension semantics of intuitionistic propositional logic to categorical proof theory in (...) presheaves, reconstructing categorically the soundness and completeness arguments, thereby demonstrating the naturality of Sandqvist’s constructions. This naturality includes Sandqvist’s treatment of disjunction that is based on its second-order or elimination-rule presentation. These constructions embody not just validity, but certain forms of objects of justifications. This analysis is taken a step further by showing that from the perspective of validity, Sandqvist’s semantics can also be viewed as the natural disjunction in a category of sheaves. (shrink)

Some thirty years ago, two proposals were made concerning criteria for identity of proofs. Prawitz proposed to analyze identity of proofs in terms of the equivalence relation based on reduction to normal form in natural deduction. Lambek worked on a normalization proposal analogous to Prawitz's, based on reduction to cut-free form in sequent systems, but he also suggested understanding identity of proofs in terms of an equivalence relation based on generality, two derivations having the same generality if after generalizing maximally (...) the rules involved in them they yield the same premises and conclusions up to a renaming of variables. These two proposals proved to be extensionally equivalent only for limited fragments of logic. The normalization proposal stands behind very successful applications of the typed lambda calculus and of category theory in the proof theory of intuitionistic logic. In classical logic, however, it did not fare well. The generality proposal was rather neglected in logic, though related matters were much studied in pure category theory in connection with coherence problems, and there are also links to low-dimensional topology and linear algebra. This proposal seems more promising than the other one for the general proof theory of classical logic. (shrink)

In the first section of this paper I define a set of measures for proof complexity, which combine measures in terms of length and space. In the second section these measures are generalized to the broader category of formal texts. In the third section of the paper I outline several applications of the proposed theory.

This comprehensive monograph is a cornerstone in the area of mathematical logic and related fields. Focusing on Gentzen-type proof theory, the book presents a detailed overview of creative works by the author and other 20th-century logicians that includes applications of proof theory to logic as well as other areas of mathematics. 1975 edition.

Language in Action demonstrates the viability of mathematical research into the foundations of categorial grammar, a topic at the border between logic and linguistics. Since its initial publication it has become the classic work in the foundations of categorial grammar. A new introduction to this paperback edition updates the open research problems and records relevant results through pointers to the literature. Van Benthem presents the categorial processing of syntax and semantics as a central component in a more (...) general dynamic logic of information flow, in tune with computational developments in artificial intelligence and cognitive science. Using the paradigm of categorial grammar, he describes the substructural logics driving the dynamics of natural language syntax and semantics. This is a general type-theoretic approach that lends itself easily to proof-theoretic and semantic studies in tandem with standard logic. The emphasis is on a broad landscape of substructural categorial logics and their proof-theoretical and semantic peculiarities. This provides a systematic theory for natural language understanding, admitting of significant mathematical results. Moreover, the theory makes possible dynamic interpretations that view natural languages as programming formalisms for various cognitive activities. (shrink)

We exhibit a bridge between the theory of cellular categories, used in algebraic topology and homological algebra, and the model-theoretic notion of stable independence. Roughly speaking, we show that the combinatorial cellular categories (those where, in a precise sense, the cellular morphisms are generated by a set) are exactly those that give rise to stable independence notions. We give two applications: on the one hand, we show that the abstract elementary classes of roots of Ext studied by Baldwin–Eklof–Trlifaj are (...) stable and tame. On the other hand, we give a simpler proof (in a special case) that combinatorial categories are closed under 2-limits, a theorem of Makkai and Rosický. (shrink)

The proof theory of many-valued systems has not been investigated to an extent comparable to the work done on axiomatizatbility of many-valued logics. Proof theory requires appropriate formalisms, such as sequent calculus, natural deduction, and tableaux for classical (and intuitionistic) logic. One particular method for systematically obtaining calculi for all finite-valued logics was invented independently by several researchers, with slight variations in design and presentation. The main aim of this report is to develop the proof (...) theory of finite-valued first order logics in a general way, and to present some of the more important results in this area. In Systems covered are the resolution calculus, sequent calculus, tableaux, and natural deduction. This report is actually a template, from which all results can be specialized to particular logics. (shrink)

In lieu of an abstract, here is a brief excerpt of the content:Feminist Studies 41, no. 3. © 2015 by Feminist Studies, Inc. 623 Jaye Cee Whitehead, Kath Bassett, Leia Franchini, and Michael Iacolucci “The Proof Is in the Pudding”: How Mental Health Practitioners View the Power of “Sex Hormones” in the Process of Transition In the United States today, popular discourse touts the power of “sex hormones” and hormone receptors in the brain to chemically produce gender expressions (manifested (...) in physical sex traits, behaviors, and attitudes) and identities (a sense of self as feminine or masculine). These accounts range from common assumptions that Western ideals of femininity (such as empathy understanding, cooperative orientation, nurturing behavior) and masculinity (rational/spatial understanding, competitive orientation, violent behavior) are produced by corresponding sex hormones, to studies that reduce complex gender identities and macrosocial economic phenomena to presocial, binary, hormonal processes.1 For sociologists, accounts that reduce complex identities to internal hormonal reactions are problematic for two primary reasons: first, they are inaccurate because they fail to examine how hormonal reactions are embedded in a complex cultural process of meaning and interpretation; second, they operate as bioreductive ideologies that obscure the social power inherent to the process of gender identity construction. In what follows, we extend both of these insights by examining mental health 1. For an example of a hybrid popular-scientific account of the power of sex hormones to destabilize economic structures, see Jon Coates and Joe Herbert, “Endogenous Steroids and Financial Risk Taking on a London Trading Floor,” Proceedings of the National Academy of Sciences 105, no. 16 (April 2008): 6167–72. 624 Whitehead, Bassett, Franchini, and Iacolucci practitioners’ divergent interpretations of the power of sex hormones in the process of gender transition.2 In doing so, we examine the cultural power of sex hormones in crafting gender identities without reproducing reductionist interpretations of trans embodiment. Perhaps what is most perplexing about the way we speak of sex hormones is that we know it is inaccurate to describe these hormones as sexed; scientists have acknowledged since the 1930s that they are neither sex specific in their function, nor in terms of their location in male or female bodies.3 In her extensive historicization of sex hormones, Anne Fausto-Sterling concludes that it is more accurate to call androgen- and estrogen-based hormones, “steroid hormones” as they have functions that are not confined to corresponding sexed bodies. In fact she urges scientists to “break out of the sex hormone straightjacket” and to look at steroids as just one of a number of components that are important to the creation of sex and gender, including environment and experience.4 Scholars also point to an inextricable link between the chemical operation of hormones and the social process of constructing meaning, both at the level of social interaction and macrocultural constructions of sex categories and gender ideologies.5 While brain organization/activation theory attributes sex and gender differences to hormonal interactions within the developing brain, Fausto-Sterling questions the distinction between activation and organization by pointing out how “the brain can respond to hormonal stimuli with anatomical changes…hormonal systems, after all, respond exquisitely to experience, be it in the form of nutrition, stress, or sexual activity (to name but a few possibilities ).”6 Drawing from Elizabeth Grosz, Fausto-Sterling argues that the power of hormones is best understood according to the model of the 2. “Gender transition” is a controversial phrase, as it implies that transgendered individuals who receive hormone therapy are changing identities. We are only using it for lack of clear alternative phrasing, not because we believe body modifications change gender identities. 3. See Anne Fausto-Sterling, Sexing the Body: Gender Politics and the Construction of Sexuality (New York: Basic Books, 2000); Rebecca Jordan-Young, Brainstorm: The Flaws in the Science of Sex Differences (Cambridge, MA: Harvard University Press, 2010); and Nelly Oudshoorn, Beyond the Natural Body: An Archeology of Sex Hormones (New York: Routledge, 1994). 4. Fausto-Sterling, Sexing the Body, 193–94. 5. Fausto-Sterling, Sexing the Body. 6. Ibid., 232. Whitehead, Bassett, Franchini, and Iacolucci 625 Möbius strip, wherein internal components of the self are always connected to and continuous with outer components such as culture and environment.7 In other... (shrink)

We discuss the semantical categories of base and object implicit in the Curry-Howard theory of types and we derive derive logic and, in particular, the comprehension principle in the classical version of the theory. Two results that apply to both the classical and the constructive theory are discussed. First, compositional semantics for the theory does not demand ‘incomplete objects’ in the sense of Frege: bound variables are in principle eliminable. Secondly, the relation of extensional equality for (...) each type is definable in the Curry-Howard theory. (shrink)

When Gödel developed his functional interpretation, also known as the Dialectica interpretation, his aim was to prove consistency of first order arithmetic by reducing it to a quantifier-free theory with finite types. Like other functional interpretations Gödel’s Dialectica interpretation gives rise to category theoretic constructions that serve both as new models for logic and semantics and as tools for analysing and understanding various aspects of the Dialectica interpretation itself. Gödel’s Dialectica interpretation gives rise to the Dialectica categories , in: (...) Contemp. Math., vol. 92, Amer. Math. Soc., Providence, RI, 1989, pp. 47–62] and J.M.E. Hyland in [J.M.E. Hyland, Proof theory in the abstract, Ann. Pure Appl. Logic 114 43–78, Commemorative Symposium Dedicated to Anne S. Troelstra ]). These categories are symmetric monoidal closed and have finite products and weak coproducts, but they are not Cartesian closed in general. We give an analysis of how to obtain weakly Cartesian closed and Cartesian closed Dialectica categories, and we also reflect on what the analysis might tell us about the Dialectica interpretation. (shrink)

We can regard operations that discard information, like specializing to a particular case or dropping the intermediate steps of a proof, as projections, and operations that reconstruct information as liftings. By working with several projections in parallel we can make sense of statements like “Set is the archetypal Cartesian Closed Category”, which means that proofs about CCCs can be done in the “archetypal language” and then lifted to proofs in the general setting. The method works even when our archetypal (...) language is diagrammatical, has potential ambiguities, is not completely formalized, and does not have semantics for all terms. We illustrate the method with an example from hyperdoctrines and another from synthetic differential geometry. (shrink)

Available from UMI in association with The British Library. ;A form of metaphysical inquiry is in this thesis both illustrated in detail and defended against the charge of issuing in statements which lack cognitive content. 'Categorial description' concerns the fundamental features of our conceptual scheme: the categories described are those of substance, accident, cause, space and time. ;Following Aristotle's distinction between primary and secondary substances, these two notions are addressed as equivalent to those individual or particular things and their (...) kinds. A particular thing is characterised as not being capable of occuring in the predicate position in a proposition; and as having criteria or principles of individuation and reidentification. Accidents or properties can appear in the predicate position and do not have criteria of identity. ;Secondary substances, or natural kinds, being a species of property, also fail to have criteria for individuation and reidentification. It follows that the recently revived Aristotelian essentialism, as exhibited in particular in the work of Kripke, fails to correctly characterise the category of natural kinds: in that theory, natural kinds have essential properties which enable individuation and reidentification across possible worlds. ;Efficient causation is described, against the background of the Locke-Hume dispute, as involving the concept of necessary connection between cause and effect. Rejecting the theory of Harre and Madden on causal powers, an approach by Mackie is defended whereby this connection is a reflection of our counterfactual thinking. The possible worlds essentialist approach of Lewis to counterfactuals is rejected too, as inadequate. ;Space and time, spatial and temporal relations, and places and moments in time are approached in terms of the other categories of particular and property. The obscurity of fit between these categories is identified as responsible for many philosophical puzzles concerning space and time: for example, McTaggart's 'proof' of the unreality of time; and the recent debate on the possibility of multiple times and multiple spaces. ;In the final chapter, the logical commitments of categorial description concerning conceptual relativism and the nature of reality in itself are explored. It is argued that, since categories are in large part responsible for the kinds of acts there are, a description of our categories is a description of reality itself. Since our categories do not involve the machinery of possible worlds offered by contemporary essentialist theories, those theories fail to describe reality. (shrink)

Discontinuity refers to the character of many natural language constructions wherein signs differ markedly in their prosodic and semantic forms. As such it presents interesting demands on monostratal computational formalisms which aspire to descriptive adequacy. Pied piping, in particular, is argued by Pollard (1988) to motivate phrase structure-style feature percolation. In the context of categorial grammar, Bach (1981, 1984), Moortgat (1988, 1990, 1991) and others have sought to provide categorial operators suited to discontinuity. These attempts encounter certain difficulties (...) with respect to model theory and/or proof theory, difficulties which the current proposals are intended to resolve.Lambek calculus is complete for interpretation byresiduation with respect to the adjunction operation of groupoid algebras (Buszkowski 1986). In Moortgat and Morrill (1991) it is shown how to give calculi for families of categorial operators, each defined by residuation with respect to an operation of prosodic adjunction (associative, non-associative, or with interactive axioms). The present paper treats discontinuity in this way, by residuation with respect to three adjunctions: + (associative), (.,.) (split-point marking), andW (wrapping) related by the equations 1+s 2+s 3=(s 1,s 3)Ws 2. We show how the resulting methods apply to discontinuous functors, quantifier scope and quantifier scope ambiguity, pied piping, and subject and object antecedent reflexivisation. (shrink)

This volume is the first ever collection devoted to the field of proof-theoretic semantics. Contributions address topics including the systematics of introduction and elimination rules and proofs of normalization, the categorial characterization of deductions, the relation between Heyting's and Gentzen's approaches to meaning, knowability paradoxes, proof-theoretic foundations of set theory, Dummett's justification of logical laws, Kreisel's theory of constructions, paradoxical reasoning, and the defence of model theory. The field of proof-theoretic semantics has existed (...) for almost 50 years, but the term itself was proposed by Schroeder-Heister in the 1980s. Proof-theoretic semantics explains the meaning of linguistic expressions in general and of logical constants in particular in terms of the notion of proof. This volume emerges from presentations at the Second International Conference on Proof-Theoretic Semantics in Tübingen in 2013, where contributing authors were asked to provide a self-contained description and analysis of a significant research question in this area. The contributions are representative of the field and should be of interest to logicians, philosophers, and mathematicians alike. (shrink)

Second-order abstract categorial grammars (de Groote in Association for computational linguistics, 39th annual meeting and 10th conference of the European chapter, proceedings of the conference, pp. 148–155, 2001) and hyperedge replacement grammars (Bauderon and Courcelle in Math Syst Theory 20:83–127, 1987; Habel and Kreowski in STACS 87: 4th Annual symposium on theoretical aspects of computer science. Lecture notes in computer science, vol 247, Springer, Berlin, pp 207–219, 1987) are two natural ways of generalizing “context-free” grammar formalisms for string (...) and tree languages. It is known that the string generating power of both formalisms is equivalent to (non-erasing) multiple context-free grammars (Seki et al. in Theor Comput Sci 88:191–229, 1991) or linear context-free rewriting systems (Weir in Characterizing mildly context-sensitive grammar formalisms, University of Pennsylvania, 1988). In this paper, we give a simple, direct proof of the fact that second-order ACGs are simulated by hyperedge replacement grammars, which implies that the string and tree generating power of the former is included in that of the latter. The normal form for tree-generating hyperedge replacement grammars given by Engelfriet and Maneth (Graph transformation. Lecture notes in computer science, vol 1764. Springer, Berlin, pp 15–29, 2000) can then be used to show that the tree generating power of second-order ACGs is exactly the same as that of hyperedge replacement grammars. (shrink)

The equivalence of (classical) categorial grammars and context-free grammars, proved by Gaifman [4], is a very basic result of the theory of formal grammars (an essentially equivalent result is known as the Greibach normal form theorem [1], [14]). We analyse the contents of Gaifman's theorem within the framework of structure and type transformations. We give a new proof of this theorem which relies on the algebra of phrase structures and exhibit a possibility to justify the key construction (...) used in Gaifman's proof by means of the Lambek calculus of syntactic types [15]. (shrink)

Dennis Schulting offers a thoroughgoing, analytic account of the first half of the Transcendental Deduction of the Categories in the B-edition of Kant's Critique of Pure Reason that is different from existing interpretations in at least one important aspect: its central claim is that each of the 12 categories is wholly derivable from the principle of apperception, which goes against the current view that the Deduction is not a proof in a strict philosophical sense and the standard reading that (...) in the Deduction Kant only gives an account of the global applicability of the categories to experience. This novel approach enables a reappraisal of Kant's controversial claim that transcendental self-consciousness is not only a necessary condition of objective experience but also sufficient for it. The book provides an extensive analysis of Kant's theory of transcendental apperception and also explains why the argument of the Transcendental Deduction is both a regressive and a progressive argument. (shrink)

We present a proof system for a multimode and multimodal logic, which is based on our previous work on modal Martin-Löf type theory. The specification of modes, modalities, and implications between them is given as a mode theory, i.e., a small 2-category. The logic is extended to a lambda calculus, establishing a Curry–Howard correspondence.

The article presents the first results we have obtained studying natural reasoning from a proof-theoretic perspective. In particular we focus our attention on monotonic reasoning. Our system consists of two parts: (i) A Formal Grammar – a multimodal version of classical Categorial Grammar – which while syntactically analysing linguistic expressions given as input, computes semantic information (In particular information about the monotonicity properties of the components of the input string are displayed.); (ii) A simple Natural Logic which derives (...) (monotonicity) inferences using as vehicle the parsed output. The monotonicity markers assigned in the lexicon are propagated through the proofs via a combination of the structural and the logical rules for the unary operators of Multimodal Categorial Grammar (MMCG) [Moo97]. We have chosen to work with an expressive ‘grammar logic’, in order to avoid the use of extra-logical marking devices and extra-logical structural reasoning. Having MMCG as parser, our system is able to make the derivations simply within the logic. This new approach makes the implementation of the theory an easier task. We have implemented the theoretical results, so far obtained, using Grail, a theorem prover for Categorial Grammar Logics [Moo98]. (shrink)

Structural proof theory is a branch of logic that studies the general structure and properties of logical and mathematical proofs. This book is both a concise introduction to the central results and methods of structural proof theory, and a work of research that will be of interest to specialists. The book is designed to be used by students of philosophy, mathematics and computer science. The book contains a wealth of results on proof-theoretical systems, including extensions (...) of such systems from logic to mathematics, and on the connection between the two main forms of structural proof theory - natural deduction and sequent calculus. The authors emphasize the computational content of logical results. A special feature of the volume is a computerized system for developing proofs interactively, downloadable from the web and regularly updated. (shrink)

Algebraic quantum field theory provides a general, mathematically precise description of the structure of quantum field theories, and then draws out consequences of this structure by means of various mathematical tools -- the theory of operator algebras, category theory, etc.. Given the rigor and generality of AQFT, it is a particularly apt tool for studying the foundations of QFT. This paper is a survey of AQFT, with an orientation towards foundational topics. In addition to covering the basics (...) of the theory, we discuss issues related to nonlocality, the particle concept, the field concept, and inequivalent representations. We also provide a detailed account of the analysis of superselection rules by Doplicher, Haag, and Roberts (DHR); and we give an alternative proof of Doplicher and Robert's reconstruction of fields and gauge group from the category of physical representations of the observable algebra. The latter is based on unpublished ideas due to J. E. Roberts and the abstract duality theorem for symmetric tensor *-categories, a self-contained proof of which is given in the appendix. (shrink)

This work is derived from the SERC "Logic for IT" Summer School Conference on Proof Theory held at Leeds University. The contributions come from acknowledged experts and comprise expository and research articles which form an invaluable introduction to proof theory aimed at both mathematicians and computer scientists.

The theory of resistance here elaborated is based on considerations current since the 18th century and concern the proof of reality of the external world. However, what is ignored in the course of these proofs are the social, psychological, and in particular the logical aspects of resistance. The idea of a theory of resistance is inspired by tendencies in the philosophy of technology, as well as other current philosophical and scientific lines of thought that obscure their metaphysical (...) underpinnings, advocating a position of complete achievability of human and natural relations. The theory of resistance seeks to show that resistance is a reflexive term that concerns relations, not objects or those relations that can be expressed in qualities and quantities. Furthermore, this concept has a positioning role, important in epistemological, as well as ethical and anthropological sense. Resistance is a central, although not the sole characteristic of reality. As an ethical category, it is articulated, for example, in the idea of dignity if understood as hostility to mere typologization and subjection to calcu?lation. The theory of resistance does not advocate some existing reality, but limits the domain of validity of constructivist and narrativist theories. (shrink)

Hegel endorsed proofs of the existence of God, and also believed God to be a person. Some of his interpreters ignore these apparently retrograde tendencies, shunning them in favor of the philosopher's more forward-looking contributions. Others embrace Hegel's religious thought, but attempt to recast his views as less reactionary than they appear to be. Robert Williams's latest monograph belongs to a third category: he argues that Hegel's positions in philosophical theology are central to his philosophy writ large. The book is (...) diligently researched, and marshals an impressive amount of textual evidence concerning Hegel's view of the proofs, his theory of personhood, and his views on religious community.Many of... (shrink)

This paper begins a working through of Blair’s (2001) theoretical agenda concerning argumentation schemes and their attendant critical questions, in which we propose a number of solutions to some outstanding theoretical issues. We consider the classification of schemes, their ultimate nature, their role in argument reconstruction, their foundation as normative categories of argument, and the evaluative role of critical questions.We demonstrate the role of schemes in argument reconstruction, and defend a normative account of their nature against specific criticisms due to (...) Pinto (2001). Concerning critical questions, we propose an account on which they are founded in the R.S.A. cogency standard, and develop an account of the relationship between critical questions and burden of proof. Our ultimate aim is to initiate a reconciliation between dialectical and informal logic approaches to the schemes. (shrink)

The possibility of spectrum inversion has been debated since it was raised by Locke and is still discussed because of its implications for functionalist theories of conscious experience . This paper provides a mathematical formulation of the question of spectrum inversion and proves that such inversions, and indeed bijective scramblings of color in general, are logically possible. Symmetries in the structure of color space are, for purposes of the proof, irrelevant. The proof entails that conscious experiences are not (...) identical with functional relations. It leaves open the empirical possibility that functional relations might, at least in part, be causally responsible for generating conscious experiences. Functionalists can propose causal accounts that meet the normal standards for scientific theories, including numerical precision and novel prediction; they cannot, however, claim that, because functional relationships and conscious experiences are identical, any attempt to construct such causal theories entails a category error. (shrink)

An appropriate framework is put forward for the construction of $$\lambda $$ -models with $$\infty $$ -groupoid structure, which we call homotopic $$\lambda $$ -models, through the use of an $$\infty $$ -category with cartesian closure and enough points. With this, we establish the start of a project of generalization of Domain Theory and $$\lambda $$ -calculus, in the sense that the concept of proof (path) of equality of $$\lambda $$ -terms is raised to higher proof (homotopy).

The eta rule for a set A says that an arbitrary element of A is judgementally identical to an element of constructor form. Eta rules are not part of what may be called canonical Martin-Löf type theory. They are, however, justified by the meaning explanations, and a higher-order eta rule is part of that type theory. The main aim of this paper is to clarify this somewhat puzzling situation. It will be argued that lower-order eta rules do not, (...) whereas the higher-order eta rule does, accord with the understanding of judgemental identity as definitional identity. A subsidiary aim is to clarify precisely what an eta rule is. This will involve showing how such rules relate to various other notions of type theory, proof theory, and category theory. (shrink)

This paper considers a topos-theoretic structure for the interpretation of co-constructive logic for proofs and refutations following Trafford :22–40, 2015). It is notoriously tricky to define a proof-theoretic semantics for logics that adequately represent constructivity over proofs and refutations. By developing abstractions of elementary topoi, we consider an elementary topos as structure for proofs, and complement topos as structure for refutation. In doing so, it is possible to consider a dialogue structure between these topoi, and also control their relation (...) such that classical logic is simulated where proofs and refutations are conclusive. (shrink)

Proof-theoretical notions and techniques, developed on the basis of sentential/symbolic representations of formal proofs, are applied to Euler diagrams. A translation of an Euler diagrammatic system into a natural deduction system is given, and the soundness and faithfulness of the translation are proved. Some consequences of the translation are discussed in view of the notion of free ride, which is mainly discussed in the literature of cognitive science as an account of inferential efficacy of diagrams. The translation enables us (...) to formalize and analyze free ride in terms of proof theory. The notion of normal form of Euler diagrammatic proofs is investigated, and a normalization theorem is proved. Some consequences of the theorem are further discussed: in particular, an analysis of the structure of normal diagrammatic proofs; a diagrammatic counterpart of the usual subformula property; and a characterization of diagrammatic proofs compared with natural deduction proofs. (shrink)

Working in homotopy type theory, we provide a systematic study of homotopy limits of diagrams over graphs, formalized in the Coq proof assistant. We discuss some of the challenges posed by this approach to the formalizing homotopy-theoretic material. We also compare our constructions with the more classical approach to homotopy limits via fibration categories.