Higher-Order Logic

We develop a theory of necessity operators within a version of higher-order logic that is neutral about how fine-grained reality is. The theory is axiomatized in terms of the primitive of *being a necessity*, and we show how the central notions in the philosophy of modality can be recovered from it. Various questions are formulated and settled within the framework, including questions about the ordering of necessities under strength, the existence of broadest necessities satisfying various logical conditions, and questions about (...) their logical behaviour. We also wield the framework to probe the conditions under which a logicist account of necessities is possible, in which the theory is completely reducible to logic. (shrink)

This paper investigates the connection between two recent trends in philosophy: higher-orderism and conceptual engineering. Higher-orderists use higher-order quantifiers (in particular quantifiers binding variables that occupy the syntactic positions of predicates) to express certain key metaphysical doctrines, such as the claim that there are properties. I argue that, on a natural construal, the higher-orderist approach involves an engineering project concerning, among others, the concept of existence. I distinguish between a modest construal of this project, on which it aims at engineering (...) higher-order analogues of the familiar notion of first-order existence, and an ambitious construal, on which it additionally aims at engineering a broadened notion of existence that subsumes first-order and higher-order existence. After identifying a substantial problem for the ambitious project, I investigate a possible response which is based on adopting a cumulative type theory as the background higher-order logic. While effective against the problem at hand, this strategy turns out to undermine a major reason to embrace higher-orderism in the first place, namely the idea that higher-orderism dissolves a range of otherwise intractable debates in metaphysics. Higher-orderists are therefore best advised to pursue their engineering project on the modest variant and against the background of standard type theory. (shrink)

What is the relation between metaphysical necessity and essence? This paper defends the view that the relation is one of identity: metaphysical necessity is a special case of essence. My argument consists in showing that the best joint theory of essence and metaphysical necessity is one in which metaphysical necessity is just a special case of essence. The argument is made against the backdrop of a novel, higher-order logic of essence (HLE), whose core features are introduced in the first part (...) of the paper. The second part investigates the relation between metaphysical necessity and essence in the context of HLE. Reductive hypotheses are among the most natural hypotheses to be explored in the context of HLE. But they also have to be weighed against their nonreductive rivals. I investigate three different reductive hypotheses and argue that two of them fare better than their non-reductive rivals: they are simpler, more natural, and more systematic. Specifically, I argue that one candidate reduction, according to which metaphysical necessity is truth in virtue of the nature of all propositions, is superior to the others, including one proposed by Kit Fine, according to which metaphysical necessity is truth in virtue of the nature of all objects. The paper concludes by offering some reasons to think that the best joint theory of essence and metaphysical necessity is one in which the logic of metaphysical necessity includes S4, but not S5. (shrink)

Subverting a once widely held Quinean paradigm, there is a growing consensus among philosophers of logic that higher-order quantifiers (which bind variables in the syntactic position of predicates and sentences) are a perfectly legitimate and useful instrument in the logico-philosophical toolbox, while neither being reducible to nor fully explicable in terms of first-order quantifiers (which bind variables in singular term position). This article discusses the impact of this quantificational paradigm shift on metaphysics, focussing on theories of properties, propositions, and identity, (...) as well as on the metaphysics of modality. (shrink)

Logic Works is a critical and extensive introduction to logic. It asks questions about why systems of logic are as they are, how they relate to ordinary language and ordinary reasoning, and what alternatives there might be to classical logical doctrines. It considers how logical analysis can be applied to carefully represent the reasoning employed in academic and scientific work, better understand that reasoning, and identify its hidden premises. Aiming to be as much a reference work and handbook for further, (...) independent study as a course text, it covers more material than is typically covered in an introductory course. -/- Topics include: translation, proofs, and trees for sentential and predicate logic with identity, definite descriptions, and functional terms; normal forms; proofs and trees for the principal normal modal systems; an introduction to second order and quantified modal logic; formal syntax and semantics; mathematical induction; metatheory for many of these systems; semantics and trees for free logic, intuitionistic logic, and three-valued and paraconsistent logics. -/- A companion website contains a detailed student solutions manual with a running commentary on all starred exercises and a set of editable slides for instructors to customize their courses. (shrink)

The aim of this volume is to open up new perspectives and to raise new research questions about a unified approach to truth, modalities, and propositional attitudes. The volume's essays are grouped thematically around different research questions. The first theme concerns the tension between the theoretical role of the truth predicate in semantics and its expressive function in language. The second theme of the volume concerns the interaction of truth with modal and doxastic notions. The third theme covers higher-order solutions (...) to the semantic and modal paradoxes, providing an alternative to first-order solutions embraced in the first two themes. This book will be of interest to researchers working in epistemology, logic, philosophy of logic, philosophy of language, philosophy of mathematics, and semantics. (shrink)

If we replace first-order logic by second-order logic in the original definition of Gödel’s inner model L, we obtain the inner model of hereditarily ordinal definable sets [33]. In this paper...

Prior to Kripke's seminal work on the semantics of modal logic, McKinsey offered an alternative interpretation of the necessity operator, inspired by the Bolzano-Tarski notion of logical truth. According to this interpretation, `it is necessary that A' is true just in case every sentence with the same logical form as A is true. In our paper, we investigate this interpretation of the modal operator, resolving some technical questions, and relating it to the logical interpretation of modality and some views in (...) modal metaphysics. In particular, we present an hitherto unpublished solution to problems 41 and 42 from Friedman's 102 problems, which uses a different method of proof from the solution presented in the paper of Tadeusz Prucnal. (shrink)

In explaining the notion of a fundamental property or relation, metaphysicians will often draw an analogy with languages. The fundamental properties and relations stand to reality as the primitive predicates and relations stand to a language: the smallest set of vocabulary God would need in order to write the “book of the world.” This paper attempts to make good on this metaphor. To that end, a modality is introduced that, put informally, stands to propositions as logical truth stands to sentences. (...) The resulting theory, formulated in higher-order logic, also vindicates the Humean idea that fundamental properties and relations are freely recombinable and a variant of the structural idea that propositions can be decomposed into their fundamental constituents via logical operations. Indeed, it is seen that, although these ideas are seemingly distinct, they are not independent, and fall out of a natural and general theory about the granularity of reality. (shrink)

Higher-order realists about properties express their view that there are properties with the help of higher-order rather than first-order quantifiers. They claim two types of advantages for this way of formulating property realism. First, certain gridlocked debates about the nature of properties, such as the immanentism versus transcendentalism dispute, are taken to be dissolved. Second, a further such debate, the tropes versus universals dispute, is taken to be resolved. In this paper I first argue that higher-order realism does not in (...) fact resolve the tropes versus universals dispute. In a constructive spirit, I then develop higher-order realism in a way that leads to a dissolution, rather than a resolution, of this dispute too. (shrink)

We introduce a herbrandized functional interpretation of a first-order semi-intuitionistic extension of Heyting Arithmetic and study its main properties. We then extend the interpretation to a certain system of second-order arithmetic which includes a (classically false) formulation of the FAN principle and weak König's lemma. It is shown that any first-order formula provable in this system is classically true. It is perhaps worthy of note that, in our interpretation, second-order variables are interpreted by finite sets of natural numbers.

Proofs from assumptions are amongst the most fundamental reasoning techniques. Yet the precise nature of assumptions is still an open topic. One of the most prominent conceptions is the placeholder view of assumptions generally associated with natural deduction for intuitionistic propositional logic. It views assumptions essentially as holes in proofs, either to be filled with closed proofs of the corresponding propositions via substitution or withdrawn as a side effect of some rule, thus in effect making them an auxiliary notion subservient (...) to proper propositions. The Curry–Howard correspondence is typically viewed as a formal counterpart of this conception. I will argue against this position and show that even though the Curry–Howard correspondence typically accommodates the placeholder view of assumptions, it is rather a matter of choice, not a necessity, and that another more assumption-friendly view can be adopted. (shrink)

We investigate the strength of a randomness notion ${\cal R}$ as a set-existence principle in second-order arithmetic: for each Z there is an X that is ${\cal R}$-random relative to Z. We show that the equivalence between 2-randomness and being infinitely often C-incompressible is provable in $RC{A_0}$. We verify that $RC{A_0}$ proves the basic implications among randomness notions: 2-random $\Rightarrow$ weakly 2-random $\Rightarrow$ Martin-Löf random $\Rightarrow$ computably random $\Rightarrow$ Schnorr random. Also, over $RC{A_0}$ the existence of computable randoms is equivalent (...) to the existence of Schnorr randoms. We show that the existence of balanced randoms is equivalent to the existence of Martin-Löf randoms, and we describe a sense in which this result is nearly optimal. (shrink)

Principia Logico-Metaphysica contains a foundational logical theory for metaphysics, mathematics, and the sciences. It includes a canonical development of Abstract Object Theory [AOT], a metaphysical theory that distinguishes between ordinary and abstract objects.This article reports on recent work in which AOT has been successfully represented and partly automated in the proof assistant system Isabelle/HOL. Initial experiments within this framework reveal a crucial but overlooked fact: a deeply-rooted and known paradox is reintroduced in AOT when the logic of complex terms is (...) simply adjoined to AOT’s specially formulated comprehension principle for relations. This result constitutes a new and important paradox, given how much expressive and analytic power is contributed by having the two kinds of complex terms in the system. Its discovery is the highlight of our joint project and provides strong evidence for a new kind of scientific practice in philosophy, namely, computational metaphysics.Our results were made technically possible by a suitable adaptation of Benzmüller’s metalogical approach to universal reasoning by semantically embedding theories in classical higher-order logic. This approach enables one to reuse state-of-the-art higher-order proof assistants, such as Isabelle/HOL, for mechanizing and experimentally exploring challenging logics and theories such as AOT. Our results also provide a fresh perspective on the question of whether relational type theory or functional type theory better serves as a foundation for logic and metaphysics. (shrink)

We introduce a new axiom called inductive dichotomy, a weak variant of the axiom of inductive definition, and analyze the relationships with other variants of inductive definition and with related axioms, in the general second order framework, including second order arithmetic, second order set theory and higher order arithmetic. By applying these results to the investigations on the determinacy axioms, we show the following. (i) Clopen determinacy is consistency-wise strictly weaker than open determinacy in these frameworks, except second order arithmetic; (...) this is an enhancement of Schweber–Hachtman separation of open and clopen determinacy into the consistency-wise separation. (ii) Hausdorff–Kuratowski hierarchy of differences of opens is faithfully reflected by the hierarchy of consistency strengths of corresponding parameter-free determinacies in the aforementioned frameworks; this result is valid also in second order arithmetic only except clopen determinacy. (shrink)

An increasing amount of twenty-first century metaphysics is couched in explicitly hyperintensional terms. A prerequisite of hyperintensional metaphysics is that reality itself be hyperintensional: at the metaphysical level, propositions, properties, operators, and other elements of the type hierarchy, must be more fine-grained than functions from possible worlds to extensions. In this paper I develop, in the setting of type theory, a general framework for reasoning about the granularity of propositions and properties. The theory takes as primitive the notion of a (...) substitution on a proposition (property, etc.) and, among other things, uses this idea to elucidate a number of theoretically important distinctions. A class of structures are identified which can be used to model a wide range of positions about the granularity of reality; certain of these structures are seen to receive a natural treatment in the category of M-sets. (shrink)

A number of `no-proposition' approaches to the liar paradox find themselves implicitly committed to a moderate disquotational principle: the principle that if an utterance of the sentence `$P$' says anything at all, it says that $P$ (with suitable restrictions). I show that this principle alone is responsible for the revenge paradoxes that plague this view. I instead propose a view in which there are several closely related language-world relations playing the `semantic expressing' role, none of which is more central to (...) semantic theorizing than any other. I use this thesis about language and the negative result about disquotation to motivate the view that people do say things with utterances of paradoxical sentences, although they do not say the proposition you'd always expect, as articulated with a disquotational principle. (shrink)

We show that there is a [Formula: see text]-model of second-order arithmetic in which the choice scheme holds, but the dependent choice scheme fails for a [Formula: see text]-assertion, confirming a conjecture of Stephen Simpson. We obtain as a corollary that the Reflection Principle, stating that every formula reflects to a transitive set, can fail in models of [Formula: see text]. This work is a rediscovery by the first two authors of a result obtained by the third author in [V. (...) G. Kanovei, On descriptive forms of the countable axiom of choice, Investigations on nonclassical logics and set theory, Work Collect., Moscow, 3-136 ]. (shrink)

We study the logical and computational properties of basic theorems of uncountable mathematics, including the Cousin and Lindelöf lemma published in 1895 and 1903. Historically, these lemmas were among the first formulations of open-cover compactness and the Lindelöf property, respectively. These notions are of great conceptual importance: the former is commonly viewed as a way of treating uncountable sets like e.g. [Formula: see text] as “almost finite”, while the latter allows one to treat uncountable sets like e.g. [Formula: see text] (...) as “almost countable”. This reduction of the uncountable to the finite/countable turns out to have a considerable logical and computational cost: we show that the aforementioned lemmas, and many related theorems, are extremely hard to prove, while the associated sub-covers are extremely hard to compute. Indeed, in terms of the standard scale, a proof of these lemmas requires at least the full extent of second-order arithmetic, a system originating from Hilbert–Bernays’ Grundlagen der Mathematik. This observation has far-reaching implications for the Grundlagen’s spiritual successor, the program of Reverse Mathematics, and the associated Gödel hierarchy. We also show that the Cousin lemma is essential for the development of the gauge integral, a generalization of the Lebesgue and improper Riemann integrals that also uniquely provides a direct formalization of Feynman’s path integral. (shrink)

In this article I investigate the phenomenon of minimum and minimal models of second-order set theories, focusing on Kelley–Morse set theory KM, Gödel–Bernays set theory GB, and GB augmented with the principle of Elementary Transfinite Recursion. The main results are the following. (1) A countable model of ZFC has a minimum GBC-realization if and only if it admits a parametrically definable global well order. (2) Countable models of GBC admit minimal extensions with the same sets. (3) There is no minimum (...) transitive model of KM. (4) There is a minimum β-model of GB+ETR. The main question left unanswered by this article is whether there is a minimum transitive model of GB+ETR. (shrink)

This paper explores the impact of quantification into predicate position on the metaphysics of properties, arguing that two familiar debates about properties are fundamentally altered by recasting them in a second-order setting. Two theories of properties are outlined, differing over whether the existence of properties is expressed using first-order or second-order quantifiers. It is argued that the second-order theory: provides good reason to regard debate about the locations of properties as contentless; resolves debate about whether properties are particulars or universals (...) in favour of universals. (shrink)

In this paper the logic of broad necessity is explored. Definitions of what it means for one modality to be broader than another are formulated, and it is proven, in the context of higher-order logic, that there is a broadest necessity, settling one of the central questions of this investigation. It is shown, moreover, that it is possible to give a reductive analysis of this necessity in extensional language. This relates more generally to a conjecture that it is not possible (...) to define intensional connectives from extensional notions. This conjecture is formulated precisely in higher-order logic, and concrete cases in which it fails are examined. The paper ends with a discussion of the logic of broad necessity. It is shown that the logic of broad necessity is a normal modal logic between S4 and Triv, and that it is consistent with a natural axiomatic system of higher-order logic that it is exactly S4. Some philosophical reasons to think that the logic of broad necessity does not include the S5 principle are given. (shrink)

We explore the view that Frege's puzzle is a source of straightforward counterexamples to Leibniz's law. Taking this seriously requires us to revise the classical logic of quantifiers and identity; we work out the options, in the context of higher-order logic. The logics we arrive at provide the resources for a straightforward semantics of attitude reports that is consistent with the Millian thesis that the meaning of a name is just the thing it stands for. We provide models to show (...) that some of these logics are non-degenerate. (shrink)

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

We extend results of Bonet, Buss and Pitassi on Bondy’s Theorem and of Nozaki, Arai and Arai on Bollobás’ Theorem by proving that Frankl’s Theorem on the trace of sets has quasipolynomial size Frege proofs. For constant values of the parametert, we prove that Frankl’s Theorem has polynomial size AC0-Frege proofs from instances of the pigeonhole principle.

That every first-order theory has a coherent conservative extension is regarded by some as obvious, even trivial, and by others as not at all obvious, but instead remarkable and valuable; the result is in any case neither sufficiently well-known nor easily found in the literature. Various approaches to the result are presented and discussed in detail, including one inspired by a problem in the proof theory of intermediate logics that led us to the proof of the present paper. It can (...) be seen as a modification of Skolem’s argument from 1920 for his “Normal Form” theorem. “Geometric” being the infinitary version of “coherent”, it is further shown that every infinitary first-order theory, suitably restricted, has a geometric conservative extension, hence the title. The results are applied to simplify methods used in reasoning in and about modal and intermediate logics. We include also a new algorithm to generate special coherent implications from an axiom, designed to preserve the structure of formulae with relatively little use of normal forms. (shrink)

This paper uses the resources of higher-order logic to articulate a Fregean conception of predicate reference, and of word-world relations more generally, that is immune to the concept horse problem. The paper then addresses a prominent style of expressibility problem for views of broadly this kind, versions of which are due to Linnebo, Hale, and Wright.

Many recent writers in the philosophy of mathematics have put great weight on the relative categoricity of the traditional axiomatizations of our foundational theories of arithmetic and set theory. Another great enterprise in contemporary philosophy of mathematics has been Wright's and Hale's project of founding mathematics on abstraction principles. In earlier work, it was noted that one traditional abstraction principle, namely Hume's Principle, had a certain relative categoricity property, which here we term natural relative categoricity. In this paper, we show (...) that most other abstraction principles are not naturally relatively categorical, so that there is in fact a large amount of incompatibility between these two recent trends in contemporary philosophy of mathematics. To better understand the precise demands of relative categoricity in the context of abstraction principles, we compare and contrast these constraints to stability-like acceptability criteria on abstraction principles, the Tarski-Sher logicality requirements on abstraction principles studied by Antonelli and Fine, and supervaluational ideas coming out of Hodes' work. (shrink)

This paper begins the study of first-order functions, which are a generalization of truth-functions. The concepts of truth-table and systems of truth-functions, both introduced in propositional logic by Post, are also generalized and studied in the quantificational setting. The general facts about these concepts are given in the first five sections, and constitute a “general theory” of first-order functions. The central theme of this paper is the relation of definition among notions expressed by formulas of first-order logic. We emphasize that (...) logic is not concerned only with the consequence relation among notions expressed by formulas. It also attends to the relation of definition among notions, where a notion is defined from other notions. Sections 5 and 6 deal exclusively with the relation of definition among notions expressed by formulas of first-order logic. In these sections, we study the systems of first-order functions, which are the sets of first-order functions closed under definitions. Sections 7 and 8 are concerned with the relativization of first-order functions to a class of structures. The relativization to a class of structures is a fundamental operation which is used in order to relate the theory of first-order functions with set theory and first-order model theory, a subject which we have barely scratched the surface. The apparatus developed in this paper enables us to define what is a vehicle for the foundation of classical mathematics in set theory, and, in Sect. 8, we prove that first-order logic with one binary predicate variable is not a minimal vehicle for the foundation of classical mathematics in set theory. Sections 9 and 10 introduce further operations and ideals of first-order functions. Besides some results on the influence of the arguments of a first-order function, a result about definability is proved in Sect. 10.1. It is this theorem that provides necessary and sufficient conditions for a first-order function to be in a finitely generated ideal. In Sect. 11, this result is applied to the problem of predicate definability in classes of structures, the problem with which Beth’s theorem dealt in the case of elementary classes. (shrink)

Both second-order logic and set theory can be used as a foundation for mathematics, that is, as a formal language in which propositions of mathematics can be expressed and proved. We take it upon ourselves in this paper to compare the two approaches, second-order logic on one hand and set theory on the other hand, evaluating their merits and weaknesses. We argue that we should think of first-order set theory as a very high-order logic.

In this thesis I provide a survey over different approaches to second-order logic and its interpretation, and introduce a novel approach. Of special interest are the questions whether second-order logic can count as logic in some proper sense of logic, and what epistemic status it occupies. More specifically, second-order logic is sometimes taken to be mathematical, a mere notational variant of some fragment of set theory. If this is the case, it might be argued that it does not have the (...) "epistemic innocence" which would be needed for, e.g., foundational programmes in mathematics for which second-order logic is sometimes used. I suggest a Deductivist conception of logic, that characterises logical consequence by means of inference rules, and argue that on this conception second-order logic should count as logic in the proper sense. (shrink)