We provide a new and elementary proof of strong normalization for the lambda calculus of intersection types. It uses no strong method, like for instance Tait-Girard reducibility predicates, but just simple induction on type complexity and derivation length and thus it is obviously formalizable within first order arithmetic. To obtain this result, we introduce a new system for intersection types whose rules are directly inspired by the reduction relation. Finally, we show that not (...) only the set of strongly normalizing terms of pure lambda calculus can be characterized in this system, but also that a straightforward modification of its rules allows to characterize the set of weakly normalizing terms. (shrink)

Vector models of language are based on the contextual aspects of words and how they co-occur in text. Truth conditional models focus on the logical aspects of language, the denotations of phrases, and their compositional properties. In the latter approach the denotation of a sentence determines its truth conditions and can be taken to be a truth value, a set of possible worlds, a context change potential, or similar. In this short paper, we develop a vector semantics for (...) language based on the simply typed lambda calculus. Our semantics uses techniques familiar from the truth conditional tradition and is based on a form of dynamic interpretation inspired by Heim's context updates. (shrink)

It is well known that the simple types of closed lambda terms or combinators can be interpreted as the theorems of intuitionistic implicational logic . Venneri, using an equivalence between the intersection type system for lambda calculus, without the universal type ω, TA∧λ, and a similar system for combinators, TA∧, shows that the types of TA∧λ are the theorems of a Hilbert-style sublogic of the → ∧ fragment of H→.In this paper we fill a (...) gap in the equivalence proof and introduce a new system of intersection types for lambda calculus that is weaker than TA∧λ, but has the same set of types. The new system has the advantage that the logic of types can be obtained directly from the rules - just as H→ can be obtained from simple type theory. (shrink)

Vector models of language are based on the contextual aspects of language, the distributions of words and how they co-occur in text. Truth conditional models focus on the logical aspects of language, compositional properties of words and how they compose to form sentences. In the truth conditional approach, the denotation of a sentence determines its truth conditions, which can be taken to be a truth value, a set of possible worlds, a context change potential, or similar. In the (...) vector models, the degree of co-occurrence of words in context determines how similar the meanings of words are. In this paper, we put these two models together and develop a vector semantics for language based on the simply typed lambda calculus models of natural language. We provide two types of vector semantics: a static one that uses techniques familiar from the truth conditional tradition and a dynamic one based on a form of dynamic interpretation inspired by Heim’s context change potentials. We show how the dynamic model can be applied to entailment between a corpus and a sentence and provide examples. (shrink)

The Curry-Howard isomorphism states an amazing correspondence between systems of formal logic as encountered in proof theory and computational calculi as found in type theory. For instance, minimal propositional logic corresponds to simply typed lambda-calculus, first-order logic corresponds to dependent types, second-order logic corresponds to polymorphic types, sequent calculus is related to explicit substitution, etc. The isomorphism has many aspects, even at the syntactic level: formulas correspond to types, proofs correspond to terms, provability corresponds (...) to inhabitation, proof normalization corresponds to term reduction, etc. But there is more to the isomorphism than this. For instance, it is an old idea---due to Brouwer, Kolmogorov, and Heyting---that a constructive proof of an implication is a procedure that transforms proofs of the antecedent into proofs of the succedent; the Curry-Howard isomorphism gives syntactic representations of such procedures. The Curry-Howard isomorphism also provides theoretical foundations for many modern proof-assistant systems (e.g. Coq). This book give an introduction to parts of proof theory and related aspects of type theory relevant for the Curry-Howard isomorphism. It can serve as an introduction to any or both of typed lambda-calculus and intuitionistic logic. Key features - The Curry-Howard Isomorphism treated as common theme - Reader-friendly introduction to two complementary subjects: Lambda-calculus and constructive logics - Thorough study of the connection between calculi and logics - Elaborate study of classical logics and control operators - Account of dialogue games for classical and intuitionistic logic - Theoretical foundations of computer-assisted reasoning · The Curry-Howard Isomorphism treated as the common theme. · Reader-friendly introduction to two complementary subjects: lambda-calculus and constructive logics · Thorough study of the connection between calculi and logics. · Elaborate study of classical logics and control operators. · Account of dialogue games for classical and intuitionistic logic. · Theoretical foundations of computer-assisted reasoning. (shrink)

This paper defines reduction on derivations (cut-elimination) in the Strict Intersection Type Assignment System of an earlier paper and shows a strong normalization result for this reduction. Using this result, new proofs are given for the approximation theorem and the characterization of normalizability of terms using intersection types.

This paper discusses the relation between the minimal positive relevant logic B and intersection and union type theories. There is a marvelous coincidence between these very differently motivated research areas. First, we show a perfect fit between the Intersection Type Discipline ITD and the tweaking BT of B, which saves implication and conjunction but drops disjunction . The filter models of the -calculus (and its intimate partner Combinatory Logic CL) of the first author and her coauthors then (...) become theory models of these calculi. (The logician's "theory" is the algebraist's "filter".) The coincidence extends to a dual interpretation of key particles—the subtype translates to provable , type intersection to conjunction , function space to implication, and whole domain to the (trivially added but trivial) truth T. This satisfying ointment contains a fly. For it is right, proper, and to be expected that type union should correspond to the logical disjunction of B. But the simulation of functional application by a fusion (or modus ponens product) operation on theories leaves the key Bubbling lemma of work on ITD unprovable for the -prime theories now appropriate for the modeling. The focus of the present paper lies in an appeal to Harrop theories which are (a) prime and (b) closed under fusion. A version of the Bubbling lemma is then proved for Harrop theories, which accordingly furnish a model of and CL. (shrink)

The lambda-calculus lies at the very foundation of computer science. Besides its historical role in computability theory it has had significant influence on programming language design and implementation, denotational semantics and domain theory. The book emphasizes the proof theory for the type-free lambda-calculus. The first six chapters concern this calculus and cover the basic theory, reduction, models, computability, and the relationship between the lambda-calculus and combinatory logic. Chapter 7 presents a variety of typed (...) calculi; first the simply typed lambda-calculus, then Milner-style polymorphism and, finally the polymporphic lambda-calculus. Chapter 8 concerns three variants of the type-free lambda-calculus that have recently appeared in the research literature: the lazy lambda-calculus, the concurrent y-calculus and the lamdba omega-calculus. The final chapter contains references and a guide to further reading. There are exercises throughout. In contrast to earlier books on these topics, which were written by logicians, the book is written from a computer science perspective and emphasizes the practical relevance of many of the key theoretical ideas. The book is intended as a course text for final year undergraduates or first year graduate students in computer science. Research students should find it a useful introduction to more specialist literature. (shrink)

We investigate the polynomial time isomorphic type structure of (the class of tally, polynomial time computable sets). We partition P T into six parts: D −, D^ − , C, S, F, F^, and study their p-isomorphic properties separately. The structures of , , and are obvious, where F, F^, and C are the class of tally finite sets, the class of tally co-finite sets, and the class of tally bi-dense sets respectively. The following results for the structures of and (...) will be proved, where D^ is the class of tally, co-dense, polynomial time computable sets and S is the class of tally, scatted (i.e., neither dense nor co-dense), polynomial time computable sets. 1. is a countable distributive lattice with the greatest element. 2. Infinitely many intervals in can be distinguished by first order formulas. 3. There exist infinitely many nontrivial automorphisms for . 4. is not distributive, but any interval in is a countable distributive lattice. RID=""ID="" Mathematics Subject Classification (2000): 03D15, 03D25, 03D30, 03D35, 06A06, 06B20 RID=""ID="" Key words or phrases: Computational complexity – Polynomial time – Degree structure – Lattice – Isomorphism RID=""ID="" Part of this work was done when the author was a PhD student at the University of Heidelberg under the direction of Professor Ambos-Spies. (shrink)

Let ℒ and ? be propositional languages over Basic Propositional Calculus, and ℳ = ℒ∩?. Weprove two different but interrelated interpolation theorems. First, suppose that Π is a sequent theory over ℒ, and Σ∪ {C⇒C′} is a set of sequents over ?, such that Π,Σ⊢C⇒C′. Then there is a sequent theory Φ over ℳ such that Π⊢Φ and Φ, Σ⊢C⇒C′. Second, let A be a formula over ℒ, and C 1, C 2 be formulas over ?, such that A∧C (...) 1⊢C 2. Then there exists a formula B over ℳ such that A⊢B and B∧C 1⊢C 2. (shrink)

The strong normalization theorem is uniformly proved for typed λ-calculi for a wide range of substructural logics with or without strong negation.

In this paper we consider a type system with a universal type $omega$ where any term (whether open or closed, $beta$-normalising or not) has type $omega$. We provide this type system with a realisability semantics where an atomic type is interpreted as the set of $lambda$-terms saturated by a certain relation. The variation of the saturation relation gives a number of interpretations to each type. We show the soundness and completeness of our semantics and that for different notions of (...) saturation (based on weak head reduction and normal $beta$-reduction) we obtain the same interpretation for types. Since the presence of $omega$ prevents typability and realisability from coinciding and creates extra difficulties in characterizing the interpretation of a type, we define a class ${mathbb U}^+$ of the so-called positive types (where $omega$ can only occur at specific positions). We show that if a term inhabits a positive type, then this term is $beta$-normalisable and reduces to a closed term. In other words, positive types can be used to represent abstract data types. The completeness theorem for ${mathbb U}^+$ becomes interesting indeed since it establishes a perfect equivalence between typable terms and terms that inhabit a type. In other words, typability and realisability coincide on ${mathbb U}^+$. We give a number of examples to explain the intuition behind the definition of ${mathbb U}^+$ and to show that this class cannot be extended while keeping its desired properties. (shrink)

We develop a vector space semantics for verb phrase ellipsis with anaphora using type-driven compositional distributional semantics based on the Lambek calculus with limited contraction of Jäger. Distributional semantics has a lot to say about the statistical collocation based meanings of content words, but provides little guidance on how to treat function words. Formal semantics on the other hand, has powerful mechanisms for dealing with relative pronouns, coordinators, and the like. Type-driven compositional distributional semantics brings these two (...) models together. We review previous compositional distributional models of relative pronouns, coordination and a restricted account of ellipsis in the DisCoCat framework of Coecke et al. :1079–1100, 2013). We show how DisCoCat cannot deal with general forms of ellipsis, which rely on copying of information, and develop a novel way of connecting typelogical grammar to distributional semantics by assigning vector interpretable lambda terms to derivations of LCC in the style of Muskens and Sadrzadeh Logical aspects of computational linguistics, Springer, Berlin, 2016). What follows is an account of ellipsis in which word meanings can be copied: the meaning of a sentence is now a program with non-linear access to individual word embeddings. We present the theoretical setting, work out examples, and demonstrate our results with a state of the art distributional model on an extended verb disambiguation dataset. (shrink)

Light Linear Logic (LLL) and Intuitionistic Light Affine Logic (ILAL) are logics that capture polynomial time computation. It is known that every polynomial time function can be represented by a proof of these logics via the proofs-as-programs correspondence. Furthermore, there is a reduction strategy which normalizes a given proof in polynomial time. Given the latter polynomial time “weak” normalization theorem, it is natural to ask whether a “strong” form of polynomial time normalization theorem holds or not. In this (...) paper, we introduce an untyped term calculus, called Light Affine Lambda Calculus (λLA), which corresponds to ILAL. λLA is a bi-modal λ-calculus with certain constraints, endowed with very simple reduction rules. The main property of LALC is the polynomial time strong normalization: any reduction strategy normalizes a given λLA term in a polynomial number of reduction steps, and indeed in polynomial time. Since proofs of ILAL are structurally representable by terms of λLA, we conclude that the same holds for ILAL. (shrink)

In this note we show that the so-called weakly extensional arithmetic in all finite types, which is based on a quantifier-free rule of extensionality due to C. Spector and which is of significance in the context of Gödel"s functional interpretation, does not satisfy the deduction theorem for additional axioms. This holds already for Π0 1-axioms. Previously, only the failure of the stronger deduction theorem for deductions from (possibly open) assumptions (with parameters kept fixed) was known.

A Kripke model ? is a submodel of another Kripke model ℳ if ? is obtained by restricting the set of nodes of ℳ. In this paper we show that the class of formulas of Intuitionistic Predicate Logic that is preserved under taking submodels of Kripke models is precisely the class of semipositive formulas. This result is an analogue of the Łoś-Tarski theorem for the Classical Predicate Calculus.In Appendix A we prove that for theories with decidable identity we can (...) take as the embeddings between domains in Kripke models of the theory, the identical embeddings. This is a well known fact, but we know of no correct proof in the literature. In Appendix B we answer, negatively, a question posed by Sam Buss: whether there is a classical theory T, such that ℋT is HA. Here ℋT is the theory of all Kripke models ℳ such that the structures assigned to the nodes of ℳ all satisfy T in the sense of classical model theory. (shrink)

, which uses the intuitionistic propositional calculus, with the only connective →. It is very important, because the well known Curry-Howard correspondence between proofs and programs was originally discovered with it, and because it enjoys the normalization property: every typed term is strongly normalizable. It was extended to second order intuitionistic logic, in 1970, by J.-Y. Girard [4], under the name of system F, still with the normalization property.More recently, in 1990, the Curry-Howard correspondence was extended to (...) classical logic, following Felleisen and Griffin [6] who discovered that the law of Peirce corresponds to control instructions in functional programming languages. It is interesting to notice that, as early as 1972, Clint and Hoare [1] had made an analogous remark for the law of excluded middle and controlled jump instructions in imperative languages.There are now many type systems which are based on classical logic; among the best known are the system LC of J.-Y. Girard [5] and the λμ-calculus of M. Parigot [11]. We shall use below a system closely related to the latter, called the λ c -calculus [8, 9]. Both systems use classical second order logic and have the normalization property.In the sequel, we shall extend the λ c -calculus to the Zermelo-Frænkel set theory. The main problem is due to the axiom of extensionality. To overcome this difficulty, we first give the axioms of ZF in a suitable (equivalent) form, which we call ZF ɛ. (shrink)

Building on previous work by Mints, Buchholz and Schwichtenberg, a simplified version of continuous normalization for the untyped λ-calculus and Gödel’s is presented and analysed in the coalgebraic framework of non-wellfounded terms with so-called repetition constructors.The primitive recursive normalization function is uniformly continuous w.r.t. the natural metric on non-wellfounded terms. Furthermore, the number of necessary repetition constructors is locally related to the number of reduction steps needed to reach the normal form and its size.It is also shown (...) how continuous normal forms relate to derivations of strong normalizability in the typed λ-calculus and how this leads to new bounds for the sum of the height of the reduction tree and the size of the normal form.Finally, the methods are extended to an infinitary λ-calculus with ω-rule and permutative conversions and this is used to derive a strong form of normalization for an iterative version of Gödel’s system , leading to a value table semantics for number-theoretic functions. (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)

Barendregt gave a sound semantics of the simple type assignment system λ → by generalizing Tait’s proof of the strong normalization theorem. In this paper, we aim to extend the semantics so that the completeness theorem holds.

Mitchell, J.C. and E. Moggi, Kripke-style models for typed lambda calculus, Annals of Pure and Applied Logic 51 99–124. The semantics of typed lambda calculus is usually described using Henkin models, consisting of functions over some collection of sets, or concrete cartesian closed categories, which are essentially equivalent. We describe a more general class of Kripke-style models. In categorical terms, our Kripke lambda models are cartesian closed subcategories of the presheaves over a poset. To those (...) familiar with Kripke models of modal or intuitionistic logics, Kripke lambda models are likely to seem adequately ‘semantic’. However, when viewed as cartesian closed categories, they do not have the property variously referred to as concreteness, well- pointedness or having enough points. While the traditional lambda calculus proof system is not complete for Henkin models that may have empty types, we prove strong completeness for Kripke models. In fact, every set of equations that is closed under implication is the theory of a single Kripke model. We also develop some properties of logical relations over Kripke structures, showing that every theory is the theory of a model determined by a Kripke equivalence relation over a Henkin model. We discuss cartesian closed categories but present the main definitions and results without the use of category theory. (shrink)

Nietzsche is not difficult to read, but he is famously difficult to understand. This is because of the bewildering array of words, phrases or metaphors that he uses. The Nietzsche Dictionary aims to help, by giving readers a road map to Nietzsche's language, and thus how his terminology and images relate together, forming an overall philosophical picture. The Dictionary also includes synopses of Nietzsche's key works, and short articles on the main philosophical and cultural influences leading up to, (...) and resulting from, Nietzsche. It is designed to be a resource that all readers of Nietzsche will find invaluable, from beginners to more advanced readers.In order to make the book easy to use and navigate, all entries are treated thematically and are of seven types:1. Influences on, or the contemporary context of, Nietzsche2. Major influences of Nietzsche3. Key concepts4. Key metaphors or images5. Alternative translations of the above6. Other words or phrases found in Nietzsche that are cross-referenced to a main entry7. Synopses of major works by Nietzsche. (shrink)

A simple proof is given of the property that the set of strongly normalizing lambda terms coincides with the set of lambda terms typable in certain intersection type assignment systems.

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.This paper introduces a typed functional language Λ! and a categorical model for it.The terms of Λ! encode (...) a version of natural deduction for Intuitionistic Linear Logic such that linear and non linear assumptions are managed multiplicatively and additively, respectively. Correspondingly, the terms of Λ! are built out of two disjoint sets of variables. Moreover, the λ-abstractions of Λ! bind variables and patterns. The use of two different kinds of variables and the patterns allow a very compact definition of the one-step operational semantics of Λ!, unlike all other extensions of Curry-Howard Isomorphism to Intuitionistic Linear Logic. The language Λ! is Church-Rosser and enjoys both Strong Normalizability and Subject Reduction.The categorical model induces operational equivalences like, for example, a set of extensional equivalences.The paper presents also an untyped version of Λ! and a type assignment for it, using formulas of Linear Logic as types. The type assignment inherits from Λ! all the good computational properties and enjoys also the Principal-Type Property. (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.

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.This paper introduces a typed functional language ! and a categorical model for it.

Translated by Drew S. Burk and Anthony Paul Smith. Excerpted from Struggle and Utopia at the End Times of Philosophy , (Minneapolis: Univocal Publishing, 2012). THE END TIMES OF PHILOSOPHY The phrase “end times of philosophy” is not a new version of the “end of philosophy” or the “end of history,” themes which have become quite vulgar and nourish all hopes of revenge and powerlessness. Moreover, philosophy itself does not stop proclaiming its own death, admitting itself to be half dead (...) and doing nothing but providing ammunition for its adversaries. With our sights set on clearing up this nuance, we differentiate philosophy as an institutional entity, and the philosophizability of the World and History, of “thought-world,” which universalizes the narrow concept of philosophy and that of “capital.” We also give an eschatological and apocalyptical cause to this end, of “times” or “ages” rather than those of philosophical practice. Last but not least, it is the Future itself in the performativity of its ultimatum that determines this end times, reversing these times from the Identity the Future accorded to it, withdrawing the thought-world from the lie of its death. Why this style of axioms and oracles, these more or less subtle distinctions, old and debased, with an appeal to the ultimata , to end times and last words? We fight to give, parallel to the concept of Hell, its new theoretical position, for its philosophical return and its non-philosophical transformation. No more so than any other word, Hell is not a metaphor here, just the Principle of Sufficient World. Every man, no doubt, has his “hell” readily available, connivance, control, conformism, domestication, schooling, alienation, extermination, exploitation, oppression, anxiety, etc. We have our little list that the Contemporaries established in the previous century in the same way one used to construct lists of virtues and vices or honors and wealth. They invented it for us without knowing it, for us-the-Futures who have as our responsibility to invent its use. In the Christian and Gnostic tradition, the struggle of the End Times takes place “on earth.” The most sophisticated of believers have it taking place in Heaven as well, above all in Heaven. The various kinds of gnosis imagine infinite falls and vertiginous highs, the vertigo of salvation. On Earth as in Heaven, a hell is available. The Marxists have the law of profit and the control of production, the class struggle Capital imposes on man. The Nietzscheans, the dull grumble of the struggle in the foundations of World and History, the domestication of man, the society of control. The phenomenologists, the capture of being, the most superficial amongst them, the age of suspicion. But all of these “hells” are taken from World, History, Society, and Religion. What we call Hell is no longer of the order of these specific and total intra-worldly generalities, it is both more singular and more universal, no longer being at all of the same order, it is the determinant Identity of these small hells strung out through history but unified here in the name of the last Humaneity. It is even found within the French idiom for hell [ enfer ], en-fer literally means “in-irons.” We are as much “in-irons” as we are “alive” [ en-Vie ]. We believe in Hell but as non-philosophers and it is even because we are non-philosophers that we can believe in it outside of any sort of religion. Hell is less mythological than ideological, it combines philosophizability with universal capital. Under what form? A single term could work for them without being a metaphor or something they would participate in by analogy, a more innovative and conjectural term than control, more universal than profit. It would denote the growing and permanent extortion of a surplus-value of communication, of speed and of urgency in change, in productivity and in work, in the pressure of images and slogans. It would be worse than solicitation, more tenacious than capture, more active and persecutory than control, softer and more insidious than a frontal attack, just as perverse as questioning and accusation, less brutal and offensive than extermination, less ritualized than inquisition, it would be soft and dispersed, instantaneous and vicious, it would be a crime without declared violence. Collusion and conformism, it would be afraid to show itself. Related to rumor, from which it borrows its infinite and tortuous ways. It is harassment. As a modernized form of Hell, perhaps harassment has a long future in front of it, of innocent torture, slow assassination, in short the fall, but radical with no way of recovering and which tolerates only salvation. THE PHILOSOPHICAL PAST OF NON-PHILOSOPHY Non-philosophy is thus Man as the utopian identity of the philosophical form of the World, a utopia destined to transform it. We still have to understand these equations, in particular that of the being-uni-versed from Man, and this book adheres to this by re-exposing non-philosophy in a different way via one of its new possibilities. It uses this opportunity to once again take up formulations that lead to objections answering certain external critics, as well as revisiting diverging interpretations specific to non-philosophers. A portion of this book is devoted to going through these theories via a strict or “lengthy” presentation of non-philosophy, and its defense against more expeditious solutions. This work of rectification is the occasion, merely the occasion, for refocusing non-philosophy on Man (the “Man-in-person,” “Humaneity”), and in a more innovative manner, on its utopian vocation established since the book Future Christ . As for this “occasion,” it is quite obvious. A school of posture, not to say a school of thought, supposes a minimum of closure from the most liberating of knowledge, a heritage, its utilization, and its no less certain dispersal. Within its development, a variety of interpretations will no doubt appear, deviations that are as much normalizations, and a struggle against this multiplication of divergent tendencies. These are perhaps not inevitable evils, especially here, merely a normal development according to the twisting paths of history. But the problem is made worse by the fact that this school of non-philosophers is that of utopia. Not the former attempts devoted to commenting on the worst authoritarian and criminal forms of the past and the present, but utopia as the determinant principle for human life, or to put it another way, of the Future as an irreducible presupposition of (for) thinking the World and History. Non-philosophers are engaged in an aleatory navigation between the respect for the most rigorous utopia, whose rules are not that of the reproductive imagination but those from the Future determining imagination itself, as well as the temptations, diversions, and remorse of history. Little by little, we will begin to understand that the Future as we understand it no longer has any temporal consistency or positive content, without being an empty form or a nothingness, but that it is foreclosed to past and present History, just as it is foreclosed to the place of places, the World, and that it is the only method for establishing the practice of thinking in a non-imaginary instance. Because it is the World and History that are imaginary and have a terrible materiality, it is not necessarily utopia. We will overlap two objectives here: the defense of non-philosophy against the (non-) philosophers that we are, only occasionally, and the introduction of philosophy to a rigorous future. Together they set out to definitively render, without any possible return to philosophical conformism or towards the facilities of the past and present, the non-philosophical enterprise understood as utopia or uchronia. Imagination and speculation, left to themselves and thus undistinguished, are quite good for participating in the grand game of History but have little value or worse for the Future which is unimaginable and unintelligible and must be maintained as such. MAN-IN-PERSON AS SUSPENSION OF THE PHILOSOPHICAL CHORA The point where philosophical resistance is concentrated is without a doubt the invention of the Name-of-Man, first name, oracular as much as axiomatic, of the determining cause for the non-philosophical posture. And that which concentrates the differends is the style of non-philosophy as identity that possesses the dual aspect, of discipline and of the oeuvre, of the theorem and of the oracle. But the real difficulty in understanding the simplicity of non-philosophy is profoundly hidden in the depths of philosophy itself. Because philosophy, from Parmenides to Derrida, even Levinas, continues to be a divided gesture, without a veritable immanence, transforming its thematic contents of transcendence in also forgetting to transform the operative transcendence in the element from which the ontology of surface is established which we will call, in memory of Plato, the chorismos. The general effect of the chora literally gives place to philosophy, demanding binding and sutures to which we will once and for all “oppose” the Man-in-person, his power of cloning, and his future being. All philosophy contains a hinter-philosophy in which it deploys its operations and weaves its tradition like an understudy of a topographical nature and in the best of cases being itself topological. Philosophy as well consists of two levels, its pre-ontological operative conditions on the one hand, and its superficial theme on the other, it too has its presupposed, but is not aware of it or erases it within the unity of appearance named Logos. Rightly, the Logos, and its flash or lightning nature, possesses a “dark precursor,” the chora, which is as much a virtual image, and philosophy, dazzled by its own lightning flash, seems to completely forget about it at the same time it sets itself up within it. Non-philosophy risks taking this same path, of confusing what it believes to be the real with its phantom double, contenting itself to working on the thematic level of philosophy, not its surface objects and its idle chatter (we stopped talking about this a long time ago and in any case they are merely simple materials for inducing a work of transformation), but the transcendence-form of its objects. In the end it risks, through precipitation, taking back up the heritage of philosophy, a heritage of a misunderstood presupposed, even more profound than the play of transcendences. This is what the imperative of the radicality of immanence meant, to treat immanence in an immanent manner, not to make a new object out of it. And from here we get non- (philosophy) and its refusal of the Platonic chorismos , symbol of all abstraction, and thus all transcendental appearance. There are no illusions. The message will leave a heritage in tattered pieces and interpretations. But it was difficult not to dispute the differend to its core. There will be complete confusion of the multiple, possible, and necessary effectuations of non-philosophy with its interpretations. The non-philosophical or human freedom of philosophical effectuation and the philosophical freedom of interpretation. Effectuations demand non-philosophy to return to zero from the point of view of its philosophical material and thus also but within these limits the formulation of its axioms , but in no way providing from the outset divergent interpretations of the aforementioned axioms. They are divergent because they do not take into account the material from which these axioms are derived within non-philosophy, and because they do not see themselves as symptoms of another vision of the World. The utterances of non-philosophy are not mathematical theorems and pure axioms, they merely have a mathematical aspect . They are, by their extraction or origin, mathematical and transcendental. And by their determined function in-Real, within non-philosophy, they are identically in-the-last-Humaneity entities which have an aspect of an axiom and an aspect of interpretation (or an oracular aspect as we say) that attempts (sometimes it is ourselves who provide the occasion) to isolate and transform, in complete freedom of interpretation. There will be an opportunity to complain about the complex character of the language of non-philosophy, an idiom saturated with classical references, sophisticated in a contemporary way. Its freedom of decision up against the whole of philosophy demands these effects of “complication” and “privatization,” as the saying goes. But it also demands fighting against the drift [ dérive ] of the pedagogical-all and the mediatic-all that leads philosophy into the shallow depths of opinion, which is the site of its impossible death. The noble idealism of “pop-philosophy” has been consumed into a “philo-reality;” against this we propose philo-fiction. Parricide, which is at the bottom of these interpretations and which we can judge as being quite fertile, although it has informed tradition, only takes place once or within one lone meaning. In regards to Parmenides, it was possible; Plato introduced the Other as non-being and language, bringing into existence the philosophical system of the World, but is it possible to repeat it again with the same fecundity in regards to non-philosophy, this time in introducing (non) religion or (non) art, still mixing them without taking into account this mixture, alternatively as a philosophical or religious resentment? If philosophy begins via a crime, it is no doubt obliged to continue down similar pathways, to the effect that the crimes of philosophy, once the founding crime has been committed, are a reaction of self-defense. It is undoubtedly from this that we get Marx’s declaration that history begins by tragedy and repeats itself or ends in farce. The preservation of rigor and fecundity is, in every respect, a psychologically difficult task within a theory such as non-philosophy. Having posited an essential objective of liberation in regards to philosophy and its services, one has often understood this objective as an authorization of providing particular interpretations of its axioms and ends up obliterating their scope. This ends up confusing, on one hand, two kinds of freedoms in regards to non-philosophy, the freedom of its interpretations and the freedom of its effectuations. On the other hand, any defense of “principles” against precipitated interpretations is immediately taxed with a will to orthodoxy, a prohibitive objection when we are dealing with, as is the case here, a heretical theory of thought. Nevertheless, it is time to stop confusing heresy as the cause of thought with an ideology of heresies, which is certainly not at all our object, but rather a form of normalization. As for the “disciplinary” aspect, which is not the only aspect, it demands something other than philosophical “answers to objections,” a precision in the definition and use of its procedures in the formation of utterances, since non-philosophy is neither a supplementary doctrine interior to philosophy nor a vision of the world but one whose priority is a “vision of Man,” or rather Man as “vision” that implies a theory and a practice of philosophy. In the end, struggle is only one aspect of non-philosophy, not its whole or telos, struggle coming only from its materiality. In particular, if the discipline of non-philosophy is inseparable from struggle, it is not a question of reducing the monomaniacal obsession of its “marching orders.” This would reduce its complexity and kill its indivisibility, deploying it in a “long march” and a form of Maoization whose philosophical presuppositions no longer have any pertinence here, a case of the One and the Two, which are now cloned and no longer tied together. More generally, non-philosophy is a complex thought composed of a multitude of aspects, which is to say, unilateral interpretations, of a philosophical origin but reduced by their determination in-the-last-instance . The “liberalism” of non-philosophy is merely one of the aspects of which it is capable, not an essence. Similarly, it is only capable of having a “Maoist” aspect. Let us generalize. The weakness of non-philosophy is due to a specific cause, the determination-in-the-last-Humaneity of a subject for the World. Everything that has a right to the philosophical city can be said about it in turn and in a retaliatory mode since Man contributes nothing of himself that Man takes from the World. We can consider non-philosophy as being pretentious, absurd, idealistic, empty, materialistic, formalistic, contradictory, modern, post-modern, Zen, Buddhist, Marxist; it endures or tolerates, perhaps “appeals” to, or at least renders possible, sarcasms, ironies, and insults without even talking about the misunderstandings, partly for the same reason as psychoanalysis. All of this goes beyond simple “deviations.” They are its aspects, which is to say, its “unilateral” philosophical interpretations in both senses of the word, being either sufficient coming from the mouth of philosophers, or reduced to their absolute dimension of sufficiency and totality in the mouths of non-philosophers, and both times due to the weakness and strength of Man-in-person as their determination only in-the-last-instance. The non-philosopher is certainly not a Saint Paul fantasizing about a new Church. The non-philosopher is either a (Saint) Sebastian whose flesh is pierced with as many arrows as there are Churches, or a Christ persecuted by a Saint Paul. What is engaged in here is the practice of retaliation. A negative rule of the non-philosophical ethics of outlawed discussion by way of argumentation (the sufficient is you, the orthodox one is always you, you are the fashionable one, and when a master you are someone else) that is founded on the confusion of effectuations of non-philosophy and of its overall interpretations. Retaliation is the law but as with any too-human law, it must acquire a dimension that displaces it, or rather emplaces it and takes away its authority but not all of its effectiveness. If the non-philosopher is only authorized by himself, which is to say by philosophy but limited by the Real-of-the-last-instance, its critique of other non-philosophers can merely be retaliatory under the same conditions, only by the Real limited in-the last-instance. THE TREE OF PHILOSOPHICAL SAINTLINESS The thematic horizon or material of these debates is in the relationships between philosophy, religion as gnosis, and non-philosophy. It is inevitable, regarding non-philosophers in general (whether they are non-philosophers by name or simply its neighbors) that we often end up evoking Marx’s Holy Family and imagining, arranged on the neighboring branches of the tree of philosophy and annexed, sometimes abusively, to non-philosophy, authors who would quite evidently and quite rightly refuse this label. So it is that we find, for example, a Saint Michel, a Saint Alain, a Saint Gilles 1 without even mentioning the youngest who aspire as well to the freedom of “saintliness” and who make their muted voices heard here. If there is a Holy Family of non-philosophers, it extends completely beyond these three, provided that the sectarian spirit can save us. This book is organized in the following manner: To begin, in order to recall the essential part of the problematic, we have organized a Summary of Non-Philosophy , a vade-mecum of notions and basic problems, in a classical style. Secondly, there is Clarifications On the Three Axioms of Non-Philosophy , designed to posit their proper use as much as to elucidate their meaning. Thirdly, an analysis of Philosophizability and Practicity , both being extreme constituents of philosophical material or the contents of the third axiom. Fourthly, the heart of this work: Let us Make a Tabula Rasa of the Future or of Utopia as Method . Fifthly, we have a theoretical outline of a non-institutional utopia, The International Organization of Non-Philosophy, L’Organisation Non-Philosophique Internationale, (ONPHI) already created in practice but under the conditions of possibility and functioning from which here we put into question “de jure,” thus not without a perplexity concerning “facts,” in any case, without the capability of “getting to the bottom of things.” Sixthly, an essay characterizing The Right and the Left of Non-Philosophy , a brief topology of several philosophizing and normalizing positions of proponents or tenants of this problematic. Seventhly, Rebel in the Soul: A Theory of Future Struggle , a systematic discussion starting from a confrontation of non-philosophical gnosis and non-religious gnosis to the extent that they pose, posed or perhaps still will pose themselves as rivals to non-philosophy in a mixture of fidelity and infidelity. Despite the fact that it can also be read as putting non-philosophy into perspective: it pits against a standard Platonism two contemporary appropriations of Gnosticism. On the basis of the paradigm of Man who never ceases to come as the Future-in-person, each one of these moments strives to reestablish not the “true” non-philosophy and its orthodoxy, but the minimal conditions to respect in order to allow for its maximum fecundity. And in order to bring about one of the last possibilities of its development, making explicit Humaneity as a utopia-for-the-World. In introducing these considerations in the form of a “testament” and “ultimatum,” we want to indicate two things: First, that this is the last time we will intervene in order to caution non-philosophers against the temptation of returning and looking backwards towards philosophy. Only a disillusioned nostalgia for the former World and its traditions barely remain permissible to us.… Secondly, that non-philosophy is also a sort of ultimatum for considering one’s life and transforming one’s thought from the perspective of a uni-version rather than a conversion. Man as future is this ultimatum in action, not an impatient self-proclaimed genius, and philosophy is his testament. It is obviously the ultimatum that determines this testament as “old” with a view towards a life that is, itself, non-testamentary. In and of itself, the “old” can never bear a veritable eschaton. Thus, this book intersects according to the logic of this paradigm, under the sign of the ultimate or “last” as future, philosophy as testament and cautionary note for maintaining the non-philosophical oeuvre as “future” or “utopian.” We will see that between these two dimensions it cradles a theory of struggle. In the end, this book envisions non-philosophers in multiple ways. It inevitably sees them as subjects of knowledge, most often academics insofar as life in the world demands, but above all as close relatives of three great human types. The analyst and political militant are quite obvious, for non-philosophy is close to psychoanalysis and Marxism insofar as it transforms the subject in transforming philosophy. Here again, one must have a sense not of certain nuances but of aspects (of the interpretations, albeit unilateralized) and not in order to construct a simple proletarization or militarization of thought as theory. To be rigorous, rather than authoritarian or spiteful, is its task. And lastly, non-philosophy is a close relative of the spiritual but definitely not the spiritualist. Those who are spiritual are not at all spiritualists, for the spiritual oscillate between fury and tranquil rage, they are great destroyers of the forces of Philosophy and the State, which are united under the name of Conformism. They haunt the margins of philosophy, gnosis, mysticism, science fiction and even religions. Spiritual types are not only abstract mystics and quietists; they are heretics for the World. The task is to bring their heresy to the capacity of utopia, and their utopia to the capacity of the paradigm. NOTES We will recognize allusions, and sometimes references, to closely related or distant themes, but which are related, in the work of Michel Henry, Alain Badiou and via the representative of “non-religious” gnosis of a Platonic origin, in Gilles Grelet. It goes without saying that these discussions are current and local, neither concerning the ensemble of doctrines nor prejudging the eventual evolution of certain amongst them. This concerns defining certain proximities with non-philosophy (rather than adversaries which in some sense they are) and typological and emblematic differends (rather than conflicts with a certain author). (shrink)

The restrictive grammatical format suggested in GPSG provides an extremely interesting alternative to transformational approaches to grammar. However, we have seen that the way the grammar is currently organized, it will in certain cases fail to give the correct interpretation to sentences with displaced constituents. Whenever a left or rightward displaced constituent contains an element that can stand in an anaphoric relation with some other element in the sentence, i.e. contains a quantifier or a pronoun, the semantic rules as given (...) do not provide the intended reading. It should be made clear, however, that this shortcoming pertains to one particular type of GPSG, namely one whose interpretation procedures make use of lambda abstraction. The problematic cases addressed here do not by themselves invalidate the syntactic framework of a GPSG. It seems quite plausible that one could construct a semantics that does not depend on lambda conversion, in which case the problem addressed in this note is presumably no longer relevant. One such proposal is put forward in Cooper (forthcoming) where a non-movement syntax is combined with interpretation procedures that do not involve translation into a lambda calculus. (shrink)

Categorial grammar is well-known for its elegant analysis of coordination enabled by the flexible notion of constituency it entertains. However, to date, no systematic study exists that examines whether this analysis has any obvious empirical advantage over alternative analyses of nonconstituent coordination available in phrase structure-based theories of syntax. This paper attempts precisely such a comparison. We compare the direct constituent coordination analysis of non-canonical coordinations in categorial grammar with an ellipsis-based analysis of the same phenomena in the recent HPSG (...) literature. We provide a set of empirical evidence, consisting of cases in which non-canonical coordinations interact with scopal operators of various sorts, which systematically falsifies the predictions of the latter, ‘linearization-based’ ellipsis approach to coordination. We propose an alternative analysis in a variant of categorial grammar called Hybrid Type-Logical Categorial Grammar. The proposed framework builds on both the Lambek-inspired variants of categorial grammar and a more recent line of work modelling word order via a lambda calculus for the prosodic component. The flexible syntax–semantics interface of this framework straightforwardly captures the interactions between non-canonical coordinations and scopal expressions, demonstrating the broader empirical payoff of the direct constituent coordination analysis of non-canonical coordinations pioneered by Steedman :523–568, 1985; Linguist Philos 13:207–263, 1990) and Dowty hitherto not explicitly recognized in the literature. (shrink)

KRISP is a representation system and set of interpretation protocols that is used in the Sparser natural language understanding system to embody the meaning of texts and their pragmatic contexts. It is based on a denotational notion of semantic interpretation, where the phrases of a text are directly projected onto a largely pre-existing set of individuals and categories in a model, rather than first going through a level of symbolic representation such as a logical form. It defines a small (...) set of semantic object types, grounded in the lambda calculus, and it supports the principle of uniqueness and supplies first class objects to represent partially-saturated relationships.KRISP is being used to develop a core set of concepts for such things as names, amounts, time, and modality, which are part of a few larger models for domains including Who''s News and joint ventures. It is targeted at the task of information extraction, emphasizing the need to relate entities mentioned in new texts to a large set of pre-defined entities and those read about in earlier articles or in the same article. (shrink)

Our goal in this paper is to analyze the interpretation of arbitrary unsolvable $\lambda$-terms in a given model of $\lambda$-calculus. We focus on graph models and (a special type of) stable models. We introduce the syntactical notion of a decoration and the semantical notion of a critical sequence. We conjecture that any unsolvable term $\beta$-reduces to a term admitting a decoration. The main result of this paper concerns the interconnection between those two notions: given a graph model (...) or stable model $\mathfrak{D}$, we show that any unsolvable term admitting a decoration and having a non-empty interpretation in $\mathfrak{D}$ generates a critical sequence in the model. In the last section, we examine three classical graph models, namely the model $\mathfrak{B}(\omega)$ of Plotkin and Scott, Engeler's model $\mathfrak{D}_A$ and Park's model $\mathfrak{D}_P$. We show that $\mathfrak{B}(\omega)$ and $\mathfrak{D}_A$ do not contain critical sequences whereas $\mathfrak{D}_P$ does. (shrink)

One of the divine quotations narrated from the timeline of Qur’ānic revelation is seen as a word of Prophet Mohammad in the 30th verse of the surah of al-Furqān. It’s observed that the speaker of this verse is Prophet Mohammad and he complains to God about his tribe which neglects the Qur’ān. In the present study, semantic structure and the meaning area of the phrase “mahjūr”, which is the key word in this verse, the meaning of it in the timeline (...) of Qur’ānic revelation and the interpretations attributed to it in the following centuries are traced. Likewise by examining Qur’ānic exegesis chronologically and investigating the interpretations of the exegetes on the relevant verse, it’s tried to see the semantic breaking points, changes and transformations regarding this verse in the historical process. Finally, the approaches of the exegetes who interpreted this verse in terms of the method of maqāsidī tafsir or the principle of teleological interpretation are determined. The approaches detected in this respect are first explained in a descriptive style, and then they’re evaluated in an analytical point of view. The findings and conclusions we reached in this study are as follows: As stated by the majority of exegetes, especially Qatāda, al-Zamakhsharī, Ibn Atiyya, Fakhr al-Dīn al-Rāzī and al-Sa‘ālibī, the aforementioned verse belongs to the Prophet Mohammed in terms of both wording and meaning. It hasn’t been determined that there’s a conflict about the pertaining of this word to him. According to this hadith quoted in surah al-Furqān, the Qurayshi polytheists made unwarranted objections to the Prophet and the divine instructions that he brought, his heart was narrowed in the face of their attitude towards the Qur’ān, and for these reasons he complained about his tribe to God. It can be said that this meaning seen in Mecca in the tenth year of his prophethood, namely, insulting the Qur’ān, abandoning it, and denying the themes in it, also includes Muslims after the revelation period. Accordingly, it can be thought that the aspect and situation of not acting on the provisions of the Qur’ān and not thinking about its verses are also valid for the interlocutors of the next period. In this direction, when we look at the history of tafsir, it has been determined that the exegetes who interpreted this verse in terms of teleological interpretation asserted different approaches. It was seen that al-Zamakhsharī, al-Rāzī, Abū al-Barakāt al-Nasafī, al-Bikā‘ī, Kamālpasazāde, Sayhzāda and Ibn ʻĀshūr interpreted this complaint of the Prophet by associating it with the coming of punishment. Therefore, in compliance with them, this verse aimed to threaten all the interlocutors, especially the Quraysh. On the other hand, it has recognized that Ibn al-Qayyim al-Jawziyah, Ibn Kathir, Bursavī and Sayyid Qutb evaluated this verse in the context of the types and ways to abandon the Qur’ān. Thus, they interpreted the relevant verse in terms of maqāsidī tafsir in a way that would cover both the first addressees of Qur’ānic revelation and other interlocutors in the following periods. In a nutshell, it can be considered that not endeavoring to understand and interpret the Qur’ān, or keeping it away from family and social life, law, understanding of earning and spending, not referring to it in such matters, or giving up living a life pursuant to it, are some of the routes and sorts of abandonment of it for Muslims. (shrink)

This handbook with exercises reveals the mathematical beauty of formalisms hitherto mostly used for software and hardware design and verification.

Building on previous work by Coquand and Spiwack [T. Coquand, A. Spiwack, A proof of strong normalisation using domain theory, in: Proceedings of the 21st Annual IEEE Symposium on Logic in Computer Science, LICS’06, IEEE Computer Society Press, 2006, pp. 307–316] we construct a strict domain-theoretic model for the untyped λ-calculus with pattern matching and term rewriting which has the property that a term is strongly normalising if its value is not . There are no disjointness or confluence conditions (...) imposed on the rewrite rules, and under a mild but necessary condition completeness of the method is proven. As an application, we prove strong normalisation for barrecursion in higher types combined with polymorphism and non-deterministic choice. (shrink)

BL-algebras rise as Lindenbaum algebras from many valued logic introduced by Hájek [2]. In this paper Boolean ds and implicative ds of BL-algebras are defined and studied. The following is proved to be equivalent: (i) a ds D is implicative, (ii) D is Boolean, (iii) L/D is a Boolean algebra. Moreover, a BL-algebra L contains a proper Boolean ds iff L is bipartite. Local BL-algebras, too, are characterized. These results generalize some theorems presented in [4], [5], [6] for MV-algebras which (...) are BL-algebras fulfiling an additional double negation law x = x **. (shrink)

In this paper, we shall present a generalization of phrase structure grammar, in which all functional categories have type restrictions, that is, their argument types are specific domains. In ordinary phrase structure grammar, there is just one universal domain of individuals. The grammar does not make a distinction between verbs and adjectives in terms of domains of applicability. Consequently, it fails to distinguish between sentences like every line intersects every line, which is well typed, and every line intersects every (...) point, which is ill typed.Our generalization relates to ordinary phrase structure grammar in the same way as the higherlevel constructive type theory of Martin-Löf relates to the simple type theory of Church . Simple type theory has been used in linguistics and related with phrase structure grammar, especially in the tradition based on the work of Montague .Our definition of the grammar will be more formal than Montague's in the sense that we shall use a formal metalanguage, that of constructive type theory, for defining both the object language and its interpretation. The grammar, both syntax and semantics, is thus readily implementable in the type-theoretical proof system ALF . Inside type theory, a distinction can be made between the object language and the model, in other words, between syntactic and semantic types. It will turn out that the object language cannot be defined independently of the model, as in ordinary Tarski semantics. This is a direct consequence of introducing the typing restrictions.The grammar presented here can be seen as a formal linguistic elaboration of the work presented in Ranta 1991 and 1994. The organization of generative grammar as categorial grammar followed by sugaring should now look more familiar to the linguist, as the grammatical formalism on which sugaring operates is no longer full type theory but a set of phrase structure trees. (shrink)

A filter of a sentential logic ? is Leibniz when it is the smallest one among all the ?-filters on the same algebra having the same Leibniz congruence. This paper studies these filters and the sentential logic ?+ defined by the class of all ?-matrices whose filter is Leibniz, which is called the strong version of ?, in the context of protoalgebraic logics with theorems. Topics studied include an enhanced Correspondence Theorem, characterizations of the weak algebraizability of ?+ and of (...) the explicit definability of Leibniz filters, and several theorems of transfer of metalogical properties from ? to ?+. For finitely equivalential logics stronger results are obtained. Besides the general theory, the paper examines the examples of modal logics, quantum logics and Łukasiewicz's finitely-valued logics. One finds that in some cases the existence of a weak and a strong version of a logic corresponds to well-known situations in the literature, such as the local and the global consequences for normal modal logics; while in others these constructions give an independent interest to the study of other lesser-known logics, such as the lattice-based many-valued logics. (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)

This paper describes a novel pedagogical software program that can be seen as an online companion to one of the standard textbooks of formal natural language semantics, Heim and Kratzer (1998). The Penn Lambda Calculator is a multifunctional application designed for use in standard graduate and undergraduate introductions to formal semantics: Teachers can use the application to demonstrate complex semantic derivations in the classroom and modify them interactively, and students can use it to work on problem sets provided by (...) the teacher. The program supports demonstrations and exercises in two main areas: (1) performing beta reduction in the simply typed lambda calculus; (2) application of the bottom-up algorithm for computing the compositional semantics of natural language syntax trees. The program is able to represent the full range of phenomena covered in the Heim and Kratzer textbook by function application, predicate modification, and lambda abstraction. This includes phenomena such as intersective adjectives, relative clauses and quantifier raising. In the student use case, emphasis has been placed on providing “live” feedback for incorrect answers. Heuristics are used to detect the most frequent student errors and to return specific, interactive suggestions. (shrink)

Corcoran, John. 2005. Meanings of word: type-occurrence-token. Bulletin of Symbolic Logic 11(2005) 117. -/- Once we are aware of the various senses of ‘word’, we realize that self-referential statements use ambiguous sentences. If a statement is made using the sentence ‘this is a pronoun’, is the speaker referring to an interpreted string, a string-type, a string-occurrence, a string-token, or what? The listeners can wonder “this what?”. -/- John Corcoran, Meanings of word: type-occurrence-token Philosophy, University at Buffalo, Buffalo, NY 14260-4150 E-mail: (...) [email protected] The four-letter written-English expression ‘word’, which plays important roles in applications and expositions of logic and philosophy of logic, is ambiguous (multisense, or polysemic) in that it has multiple normal meanings (senses, or definitions). Several of its meanings are vague (imprecise, or indefinite) in that they admit of borderline (marginal, or fringe) cases. This paper juxtaposes, distinguishes, and analyses several senses of ‘word’ focusing on a constellation of senses analogous to constellations of senses of other expression words such as ‘expression’, ‘symbol’, ‘character’, ‘letter’, ‘term’, ‘phrase’, ‘formula’, ‘sentence’, ‘derivation’, ‘paragraph’, and ‘discourse’. Consider, e.g., the word ‘letter’. In one sense there are exactly twenty-six letters (letter-types or ideal letters) in the English alphabet and there are exactly four letters in the word ‘letter’. In another sense, there are exactly six letters (letter-repetitions or letter-occurrences) in the word-type ‘letter’. In yet another sense, every new inscription (act of writing or printing) of ‘letter’ brings into existence six new letters (letter-tokens or ink-letters) and one new word that had not previously existed. The number of letter-occurrences (occurrences of a letter-type) in a given word-type is the same as the number of letter-tokens (tokens of a letter-type) in a single token of the given word. Many logicians fail to distinguish “token” from “occurrence” and a few actually confuse the two concepts. Epistemological and ontological problems concerning word-types, word-occurrences, and word-tokens are described in philosophically neutral terms. This paper presents a theoretical framework of concepts and principles concerning logicography, including use of English in logic. The framework is applied to analytical exposition and critical evaluation of classic passages in the works of philosophers and logicians including Boole, Peirce, Frege, Russell, Tarski, Church and Quine. This paper is intended as a philosophical sequel to Corcoran et al. “String Theory”, Journal of Symbolic Logic 39(1974) 625-637. https://www.academia.edu/s/cdfa6c854e?source=link -/- . (shrink)

We show that some well known theorems in topology may not be true without the axiom of choice.

The main notion dealt with in this article is where A is a Boolean algebra. A partition of 1 is a family ofnonzero pairwise disjoint elements with sum 1. One of the main reasons for interest in this notion is from investigations about maximal almost disjoint families of subsets of sets X, especially X=ω. We begin the paper with a few results about this set-theoretical notion.Some of the main results of the paper are:• (1) If there is a maximal family (...) of size λ≥κ of pairwise almost disjoint subsets of κ each of size κ, then there is a maximal family of size λ of pairwise almost disjoint subsets of κ+ each of size κ.• (2) A characterization of the class of all cardinalities of partitions of 1 in a product in terms of such classes for the factors; and a similar characterization for weak products.• (3) A cardinal number characterization of sets of cardinals with a largest element which are for some BA the set of all cardinalities of partitions of 1 of that BA.• (4) A computation of the set of cardinalities of partitions of 1 in a free product of finite-cofinite algebras. (shrink)

Let ω be a Kolmogorov–Chaitin random sequence with ω1: n denoting the first n digits of ω. Let P be a recursive predicate defined on all finite binary strings such that the Lebesgue measure of the set {ω|∃nP(ω1: n )} is a computable real α. Roughly, P holds with computable probability for a random infinite sequence. Then there is an algorithm which on input indices for any such P and α finds an n such that P holds within the first (...) n digits of ω or not in ω at all. We apply the result to the halting probability Ω and show that various generalizations of the result fail. (shrink)

The new concept of lambda calculi with monotone inductive types is introduced byhelp of motivations drawn from Tarski's fixed-point theorem (in preorder theory) andinitial algebras and initial recursive algebras from category theory. They are intendedto serve as formalisms for studying iteration and primitive recursion ongeneral inductively given structures. Special accent is put on the behaviour ofthe rewrite rules motivated by the categorical approach, most notably on thequestion of strong normalization (i.e., the impossibility of an infinitesequence of successive (...) rewrite steps). It is shown that this key propertyhinges on the concrete formulation. The canonical system of monotone inductivetypes, where monotonicity is expressed by a monotonicity witness beinga term expressing monotonicity through its type, enjoys strong normalizationshown by an embedding into the traditional system of non-interleavingpositive inductive types which, however, has to be enriched by the parametricpolymorphism of system F. Restrictions to iteration on monotone inductive typesalready embed into system F alone, hence clearly displaying the differencebetween iteration and primitive recursion with respect to algorithms despitethe fact that, classically, recursion is only a concept derived from iteration. (shrink)

This paper studies intersection and union type assignment for the calculus , a proof-term syntax for Gentzen’s classical sequent calculus, with the aim of defining a type-based semantics, via setting up a system that is closed under conversion. We will start by investigating what the minimal requirements are for a system, for to be complete ; this coincides with System , the notion defined in Dougherty et al. [18]; however, we show that this system is not sound (...) , so our goal cannot be achieved. We will then show that System is also not complete, but can recover from this by presenting System as an extension of and showing that it satisfies completeness; it still lacks soundness. We show how to restrict so that it satisfies soundness as well by limiting the applicability of certain type assignment rules, but only when limiting reduction to call-by-name or call-by-value reduction; in restricting the system this way, we sacrifice completeness. These results when combined show that, with respect to full reduction, it is not possible to define a sound and complete intersection and union type assignment system for. (shrink)

We study the filter ℒ*(A) of computably enumerable supersets (modulo finite sets) of an r-maximal set A and show that, for some such set A, the property of being cofinite in ℒ*(A) is still Σ0 3-complete. This implies that for this A, there is no uniformly computably enumerable “tower” of sets exhausting exactly the coinfinite sets in ℒ*(A).

Continuing [6], [8] and [16], we study the consequences of the weak Freese-Nation property of (?(ω),⊆). Under this assumption, we prove that most of the known cardinal invariants including all of those appearing in Cichoń's diagram take the same value as in the corresponding Cohen model. Using this principle we could also strengthen two results of W. Just about cardinal sequences of superatomic Boolean algebras in a Cohen model. These results show that the weak Freese-Nation property of (?(ω),⊆) captures many (...) of the features of Cohen models and hence may be considered as a principle axiomatizing a good portion of the combinatorics available in Cohen models. (shrink)