This article presents an historical and conceptual overview on different approaches to logical abstraction. Two main trends concerning abstraction in the history of logic are highlighted, starting from the logical notions of concept and function. This analysis strictly relates to the philosophical discussion on the nature of abstract objects. I develop this issue further with respect to the procedure of abstraction involved by (typed) λ-systems, focusing on the crucial change about meaning and predicability. In particular, the analysis of the nature (...) of logical types in the context of Constructive Type Theory allows elucidation of the role of the previously introduced notions. Finally, the connection to the analysis of abstraction in computer science is drawn, and the methodological contribution provided by the notion of information is considered, showing its conceptual and technical relevance. Future research shall focus on the notion of information in distributed systems, analysing the paradigm of information hiding in dependent type theories. (shrink)

It is well known that the circumflex notation used by Russell and Whitehead to form complex function names in Principia Mathematica played a role in inspiring Alonzo Church's “lambda calculus” for functional logic developed in the 1920s and 1930s. Interestingly, earlier unpublished manuscripts written by Russell between 1903–1905—surely unknown to Church—contain a more extensive anticipation of the essential details of the lambda calculus. Russell also anticipated Schönfinkel's combinatory logic approach of treating multiargument functions as functions having other functions as value. (...) Russell’s work in this regard seems to have been largely inspired by Frege’s theory of functions and “value-ranges”. This system was discarded by Russell due to his abandonment of propositional functions as genuine entities as part of a new tack for solving Russell’s paradox. In this article, I explore the genesis and demise of Russell’s early anticipation of the lambda calculus. (shrink)

Monism is the claim that only one object exists. While few contemporary philosophers endorse monism, it has an illustrious history – stretching back to Bradley, Spinoza and Parmenides. In this paper, I show that plausible assumptions about the higher-order logic of property identity entail that monism is true. Given the higher-order framework I operate in, this argument generalizes: it is also possible to establish that there is a single property, proposition, relation, etc. I then show why this form of monism (...) is inconsistent; because all propositions are identical, p is identical to ~p – and so they have the same truth-value. At least one of the assumptions that generate higher-order monism must be rejected. (shrink)

The present PhD dissertation aims to examine the relation between modality and change in Aristotle’s metaphysics. -/- On the one hand, Aristotle supports his modal realism (i.e., worldly objects have modal properties - potentialities and essences - that ground the ascriptions of possibility and necessity) by arguing that the rejection of modal realism makes change inexplicable, or, worse, banishes it from the realm of reality. On the other hand, the Stagirite analyses processes by means of modal notions (‘change is the (...) actuality of what is virtual insofar as it is virtual’). In other words: to grasp what change is, one has to resort to the modal idiom of potentialities, while the fact that there is change is indicative of the fact that nature is full of modal properties. -/- Aristotle’s modal and kinetic realism finds a negative in the figure of the Megaric Diodorus Kronus. The polemical situation of Greek philosophy has indeed the dialectical advantage of not opposing the Aristotelian position to a sui generis straw man. Both in its reduction of modal judgements to temporal quantifications and in its dissolution of the reality of the state-of-being-in-motion in favour of a cinematographic view of processes, the philosophical figure of reductionist antirealism embodied by Diodorus constitutes an alternative that takes the opposite view of Aristotle’s realism. -/- The present study is structured as a discussion between these two positions. In the face of Diodorus’ antirealist challenges, Aristotle articulates modal and kinetic considerations: the answers he gives to Diodorus’ puzzles thus provide valuable insight into his metaphysics. Moreover, the examination of Aristotle’s and Diodorus’ metaphysics, because of their insight and originality, will not fail to interest the philosopher concerned with the metaphysical foundations of modern physics, insofar as the entanglement between modalities and processes is nowadays at the core of mechanics (phase spaces, path integrals, etc.). (shrink)

The paper first formalizes the ramified type theory as (informally) described in the Principia Mathematica [32]. This formalization is close to the ideas of the Principia, but also meets contemporary requirements on formality and accuracy, and therefore is a new supply to the known literature on the Principia (like [25], [19], [6] and [7]).As an alternative, notions from the ramified type theory are expressed in a lambda calculus style. This situates the type system of Russell and Whitehead in a modern (...) setting. Both formalizations are inspired by current developments in research on type theory and typed lambda calculus; see [3]. (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.

In the context of his theory of numberings, Ershov showed that Kleene's recursion theorem holds for any precomplete numbering. We discuss various generalizations of this result. Among other things, we show that Arslanov's completeness criterion also holds for every precomplete numbering, and we discuss the relation with Visser's ADN theorem, as well as the uniformity or nonuniformity of the various fixed point theorems. Finally, we base numberings on partial combinatory algebras and prove a generalization of Ershov's theorem in this context.

Review of a compendium of alternative formal representations of common-sense knowledge. The book is centered largely on formal representations drawn from first-order logic, and thus lies in the tradition of Kenneth Forbus, Patrick Hayes and Jerry Hobbs.

This essay examines an argument of perennial importance against naive Leibnizian absolute identity theory, originating with Ruth Barcan in 1947 (Barcan, R. 1947. ?The identity of individuals in a strict functional 3 calculus of second order?, Journal of Symbolic Logic, 12, 12?15), and developed by Arthur Prior in 1962 (Prior, A.N. 1962. Formal Logic. Oxford: The Clarendon Press), presented here in the form offered by Nicholas Griffin in his 1977 book, Relative Identity (Griffin, N. 1977. Relative Identity. Oxford: The Clarendon (...) Press). The objection considers the property of being necessarily identical to a specific object a as a counterexample to Leibnizian identity conditions, and more particularly to the indiscernibility of identicals, when it is only contingently true that a=b. The inquiry eliminates necessity and reference to a specifically designated object as responsible for the counterexample, leaving only identity. The requirements for an exact reinterpretation of Leibniz's Law in light of counterexamples involving converse intentional properties and the family of properties suggested by the property of being necessarily identical to a where a=b (or an equivalent definite descriptor variation) is only logically contingently true, are formalized in a more powerful, counterexample-resistant version of Leibniz's Law that does not succumb to relative identity as a necessary alternative motivated by desperation over the failure of the absolute identity principle. (shrink)

Purpose: The paper discusses the concept of a reflexive domain, an arena where the apparent objects as entities of the domain are actually processes and transformations of the domain as a whole. Human actions in the world partake of the patterns of reflexivity, and the productions of human beings, including science and mathematics, can be seen in this light. Methodology: Simple mathematical models are used to make conceptual points. Context: The paper begins with a review of the author's previous work (...) on eigenforms - objects as tokens for eigenbehaviors, the study of recursions and fixed points of recursions. The paper also studies eigenforms in the Boolean reflexive models of Vladimir Lefebvre. Findings: The paper gives a mathematical definition of a reflexive domain and proves that every transformation of such a domain has a fixed point. Thus eigenforms exist in reflexive domains. We discuss a related concept called a "magma." A magma is composed entirely of its own structure-preserving transformations. Thus a magma can be regarded as a model of reflexivity and we call a magma "reflexive" if it encompasses all of its structure-preserving transformations. We prove a fixed point theorem for reflexive magmas. We then show how magmas are related to knot theory and to an extension of set theory using knot diagrammatic topology. This work brings formalisms for self- reference into a wider arena of process algebra, combinatorics, non-standard set theory and topology. The paper then discusses how these findings are related to lambda calculus, set theory and models for self- reference. The last section of the paper is an account of a computer experiment with a variant of the Life cellular automaton of John H. Conway. In this variant, 7-Life, the recursions lead to self-sustaining processes with very long evolutionary patterns. We show how examples of novel phenomena arise in these patterns over the course of large time scales. Value: The paper provides a wider context and mathematical conceptual tools for the cybernetic study of reflexivity and circularity in systems. (shrink)

Information is a notion of wide use and great intuitive appeal, and hence, not surprisingly, different formal paradigms claim part of it, from Shannon channel theory to Kolmogorov complexity. Information is also a widely used term in logic, but a similar diversity repeats itself: there are several competing logical accounts of this notion, ranging from semantic to syntactic. In this chapter, we will discuss three major logical accounts of information.

We show how to encode context-free string grammars, linear context-free tree grammars, and linear context-free rewriting systems as Abstract Categorial Grammars. These three encodings share the same constructs, the only difference being the interpretation of the composition of the production rules. It is interpreted as a first-order operation in the case of context-free string grammars, as a second-order operation in the case of linear context-free tree grammars, and as a third-order operation in the case of linear context-free rewriting systems. This (...) suggest the possibility of defining an Abstract Categorial Hierarchy. (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)

The concept of “necessity of thought” plays a central role in Dag Prawitz’s essay “Logical Consequence from a Constructivist Point of View” (Prawitz 2005). The theme is later developed in various articles devoted to the notion of valid inference (Prawitz, 2009, forthcoming a, forthcoming b). In section 1 I explain how the notion of necessity of thought emerges from Prawitz’s analysis of logical consequence. I try to expound Prawitz’s views concerning the necessity of thought in sections 2, 3 and 4. (...) In sections 5 and 6 I discuss some problems arising with regard to Prawitz’s views. (shrink)

Thus, despite the di culty of higher-order automated theorem proving, which has to deal with problems like the undecidability of higher-order uni - cation (HOU) and the need for primitive substitution, there are proof problems which lie beyond the capabilities of rst-order theorem provers, but instead can be solved easily by an higher-order theorem prover (HOATP) like Leo. This is due to the expressiveness of higher-order Logic and, in the special case of Leo, due to an appropriate handling of the (...) extensionality principles (functional extensionality and extensionality on truth values). (shrink)

A semantics for quantified modal logic is presented that is based on Kleene's notion of realizability. This semantics generalizes Flagg's 1985 construction of a model of a modal version of Church's Thesis and first-order arithmetic. While the bulk of the paper is devoted to developing the details of the semantics, to illustrate the scope of this approach, we show that the construction produces (i) a model of a modal version of Church's Thesis and a variant of a modal set theory (...) due to Goodman and Scedrov, (ii) a model of a modal version of Troelstra's generalized continuity principle together with a fragment of second-order arithmetic, and (iii) a model based on Scott's graph model (for the untyped lambda calculus) which witnesses the failure of the stability of non-identity. (shrink)

We give two proofs of strong normalisation for second order classical natural deduction. The first one is an adaptation of the method of reducibility candidates introduced in [9] for second order intuitionistic natural deduction; the extension to the classical case requires in particular a simplification of the notion of reducibility candidate. The second one is a reduction to the intuitionistic case, using a Kolmogorov translation.

This volume is dedicated to Prof. Dag Prawitz and his outstanding contributions to philosophical and mathematical logic. Prawitz's eminent contributions to structural proof theory, or general proof theory, as he calls it, and inference-based meaning theories have been extremely influential in the development of modern proof theory and anti-realistic semantics. In particular, Prawitz is the main author on natural deduction in addition to Gerhard Gentzen, who defined natural deduction in his PhD thesis published in 1934. The book opens with an (...) introductory paper that surveys Prawitz's numerous contributions to proof theory and proof-theoretic semantics and puts his work into a somewhat broader perspective, both historically and systematically. Chapters include either in-depth studies of certain aspects of Dag Prawitz's work or address open research problems that are concerned with core issues in structural proof theory and range from philosophical essays to papers of a mathematical nature. Investigations into the necessity of thought and the theory of grounds and computational justifications as well as an examination of Prawitz's conception of the validity of inferences in the light of three “dogmas of proof-theoretic semantics” are included. More formal papers deal with the constructive behaviour of fragments of classical logic and fragments of the modal logic S4 among other topics. In addition, there are chapters about inversion principles, normalization of proofs, and the notion of proof-theoretic harmony and other areas of a more mathematical persuasion. Dag Prawitz also writes a chapter in which he explains his current views on the epistemic dimension of proofs and addresses the question why some inferences succeed in conferring evidence on their conclusions when applied to premises for which one already possesses evidence. (shrink)

The introduction of Linear Logic extends the Curry-Howard Isomorphism to intensional aspects of the typed functional programming. In particular, every formula of Linear Logic tells whether the term it is a type for, can be either erased/duplicated or not, during a computation. So, Linear Logic can be seen as a model of a computational environment with an explicit control about the management of resources.

In this paper we introduce a notion of context for Groenendijk & Stokhof's Dynamic Predicate Logic DPL. We use these contexts to give a characterization of the relations on assignments that can be generated by composition from tests and random resettings in the case that we are working over an infinite domain. These relations are precisely the ones expressible in DPL if we allow ourselves arbitrary tests as a starting point. We discuss some possible extensions of DPL and the way (...) these extensions interact with our notion of context. (shrink)

The first part of the paper introduces the varieties of modern constructive mathematics, concentrating on Bishop's constructive mathematics (BISH). it gives a sketch of both Myhill's axiomatic system for BISH and a constructive axiomatic development of the real line R. The second part of the paper focusses on the relation between constructive mathematics and programming, with emphasis on Martin-L6f 's theory of types as a formal system for BISH.

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)

Když jsem v roce 1992 začínal na filosofické fakultě UK přednášet teorii sémantiky, cítil jsem intenzivní potřebu poskytnout studentům nějaký učební text. O překotném vývoji tohoto interdisciplinárního oboru, který odstartovalo v sedmdesátých letech úspěšné “zkřížení logiky s lingvistikou” Richardem Montaguem a dalšími a který se nezpomalil dodnes, totiž v češtině neexistovaly prakticky žádné zprávy (s čestnou výjimkou přístupu tzv. transparentní intenzionální logiky, který byl dílem českého emigranta Pavla Tichého a o kterém u nás psal Pavel Materna). Přehledové publikace, jaké jsou (...) potřeba pro někoho, kdo se chce v dané problematice zorientovat, se ovšem v té době i po světě teprve začínaly objevovat: v roce 1990 vyšla kniha An Introduction to Semantics Gennara Chierchii a Sally McConell-Ginnetové a v roce 1991 vydala skupina holandských logiků pod kolektivním pseudonymem L.T.F. Gamut dvousvazkovou knihu Language and Meaning. Za této situace jsem se pokusil co nejrychleji sepsat učební text, který by moji studenti i jiní zájemci o sémantiku mohli použít; a protože o jeho vydání paradoxně projevila větší zájem filosofická fakulta Masarykovy univerzity v Brně (kde jsem já osobně nikdy neučil; ale zájem o sémantiku tam neúnavně podněcoval a vydání mého textu tam zprostředkoval kolega Materna) než filosofická fakulta mojí domovské Karlovy univerzity, vyšel tento text v Brně, a to pod názvem Úvod do teoretické sémantiky. (shrink)

In 1969, De Jongh proved the “maximality” of a fragment of intuitionistic predicate calculus forHA. Leivant strengthened the theorem in 1975, using proof-theoretical tools (normalisation of infinitary sequent calculi). By a refinement of De Jongh's original method (using Beth models instead of Kripke models and sheafs of partial combinatory algebras), a semantical proof is given of a result that is almost as good as Leivant's. Furthermore, it is shown thatHA can be extended to Higher Order Heyting Arithmetic+all trueΠ 2 0 (...) -sentences + transfinite induction over primitive recursive well-orderings. As a corollary of the proof, maximality of intuitionistic predicate calculus is established wrt. an abstract realisability notion defined over a suitable expansion ofHA. (shrink)

Children learn their native language by exposure to their linguistic and communicative environment, but apparently without requiring that their mistakes be corrected. Such learning from “positive evidence” has been viewed as raising “logical” problems for language acquisition. In particular, without correction, how is the child to recover from conjecturing an over-general grammar, which will be consistent with any sentence that the child hears? There have been many proposals concerning how this “logical problem” can be dissolved. In this study, we review (...) recent formal results showing that the learner has sufficient data to learn successfully from positive evidence, if it favors the simplest encoding of the linguistic input. Results include the learnability of linguistic prediction, grammaticality judgments, language production, and form-meaning mappings. The simplicity approach can also be “scaled down” to analyze the learnability of specific linguistic constructions, and it is amenable to empirical testing as a framework for describing human language acquisition. (shrink)

We combine a variety of constructive methods (including forcing, realizability, asymmetric interpretation), to obtain consistency results concerning combinatory logic with extensionality and (forms of) the axiom of choice.