Simple type theory is a higher-order predicate logic for reasoning about truth values, individuals, and simply typed total functions. We present in this paper a version of simple type theory, called PF*, in which functions may be partial and types may have subtypes. We define both a Henkin-style general models semantics and an axiomatic system for PF*, and we prove that the axiomatic system is complete with respect to the general models semantics. We also define a notion (...) of an interpretation of one PF* theory in another. PF* is intended as a foundation for mechanized mathematics. It is the basis for the logic of, an Interactive Mathematical Proof System developed at The MITRE Corporation. (shrink)

We introduce a notion of simplicity for types in discretely ordered first order structures. We prove that all the structure on the locus of a simple type is induced exclusively by the ordering relation. As an application we determine all possible expansions of satisfying CB = 1.

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

Simple type theory is a higher-order predicate logic for reasoning about truth values, individuals, and simply typed total functions. We present in this paper a version of simple type theory, called PF*, in which functions may be partial and types may have subtypes. We define both a Henkin-style general models semantics and an axiomatic system for PF*, and we prove that the axiomatic system is complete with respect to the general models semantics. We also define a notion (...) of an interpretation of one PF* theory in another. PF* is intended as a foundation for mechanized mathematics. It is the basis for the logic of , an Interactive Mathematical Proof System developed at The MITRE Corporation. (shrink)

We present various results regarding the decidability of certain sets of sentences by Simple Type Theory. First, we introduce the notion of decreasing sentence, and prove that the set of decreasing sentences is undecidable by Simple Type Theory with infinitely many zero-type elements ; a result that follows directly from the fact that every sentence is equivalent to a decreasing sentence. We then establish two different positive decidability results for a weak subtheory of math formula. Namely, the decidability (...) of math formula and math formula. Finally, we present some consequences for the set of existential-universal sentences. All the above results have direct implications for Quine's theory of “New Foundations” and its weak subtheory math formula. (shrink)

We present a cut-elimination proof for simple type theory with an axiom of choice formulated in the language with an epsilon-symbol. The proof is modeled after Takahashi's proof of cut-elimination for simple type theory with extensionality. The same proof works when types are restricted, for example for second-order classical logic with an axiom of choice.

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

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

The decidability of the logic of pure ticket entailment means that the problem of inhabitation of simple types by combinators over the base { B, B′, I, W } is decidable too. Type-assignment systems are often formulated as natural deduction systems. However, our decision procedure for this logic, which we presented in earlier papers, relies on two sequent calculi and it does not yield directly a combinator for a theorem of ${T_\to}$. Here we describe an algorithm to extract (...) an inhabitant from a sequent calculus proof—without translating the proof into another proof system. (shrink)

As emphasized by Alonzo Church and David Kaplan (Church 1974, Kaplan 1975), the philosophies of language of Frege and Russell incorporate quite different methods of semantic analysis with different basic concepts and different ontologies. Accordingly we distinguish between a Fregean and a Russellian tradition in intensional semantics. The purpose of this paper is to pursue the Russellian alternative and to provide a language of intensional logic with a model-theoretic semantics. We also discuss the so-called Russell-Myhill paradox that threatens simple (...) Russellian type theory if propositions satisfies very strict principles of individuation. One way of avoiding the paradox is to adopt a ramified rather than a simple theory of types. (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)

We continue work of Shelah on the cardinality of families of pairwise incompatible types in simple theories obtaining characterizations of simple and supersimple theories. We develop a local analysis of the number of types in simple theories and we find a new example of a simple unstable theory.

In this paper a class of simple theories, called the low theories is developed, and the following is proved. Theorem. Let T be a low theory. A set and a, b elements realizing the same strong type over A. Then, a and b realized the same Lascar strong type over A.

We solve a question of McLaughlin by showing that if A is a regressive co-simple isol, there is a co-simple regressive isol B such that the intersection type of A and B is trivial. The proof is a nonuniform 0 priority argument that can be viewed as the execution of a single strategy from a 0-argument. We establish some limit on the properties of such pairs by showing that if AxB has low degree, then the intersection type of (...) A and B cannot be trivial. (shrink)

Let T be simple, work in Ceq over a boundedly closed set. Let p ∈ S(θ) be internal in a quasi-stably-embedded type-definable set Q (e.g., Q is definable or stably-embedded) and suppose (p, Q) is ACL-embedded in Q (see definitions below). Then Aut(p/Q) with its action on pC is type-definable in Ceq over θ. In particular, if p ∈ S(θ) is internal in a stably-embedded type-definable set Q, and pC υ Q is stably-embedded, then Aut(p/Q) is type-definable with its (...) action on pC. (shrink)

Perfect for students with no background in logic or philosophy, Simple Formal Logic provides a full system of logic adequate to handle everyday and philosophical reasoning. By keeping out artificial techniques that aren’t natural to our everyday thinking process, Simple Formal Logic trains students to think through formal logical arguments for themselves, ingraining in them the habits of sound reasoning. Simple Formal Logic features: a companion website with abundant exercise worksheets, study supplements (including flashcards for symbolizations and (...) for deduction rules), and instructor’s manual two levels of exercises for beginning and more advanced students a glossary of terms, abbreviations and symbols. This book arose out of a popular course that the author has taught to all types of undergraduate students at Loyola University Chicago. He teaches formal logic without the artificial methods–methods that often seek to solve farfetched logical problems without any connection to everyday and philosophical argumentation. The result is a book that teaches easy and more intuitive ways of grappling with formal logic–and is intended as a rigorous yet easy-to-follow first course in logical thinking for philosophy majors and non-philosophy majors alike. (shrink)

Let T be a complete countable first-order theory such that every ultrapower of a model of T is saturated. If T has a model omitting a type p in every cardinality $ then T has a model omitting p in every cardinality. There is also a related theorem, and an example showing the $\beth_\omega$ cannot be improved.