This paper presents a systematic study of the prehistory of the traditional subsystems of second-order arithmetic that feature prominently in the reverse mathematics program of Friedman and Simpson. We look in particular at: (i) the long arc from Poincar\'e to Feferman as concerns arithmetic definability and provability, (ii) the interplay between finitism and the formalization of analysis in the lecture notes and publications of Hilbert and Bernays, (iii) the uncertainty as to the constructive status of principles equivalent to Weak K\"onig's (...) Lemma, and (iv) the large-scale intellectual backdrop to arithmetical transfinite recursion in descriptive set theory and its effectivization by Borel, Lusin, Addison, and others. (shrink)

ABSTRACT Theories of sets such as Zermelo Fraenkel set theory are usually presented as the combination of two distinct kinds of principles: logical and set-theoretic principles. The set-theoretic principles are imposed ‘on top’ of first-order logic. This is in agreement with a traditional view of logic as universally applicable and topic neutral. Such a view of logic has been rejected by the intuitionists, on the ground that quantification over infinite domains requires the use of intuitionistic rather than classical logic. In (...) the following, I consider constructive set theories, which use intuitionistic rather than classical logic, and argue that they manifest a distinctive interdependence or an entanglement between sets and logic. In fact, Martin-Löf type theory identifies fundamental logical and set-theoretic notions. Remarkably, one of the motivations for this identification is the thought that classical quantification over infinite domains is problematic, while intuitionistic quantification is not. The approach to quantification adopted in Martin-Löf’s type theory is subtly interconnected with its predicativity. I conclude by recalling key aspects of an approach to predicativity inspired by Poincaré, which focuses on the issue of correct quantification over infinite domains and relate it back to Martin-Löf type theory. (shrink)

In this paper we propose a way to deal with natural language inference by implementing Modern Type Theoretical Semantics in the proof assistant Coq. The paper is a first attempt to deal with NLI and natural language reasoning in general by using the proof assistant technology. Valid NLIs are treated as theorems and as such the adequacy of our account is tested by trying to prove them. We use Luo’s Modern Type Theory with coercive subtyping as the formal language into (...) which we translate natural language semantics, and we further implement these semantics in the Coq proof assistant. It is shown that the use of a MTT with an adequate subtyping mechanism can give us a number of promising results as regards NLI. Specifically, it is shown that a number of inference cases, i.e. quantifiers, adjectives, conjoined noun phrases and temporal reference among other things can be successfully dealt with. It is then shown, that even though Coq is an interactive and not an automated theorem prover, automation of all of the test examples is possible by introducing user-defined automated tactics. Lastly, the paper offers a number of innovative approaches to NL phenomena like adjectives, collective predication, comparatives and factive verbs among other things, contributing in this respect to the theoretical study of formal semantics using MTTs. (shrink)

In this paper we present a study of adjectival/adverbial modification using modern type theories, i.e. type theories within the tradition of Martin-Löf. We present an account of various issues concerning adjectival/adverbial modification and argue that MTTs can be used as an adequate language for interpreting NL semantics. MTTs are not only expressive enough to deal with a range of modification phenomena, but are furthermore well-suited to perform reasoning tasks that can be easily implemented given their proof-theoretic nature. In MTT-semantics, common (...) nouns are interpreted as types rather than predicates. Therefore, in order to capture the semantics of adjectives adequately, one needs to meet the challenge of modeling CNs modified by adjectives as types. To explicate that this can be done successfully, we first look at the mainstream classification of adjectives, i.e. intersective, subsective and non-subsective adjectives. There, we show that the rich type structure available in MTTs, along with a suitable subtyping framework, offers an adequate mechanism to model these cases. In particular, this modelling naturally takes care of the characterising inferences associated with each class of adjectives. Then, more advanced issues on adjectival modification are discussed: degree adjectives, comparatives and multidimensional adjectives. There, it is shown that the use of indexed types can be usefully applied in order to deal with these cases. In the same vein, the issue of adverbial modification is discussed. We study two general typings for sentence and VP adverbs respectively. It is shown that the rich type structure in MTTs further provides useful organisational mechanisms in giving formal semantics for adverbs. In particular, we discuss the use of \-types to capture the veridicality/non-veridicality distinction and further discuss cases of intensional adverbs using the type theoretic notion of context. We also look at manner, subject and speech act adverbials and propose solutions using MTTs. Finally, we show that the current proof technology can help mechanically check the associated inferences. A number of our proposals concerning adjectival and adverbial modification have been formalised in the proof assistant Coq and many of the associated inference patterns are checked to be correctly captured. (shrink)

In this contribution, we try to show that traditional Aristotelian logic can be useful (in a non-trivial way) for computational thinking. To achieve this objective, we argue in favor of two statements: (i) that traditional logic is not classical and (ii) that logic programming emanating from traditional logic is not classical logic programming.

Here, I offer a rapid overview of the theory of metaphor, in order to situate the contributions to this volume in relation to one another and within the field more generally.

: The Hamblin-Karttunen approach has led to many insights about questions in English. In this article the results of this rule-by-rule tradition are reconsidered from a crosslinguistic perspective. Starting from the type-driven XLS theory developed in Bittner (1994a, b), it is argued that evidence from simple questions (in English, Polish, Lakhota and Warlpiri) leads to certain revisions. The revised XLS theory then immediately generalizes to complex questions — including scope marking (Hindi), questions with quantifiers (English) and multiple wh-questions (English, Hindi, (...) Japanese). Eliminating language- and construction-specific information from the compositional rules, in favor of universal semantic filters, leads to analyses that not only generalize across unrelated languages but are also empirically more accurate, not less. (shrink)

Crosslinguistically, causative constructions conform to the following generalization: If the causal relation is syntactically concealed, then it is semantically direct. Concealed causatives span a wide syntactic spectrum, ranging from resultative complements in English to causative subjects in Miskitu. A unified type-driven theory is proposed which attributes the understood causal relation—and other elements of constructional meaning—to type lifting operations predictably licensed by type mismatch at LF. The proposal has far-reaching theoretical implications not only for the theory of compositionality and causation, but (...) also for the underlying theory of events, space, and time, in natural language discourse. (shrink)

This paper reports on an exploration of Boolos’ Curious Inference, using higher-order automated theorem provers (ATPs). Surprisingly, only suitable shorthand notations had to be provided by hand for ATPs to find a short proof. The higher-order lemmas required for constructing a short proof are automatically discovered by the ATPs. Given the observations and suggestions in this paper, full proof automation of Boolos’ and related examples now seems to be within reach of higher-order ATPs.

We present an embedding of quantified multimodal logics into simple type theory and prove its soundness and completeness. A correspondence between QKπ models for quantified multimodal logics and Henkin models is established and exploited. Our embedding supports the application of off-the-shelf higher-order theorem provers for reasoning within and about quantified multimodal logics. Moreover, it provides a starting point for further logic embeddings and their combinations in simple type theory.

We study straightforward embeddings of propositional normal multimodal logic and propositional intuitionistic logic in simple type theory. The correctness of these embeddings is easily shown. We give examples to demonstrate that these embeddings provide an effective framework for computational investigations of various non-classical logics. We report some experiments using the higher-order automated theorem prover LEO-II.

It is often claimed that the theory of function levels proposed by Frege in Grundgesetze der Arithmetik anticipates the hierarchy of types that underlies Church’s simple theory of types. This claim roughly states that Frege presupposes a type of functions in the sense of simple type theory in the expository language of Grundgesetze. However, this view makes it hard to accommodate function names of two arguments and view functions as incomplete entities. I propose and defend an alternative interpretation of first-level (...) function names in Grundgesetze into simple type-theoretic open terms rather than into closed terms of a function type. This interpretation offers a still unhistorical but more faithful type-theoretic approximation of Frege’s theory of levels and can be naturally extended to accommodate second-level functions. It is made possible by two key observations that Frege’s Roman markers behave essentially like open terms and that Frege lacks a clear criterion for distinguishing between Roman markers and function names. (shrink)

A semantic embedding of quantified conditional logic in classical higher-order logic is utilized for reducing cut-elimination in the former logic to existing results for the latter logic. The presented embedding approach is adaptable to a wide range of other logics, for many of which cut-elimination is still open. However, special attention has to be payed to cut-simulation, which may render cut-elimination as a pointless criterion.

We investigate several approaches to resolution based automated theoremproving in classical higher-order logic (based on Church's simply typedλ-calculus) and discuss their requirements with respect to Henkincompleteness and full extensionality. In particular we focus on Andrews' higher-order resolution (Andrews 1971), Huet's constrained resolution (Huet1972), higher-order E-resolution, and extensional higher-order resolution(Benzmüller and Kohlhase 1997). With the help of examples we illustratethe parallels and differences of the extensionality treatment of these approachesand demonstrate that extensional higher-order resolution is the sole approach thatcan completely avoid (...) additional extensionality axioms. (shrink)

Because the label "computing and philosophy" can seem like an ad hoc attempt to tie computing to philosophy, it is important to explain why it is not, what it studies (or does) and how it differs from research in, say, "computing and history," or "computing and biology". The American Association for History and Computing is "dedicated to the reasonable and productive marriage of history and computer technology for teaching, researching and representing history through scholarship and public history" (http://theaahc.org). More pervasive, (...) work in computing and biology enjoys the convenient name of "bioinformatics...the science of using information to understand biology..., a subset of the larger field of computational biology, the application of quantitative analytical techniques in modeling biological systems" (http://oreilly.com/catalog/bioskills/chapter/ ch01.html). The recent venture of the Association for Computing Machinery and the Institute of Electrical and Electronics Engineers to publish the Transactions on Computational Biology and Bioinformatics (TCBB) bears witness to the reach of computing and biology and underscores its objective. TCBB intends to report "archival research results related to the algorithmic, mathematical, statistical, and computational methods that are central in bioinformatics and computational biology; the development and testing of effective computer programs in bioinformatics; the development and optimization of biological databases; and important biological results that are obtained from the use of these methods, programs, and databases" (http://tcbb.acm.org). In the case of "computing and history" and "bioinformatics," each discipline stands in a particular relationship to computers that raises questions unique to itself. But both are devoted to the development of computational tools to aid discovery.. (shrink)

In this paper it is shown how a partial semantics for presuppositions can be given which is empirically more satisfactory than its predecessors, and how this semantics can be integrated with a technically sound, compositional grammar in the Montagovian fashion. Additionally, it is argued that the classical objection to partial accounts of presupposition projection, namely that they lack “flexibility,” is based on a misconception. Partial logics can give rise to flexible predictions without postulating any ad hoc ambiguities. Finally, it is (...) shown how the partial foundation can be combined with a dynamic system of common-ground maintenance to account for accommodation. (shrink)

In this paper it is shown how a partial semantics for presuppositions can be given which is empirically more satisfactory than its predecessors, and how this semantics can be integrated with a technically sound, compositional grammar in the Montagovian fashion. Additionally, it is argued that the classical objection to partial accounts of presupposition projection, namely that they lack “flexibility,” is based on a misconception. Partial logics can give rise to flexible predictions without postulating any ad hoc ambiguities. Finally, it is (...) shown how the partial foundation can be combined with a dynamic system of common-ground maintenance to account for accommodation. (shrink)

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.

The technical contribution of this paper is threefold.First we show how to encode functionals in a ‘flat’ applicative structure by adding oracles to untyped λ-calculus and mimicking the applicative behaviour of the functionals with an impredicatively defined reduction relation. The main achievement here is a Church-Rosser result for the extended reduction relation.Second, by combining the previous result with the model construction based on partial equivalence relations, we show how to extend a λ-closed simple type structure to a model of the (...) polymorphic λ-calculus.Third, we specialize the previous result to a counter model against a simple minimization. This minimization is realized by a bar recursive functional, which contrasts the results of Spector and Girard which imply that the bar recursive functions are exactly those that are definable in the polymorphic λ-calculus. As a spin-off, we obtain directly the non-conservativity of the extensions of Gödel's T with bar recursion, fan functional, and Luckhardt's minimization functional, respectively. For the latter two extensions these results are new. (shrink)

Using recent results in topos theory, two systems of higher-order logic are shown to be complete with respect to sheaf models over topological spaces- so -called "topological semantics." The first is classical higher-order logic, with relational quantification of finitely high type; the second system is a predicative fragment thereof with quantification over functions between types, but not over arbitrary relations. The second theorem applies to intuitionistic as well as classical logic.

Steve Awodey and Erich H. Reck. Completeness and Categoricity: 19th Century Axiomatics to 21st Century Senatics.

This paper is the second in a two-part series in which we discuss several notions of completeness for systems of mathematical axioms, with special focus on their interrelations and historical origins in the development of the axiomatic method. We argue that, both from historical and logical points of view, higher-order logic is an appropriate framework for considering such notions, and we consider some open questions in higher-order axiomatics. In addition, we indicate how one can fruitfully extend the usual set-theoretic semantics (...) so as to shed new light on the relevant strengths and limits of higher-order logic. (shrink)

We show that basic hybridization (adding nominals and @ operators) makes it possible to give straightforward Henkin-style completeness proofs even when the modal logic being hybridized is higher-order. The key ideas are to add nominals as expressions of type t, and to extend to arbitrary types the way we interpret $@_i$ in propositional and first-order hybrid logic. This means: interpret $@_i\alpha _a$ , where $\alpha _a$ is an expression of any type $a$ , as an expression of type $a$ that (...) rigidly returns the value that $\alpha_a$ receives at the i-world. The axiomatization and completeness proofs are generalizations of those found in propositional and first-order hybrid logic, and (as is usual inhybrid logic) we automatically obtain a wide range of completeness results for stronger logics and languages. Our approach is deliberately low-tech. We don’t, for example, make use of Montague’s intensional type s, or Fitting-style intensional models; we build, as simply as we can, hybrid logicover Henkin’s logic. (shrink)

We show that basic hybridization makes it possible to give straightforward Henkin-style completeness proofs even when the modal logic being hybridized is higher-order. The key ideas are to add nominals as expressions of type t, and to extend to arbitrary types the way we interpret \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$@_i$\end{document} in propositional and first-order hybrid logic. This means: interpret \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$@_i\alpha _a$\end{document}, where \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} (...) \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\alpha _a$\end{document} is an expression of any type \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$a$\end{document}, as an expression of type \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$a$\end{document} that rigidly returns the value that \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\alpha_a$\end{document} receives at the i-world. The axiomatization and completeness proofs are generalizations of those found in propositional and first-order hybrid logic, and we automatically obtain a wide range of completeness results for stronger logics and languages. Our approach is deliberately low-tech. We don’t, for example, make use of Montague’s intensional type s, or Fitting-style intensional models; we build, as simply as we can, hybrid logicover Henkin’s logic. (shrink)

§0. Alonzo Church's contributions to philosophy and to that most philosophical part of logic, intensional logic, are impressive indeed. He wrote relatively few papers actually devoted to specifically philosophical issues, as distinguished from related technical work in logic. Many of his contributions appear in reviews for The Journal of Symbolic Logic, and it can hardly be maintained that one finds there a “philosophical system”. But there occur a clearly articulated and powerful methodology, terse arguments, often of “crushing cogency”, and philosophical (...) observations of the first importance.Many of the less formal philosophical contributions center around questions concerning meaning, but there are important clarifications and insights into matters of the epistemology and ontology of the sciences, especially the formal sciences.1.1. The logistic method. Church's writings on philosophical matters exhibit an unwavering commitment to what he called the “logistic method”. The term did not catch on and now one would just speak of “formalization”. The use of these ideas is now so common and familiar among logicians and logically-oriented philosophers that they are simply taken for granted. But they deserve to be celebrated and re-emphasized, for there are philosophers who seriously underestimate and even consciously reject these techniques. (shrink)

This paper introduces Richard Montague's theory of determiner phrases to the philosophically oriented readers who are familiar with Russell's traditional treatment. Determiner phrases include not only quantifier phrases in the narrow sense, such as every man, some woman, and nothing, but also DP conjunctions such as Adam and Betty and Adam or Betty, and even proper names such as Adam and Betty. Montague treats all determiner phrases as belonging to type t, i.e., the type of functions from properties of individuals (...) to truth values. This paper also introduces the simply typed lambda-calculus for the explication of Montague's theory. Two major problems with Montague's theory, one more philosophical and the other more linguistic, are discussed. (shrink)

This three-part chapter explores a higher-order logic we call ‘Classicism’, which extends a minimal classical higher-order logic with further axioms which guarantee that provable coextensiveness is sufficient for identity. The first part presents several different ways of axiomatizing this theory and makes the case for its naturalness. The second part discusses two kinds of extensions of Classicism: some which take the view in the direction of coarseness of grain (whose endpoint is the maximally coarse-grained view that coextensiveness is sufficient for (...) identity), and some which take the view in the direction of fineness of grain (whose endpoint is the maximally fine-grained theory containing all distinctness claims compatible with Classicism). The third part introduces some techniques for constructing models of Classicism, and uses them to prove the consistency of many of the extensions of Classicism introduced in the second part. (shrink)

Universals are putative objects like wisdom, morality, redness, etc. Although we believe in properties (which, we argue, are not a kind of object), we do not believe in universals. However, a number of ordinary, natural language constructions seem to commit us to their existence. In this paper, we provide a fictionalist theory of universals, which allows us to speak as if universals existed, whilst denying that any really do.

Along with offering an historically-oriented interpretive reconstruction of the syntax of PM ( rst ed.), I argue for a certain understanding of its use of propositional function abstracts formed by placing a circum ex on a variable. I argue that this notation is used in PM only when de nitions are stated schematically in the metalanguage, and in argument-position when higher-type variables are involved. My aim throughout is to explain how the usage of function abstracts as “terms” (loosely speaking) is (...) not inconsistent with a philosophy of types that does not think of propositional functions as mind- and language-independent objects, and adopts a nominalist/substitutional semantics instead. I contrast PM’s approach here both to function abstraction found in the typed λ-calculus, and also to Frege’s notation for functions of various levels that forgoes abstracts altogether, between which it is a kind of intermediary. (shrink)

Nonindexical Context-Dependence and the Interpretation as Abduction Approach Inclusive nonindexical context-dependence occurs when the preferred interpretation of an utterance implies its lexically-derived meaning. It is argued that the corresponding processes of free or lexically mandated enrichment can be modeled as abductive inference. A form of abduction is implemented in Simple Type Theory on the basis of a notion of plausibility, which is in turn regarded a preference relation over possible worlds. Since a preordering of doxastic alternatives taken for itself only (...) amounts to a relatively vacuous ad hoc model, it needs to be combined with a rational way of learning from new evidence. Lexicographic upgrade is implemented as an example of how an agent might revise his plausibility ordering in light of new evidence. Various examples are given how this apparatus may be used to model the contextual resolution of context-dependent or semantically incomplete utterances. The described form of abduction is limited and merely serves as a proof of concept, but the idea in general has good potential as one among many ways to build a bridge between semantics and pragmatics since inclusive context-dependence is ubiquitous. (shrink)

Higher-order logic, with its type-theoretic apparatus known as the simple theory of types (STT), has increasingly come to be employed in theorizing about properties, relations, and states of affairs—or ‘intensional entities’ for short. This paper argues against this employment of STT and offers an alternative: ordinal type theory (OTT). Very roughly, STT and OTT can be regarded as complementary simplifications of the ‘ramified theory of types’ outlined in the Introduction to Principia Mathematica (on a realist reading). While STT, understood as (...) a theory of intensional entities, retains the Fregean division of properties and relations into a multiplicity of categories according to their adicities and ‘input types’ and discards the division of intensional entities into different ‘orders’, OTT takes the opposite approach: it retains the hierarchy of orders (though with some modifications) and discards the categorisation of properties and relations according to their adicities and input types. In contrast to STT, this latter approach avoids intensional counterparts of the Epimenides and related paradoxes. Fundamental intensional entities lie at the base of the proposed hierarchy and are also given a prominent part to play in the individuation of non-fundamental intensional entities. (shrink)

Predicativity is a notable example of fruitful interaction between philosophy and mathematical logic. It originated at the beginning of the 20th century from methodological and philosophical reflections on a changing concept of set. A clarification of this notion has prompted the development of fundamental new technical instruments, from Russell's type theory to an important chapter in proof theory, which saw the decisive involvement of Kreisel, Feferman and Schütte. The technical outcomes of predica-tivity have since taken a life of their own, (...) but have also produced a deeper understanding of the notion of predicativity, therefore witnessing the " light logic throws on problems in the foundations of mathematics. " (Feferman 1998, p. vii) Predicativity has been at the center of a considerable part of Feferman's work: over the years he has explored alternative ways of explicating and analyzing this notion and has shown that predicative mathematics extends much further than expected within ordinary mathematics. The aim of this note is to outline the principal features of predicativity, from its original motivations at the start of the past century to its logical analysis in the 1950-60's. The hope is to convey why predicativity is a fascinating subject, which has attracted Feferman's attention over the years. (shrink)

Philosophy Compass, Volume 17, Issue 2, February 2022.

In this paper it is shown how simple texts that can be parsed in a Lambek Categorial Grammar can also automatically be provided with a semantics in the form of a Discourse Representation Structure in the sense of Kamp [1981]. The assignment of meanings to texts uses the Curry-Howard-Van Benthem correspondence.

The quest for a most general framework supporting universal reasoning is very prominently represented in the works of Leibniz. He envisioned a scientia generalis founded on a characteristica universalis, that is, a most universal formal language in which all knowledge about the world and the sciences can be encoded. A quick study of the survey literature on logical formalisms suggests that quite the opposite to Leibniz’ dream has become reality. Instead of a characteristica universalis, we are today facing a very (...) rich and heterogenous zoo of different logical systems, and instead of converging towards a single superior logic, this logic zoo is further expanding, eventually even at accelerated pace. As a consequence, the unified vision of Leibniz seems farther away than ever before. However, there are also some promising initiatives to counteract these diverging developments. Attempts at unifying approaches to logic include categorial logic algebraic logic and coalgebraic logic. (shrink)

A shallow semantic embedding of an intensional higher-order modal logic in Isabelle/HOL is presented. IHOML draws on Montague/Gallin intensional logics and has been introduced by Melvin Fitting in his textbook Types, Tableaus and Gödel’s God in order to discuss his emendation of Gödel’s ontological argument for the existence of God. Utilizing IHOML, the most interesting parts of Fitting’s textbook are formalized, automated and verified in the Isabelle/HOL proof assistant. A particular focus thereby is on three variants of the ontological argument (...) which avoid the modal collapse, which is a strongly criticized side-effect in Gödel’s resp. Scott’s original work. (shrink)

Prominent constructive theories of sets as Martin-Löf type theory and Aczel and Myhill constructive set theory, feature a distinctive form of constructivity: predicativity. This may be phrased as a constructibility requirement for sets, which ought to be finitely specifiable in terms of some uncontroversial initial “objects” and simple operations over them. Predicativity emerged at the beginning of the 20th century as a fundamental component of an influential analysis of the paradoxes by Poincaré and Russell. According to this analysis the paradoxes (...) are caused by a vicious circularity in definitions; adherence to predicativity was therefore proposed as a systematic method for preventing such problematic circularity. In the following, I sketch the origins of predicativity, review the fundamental contributions by Russell and Weyl and look at modern incarnations of this notion. (shrink)

This collection of papers, celebrating the contributions of Swedish logician Dag Prawitz to Proof Theory, has been assembled from those presented at the Natural Deduction conference organized in Rio de Janeiro to honour his seminal research. Dag Prawitz’s work forms the basis of intuitionistic type theory and his inversion principle constitutes the foundation of most modern accounts of proof-theoretic semantics in Logic, Linguistics and Theoretical Computer Science. The range of contributions includes material on the extension of natural deduction with higher-order (...) rules, as opposed to higher-order connectives, and a paper discussing the application of natural deduction rules to dealing with equality in predicate calculus. The volume continues with a key chapter summarizing work on the extension of the Curry-Howard isomorphism, via methods of category theory that have been successfully applied to linear logic, as well as many other contributions from highly regarded authorities. With an illustrious group of contributors addressing a wealth of topics and applications, this volume is a valuable addition to the libraries of academics in the multiple disciplines whose development has been given added scope by the methodologies supplied by natural deduction. The volume is representative of the rich and varied directions that Prawitz work has inspired in the area of natural deduction. (shrink)

In this book, Zalta attempts to lay the axiomatic foundations of metaphysics by developing and applying a (formal) theory of abstract objects. The cornerstones include a principle which presents precise conditions under which there are abstract objects and a principle which says when apparently distinct such objects are in fact identical. The principles are constructed out of a basic set of primitive notions, which are identified at the end of the Introduction, just before the theorizing begins. The main reason for (...) producing a theory which defines a logical space of abstract objects is that it may have a great deal of explanatory power. It is hoped that the data explained by means of the theory will be of interest to pure and applied metaphysicians, logicians and linguists, and pure and applied epistemologists. (shrink)

Zaionc, M., λ-Definability on free algebras, Annals of Pure and Applied Logic 51 279-300. A λ-language over a simple type structure is considered. There is a natural isomorphism which identifies free algebras with nonempty second-order types. If A is a free algebra determined by the signature SA = [α1,...,αn], then by a type τA we mean τ1,...,τn→0 where τi=0αi→0. It can be seen that closed terms of the type τA reflex constructions in the algebra A. Therefore any term of the (...) type n→τA defines some n-ary mapping in algebra A. The problem is to characterize λ-definable mappings in any free algebra. It is proved that the set of λ-definable operations is the minimal set that contains constant functions and projections and is closed under composition and limited recursion. This result is a generalization of the result of Schwichtenberg and Statman which characterize the λ-definable functions over the natural number type →, i.e algebra [1, 0], as well as of the result of Zaionc for λ-definable word operations over type n→, i.e algebra [1,...,1,0], and of the results about λ-definable tree operations , i.e in algebra [2, 0]. Some of the examples in Section 5 are based on a publication of Zaionc. (shrink)