We introduce a certain extension of -calculus, and show that it has the Church-Rosser property. The associated open-term extensional combinatory algebra is used as a basis to construct models for theories of Explict Mathematics (formulated in the language of "types and names") with positive stratified comprehension. In such models, types are interpreted as collections of solutions (of terms) w.r. to a set of numerals. Exploiting extensionality, we prove some consistency results for special ontological axioms which are refutable under (...) elementary comprehension. (shrink)

This paper is a companion to work of Feferman, Jäger, Glaß, and Strahm on the proof theory of the type two functionals μ and E1 in the context of Feferman-style applicative theories. In contrast to the previous work, we analyze these two functionals in the context of Schlüter's weakened applicative basis PRON which allows for an interpretation in the primitive recursive indices. The proof-theoretic strength of PRON augmented by μ and E1 is measured in terms of the two subsystems (...) of second order arithmetic, Π10-CA and Π11-CA, respectively. (shrink)

In this paper we define intensional models for the classical theory of types, thus arriving at an intensional type logic ITL. Intensional models generalize Henkin's general models and have a natural definition. As a class they do not validate the axiom of Extensionality. We give a cut-free sequent calculus for type theory and show completeness of this calculus with respect to the class of intensional models via a model existence theorem. After this we turn our attention to (...) applications. Firstly, it is argued that, since ITL is truly intensional, it can be used to model ascriptions of propositional attitude without predicting logical omniscience. In order to illustrate this a small fragment of English is defined and provided with an ITL semantics. Secondly, it is shown that ITL models contain certain objects that can be identified with possible worlds. Essential elements of modal logic become available within classical type theory once the axiom of Extensionality is given up. (shrink)

In this article I try to show the philosophical continuity of Russell's ideas from his paradox of classes to Principia mathematica. With this purpose, I display the main results (descriptions, substitutions and types) as moments of the same development, whose principal goal was (as in his The principles) to look for a set of primitive ideas and propositions giving an account of all mathematics in logical terms, but now avoiding paradoxes. The sole way to reconstruct this central period in (...) Russell is to resort to unpublished manuscripts, which show the publications of these years to be the extremities of one same iceberg. Thus the logical problems (doubts about propositions, matrices and functions) are parallel to the ontological (the searching for genuine logical subjects) and methodological ones (the status of eliminative reduction). Paradoxes were the cause that the kind of (constructive) definition already applied by Russell, as an inheritance of Moorean analysis, obtained a new trait: ontological elimination, which, beginning with a ?no classes theory? and the theory of descriptions, led to a new theory of judgment (already present in manuscripts from 1906), ?incomplete symbols, and logical constructions. (shrink)

We discuss a previously unnoticed resemblance between the theory of relations and predicates in The Philosophy of Logical Atomism [TPLA] by Russell and the theory of objects and names in the Tractatus Logico-Philosophicus [TLP] by Wittgenstein. Points of likeness are detected on three levels: ontology, syntax, and semantics. This analogy explains the prima facie similarities between the informal presentation of the theory of types in TPLA and the sections of the TLP devoted to this same topic. (...) Eventually, we draw some consequences concerning both sides of the analogy: for what concerns Russell, the contextual pertinence of this surprising fragment of Tractarian metaphysics and semantics is questioned on several grounds; about Wittgenstein, the interpreters who do not identify Tractarian objects with particulars are in a better position to make sense of the analogy here discovered. (shrink)

This article investigates a theory of type assignment (assigning types to lambda terms) called ETA which is intermediate in strength between the simple theory of type assignment and strong polymorphic theories like Girard’s F (Proofs and types. Cambridge University Press, Cambridge, 1989). It is like the simple theory and unlike F in that the typability and type-checking problems are solvable with respect to ETA. This is proved in the article along with three other main results: (...) (1) all primitive recursive functionals of finite type are representable in ETA; (2) every term typable in ETA has a unique normal form; (3) there is a function defined by ${{\varepsilon}_0}$ -recursion which takes every typable term to a natural number which is an upper bound to the lengths of all βη-reduction sequences starting with that term. (shrink)

This paper described a formal theory of type judgments for propositional logic notations of PM; I felt the need of my own automated type checker to check their examples. The type checker I wrote did indeed serve to help me referee the paper, but also took a rather different approach to notation and typing for propositional functions of PM, which proved worth writing up independently in our own paper: Holmes, M. Randall, “Polymorphic type– checking for the ramified theory (...) of types of Principia Mathematica”, in Fairouz Kamareddine, ed., Thirty–five Years of Automating Mathematics, Kluwer, 2003, pp. 173-215. (shrink)

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

In Russell''s Ramified Theory of Types RTT, two hierarchical concepts dominate:orders and types. The use of orders has as a consequencethat the logic part of RTT is predicative.The concept of order however, is almost deadsince Ramsey eliminated it from RTT. This is whywe find Church''s simple theory of types (which uses the type concept without the order one) at the bottom of the Barendregt Cube rather than RTT. Despite the disappearance of orders which have a (...) strong correlation with predicativity, predicative logic still plays an influential role in Computer Science.An important example is the proof checker Nuprl, which is basedon Martin-Löf''s Type Theory which uses type universes. Those type universes,and also degrees of expressions in AUTOMATH, are closely related toorders. In this paper, we show that orders have not disappeared from modern logic and computer science, rather, orders play a crucial role in understanding the hierarchy of modern systems. In order to achieve our goal, we concentrate on a subsystem of Nuprl.The novelty of our paper lies in: (1) a modest revival of Russell's orders, (2) the placing of the historical system RTT underlying the famous Principia Mathematica in a context with a modern system of computer mathematics (Nuprl) and modern type theories (Martin-Löf''s type theory and PTSs), and (3) the presentation of acomplex type system (Nuprl) as a simple and compact PTS. (shrink)

This is an open access title available under the terms of a CC BY-NC-ND 4.0 International licence. It is free to read at Oxford Scholarship Online and offered as a free PDF download from OUP and selected open access locations. This book characterizes a notion of type that covers both linguistic and non-linguistic action, and lays the foundations for a theory of action based on a Theory of Types with Records (TTR). Robin Cooper argues that a (...) class='Hi'>theory of language based on action allows the adoption of a perspective on linguistic content that is centred on interaction in dialogue; this approach is crucially different to the traditional view of natural languages as essentially similar to formal languages such as logics developed by philosophers or mathematicians. At the same time, he claims that the substantial technical advantages made by the formal language view of semantics can be incorporated into the action-based view, and that this can lead to important improvements in both intuitive understanding and empirical coverage. This enterprise uses types rather than possible worlds as commonly employed in studies of the semantics of natural language. Types are more tractable than possible worlds and offer greater potential for understanding the implementation of semantics both on machines and in biological brains. (shrink)

After an introductory discussion on Martin-Löf's Intuitionistic Theory of Types , the paper introduces the notion of assumption of high-arity variable. Then the original theory is extended in a very uniform way by means of the new assumptions. Some improvements allowed by high-arity variables are shown. The main result of the paper is a normal form theorem for HITT. The detailed proof follows a computability method ‘a la Tait’. The main consequences of the normal form theorem are: (...) the consistency of HITT, which also implies the consistency of ITT, and the computability of any judgement derived within HITT. Besides that, a canonical form theorem is shown: to any derivable judgement we can associate a canonical one whose derivation ends with an introductory rule. The standard disjunction and existential properties follow. Moreover, by using the computational interpretation of types it immediately follows that the execution of any proved correct program terminates. (shrink)

We introduce a notion of the space of types in positive model theory based on Stone duality for distributive lattices. We show that this space closely mirrors the Stone space of types in the full first-order model theory with negation (Tarskian model theory). We use this to generalise some classical results on countable models from the Tarskian setting to positive model theory.

It is already known that Fitch’s knowability paradox can be solved by typing knowledge within ramified theory of types. One of the aims of this paper is to provide a greater defence of the approach against recently raised criticism. My second goal is to make a sufficient support for an assumption which is needed for this particular application of typing knowledge but which is not inherent to ramified theory of types as such.

This paper presents a generalization of a proposal of van Benthem’s who has shown how to provide a canonical name for any object in propositional type theory. Van Benthem’s idea is to characterize any function in the hierarchy by the Boolean values the function takes for any sequence of arguments. The recursive definition of canonical names uses only the abstraction, functional application, the identity operator and the fact that we have a name for the true and the false. We (...) show that this result can be extended to the finite theory of types by the introduction of an algebra on individuals. (shrink)

I investigate why Frege rejected the theory of types, as Russell presented it to him in their correspondence. Frege claims that it commits one to violations of the law of excluded middle, but this complaint seems to rest on a dogmatic refusal to take Russell’s proposal seriously on its own terms. What is at stake is not so much the truth of a law of logic, but the structure of the hierarchy of the logical categories, something Frege seems (...) to neglect. To come to a better understanding of Frege’s response, I proceed to investigate his conception of the nature of the logical categories, and how it differs from Russell’s. I argue that, for Frege, our grasp of the logical categories cannot be severed from our grasp of the Begriffsschrift notation itself. Russell, on the other hand, attaches no such importance to notation. From Frege’s point of view, Russell has not succeeded in presenting an alternative conception of the logical hierarchy, since such a conception must go in tandem with the development of a notation. Moreover, Frege has good reasons to think that Russell’s proposal does not admit of a suitable notation. (shrink)

The classical theory of types in question is essentially the theory of Martin-Löf [1] but with the law of double negation elimination. I am ultimately interested in the theory of types as a framework for the foundations of mathematics and, for this purpose, we need to consider extensions of the theory obtained by adding ‘well-ordered types,’ for example the type N of the finite ordinals; but the unextended theory will suffice to illustrate (...) the treatment of extensional equality. (shrink)

This paper developes a relational---as opposed to a functional---theory of types. The theory is based on Hilbert and Bernays' eta operator plus the identity symbol, from which Church's lambda and the other usual operators are then defined. The logic is intended for use in the semantics of natural language.

This reissue, first published in 1971, provides a brief historical account of the Theory of Logical Types; and describes the problems that gave rise to it, its various different formulations, the difficulties connected with each, and the criticisms that have been directed against it. Professor Copi seeks to make the subject accessible to the non-specialist and yet provide a sufficiently rigorous exposition for the serious student to see exactly what the theory is and how it works.

Russell's involuted path in the development of his theory of logical types from 1903 to 1910-13 is examined and explained in terms of the development in his early philosophy of the notion of a logical subject vis-a-vis the problem of the one and many; i.e., the problem for russell, first, of a class-as-one as a logical subject as opposed to a class as many, and, secondly, of a propositional function as a single and separate logical subject as opposed (...) to existing only in the many propositions that are its values. (shrink)

We identify complete fragments of the simple theory of types with infinity and Quine’s new foundations set theory. We show that TSTI decides every sentence ϕ in the language of type theory that is in one of the following forms: ϕ=∀x1r1⋯∀xkrk∃y1s1⋯∃ylslθ where the superscripts denote the types of the variables, s1>⋯>sl, and θ is quantifier-free, ϕ=∀x1r1⋯∀xkrk∃y1s⋯∃ylsθ where the superscripts denote the types of the variables and θ is quantifier-free. This shows that NF decides every (...) stratified sentence ϕ in the language of set theory that is in one of the following forms: ϕ=∀x1⋯∀xk∃y1⋯∃ylθ where θ is quantifier-free and ϕ admits a stratification that assigns distinct values to all of the variables y1,…,yl, ϕ=∀x1⋯∀xk∃y1⋯∃ylθ where θ is quantifier-free and ϕ admits a stratification that assigns the same value to all of the variables y1,…,yl. (shrink)