Quine’s most important charge against second-, and more generally, higher-order logic is that it carries massive existential commitments. The force of this charge does not depend upon Quine’s questionable assimilation of second-order logic to set theory. Even if we take second-order variables to range over properties, rather than sets, the charge remains in force, as long as properties are individuated purely extensionally. I argue that if we interpret them as ranging over properties (...) more reasonably construed, in accordance with an abundant or deflationary conception, Quine’s charge can be resisted. This interpretation need not be seen as precluding the use of model-theoretic semantics for second-order languages; but it will preclude the use of the standard semantics, along with the more general Henkin semantics, of which it is a special case. To that extent, the approach I recommend has revisionary implications which some may find unpalatable; it is, however, compatible with the quite different special case in which the second-order variables are taken to range over definable subsets of the first-order domain, and with respect to such a semantics, some important metalogical results obtainable under the standard semantics may still be obtained. In my final section, I discuss the relations between second-order logic, interpreted as I recommend, and a strong version of schematic ancestral logic promoted in recent work by Richard Heck. I argue that while there is an interpretation on which Heck’s logic can be contrasted with second-order logic as standardly interpreted, when it is so interpreted, its differences from the more modest form of second-order logic I advocate are much less substantial, and may be largely presentational. (shrink)

“Second-order Logic” in Anderson, C.A. and Zeleny, M., Eds. Logic, Meaning, and Computation: Essays in Memory of Alonzo Church. Dordrecht: Kluwer, 2001. Pp. 61–76. -/- Abstract. This expository article focuses on the fundamental differences between second- order logic and first-order logic. It is written entirely in ordinary English without logical symbols. It employs second-order propositions and second-order reasoning in a natural way to illustrate the fact that (...) class='Hi'>second-order logic is actually a familiar part of our traditional intuitive logical framework and that it is not an artificial formalism created by specialists for technical purposes. To illustrate some of the main relationships between second-order logic and first-order logic, this paper introduces basic logic, a kind of zero-order logic, which is more rudimentary than first-order and which is transcended by first-order in the same way that first-order is transcended by second-order. The heuristic effectiveness and the historical importance of second-order logic are reviewed in the context of the contemporary debate over the legitimacy of second-order logic. Rejection of second-order logic is viewed as radical: an incipient paradigm shift involving radical repudiation of a part of our scientific tradition, a tradition that is defended by classical logicians. But it is also viewed as reactionary: as being analogous to the reactionary repudiation of symbolic logic by supporters of “Aristotelian” traditional logic. But even if “genuine” logic comes to be regarded as excluding second-order reasoning, which seems less likely today than fifty years ago, its effectiveness as a heuristic instrument will remain and its importance for understanding the history of logic and mathematics will not be diminished. Second-order logic may someday be gone, but it will never be forgotten. Technical formalisms have been avoided entirely in an effort to reach a wide audience, but every effort has been made to limit the inevitable sacrifice of rigor. People who do not know second-order logic cannot understand the modern debate over its legitimacy and they are cut-off from the heuristic advantages of second-order logic. And, what may be worse, they are cut-off from an understanding of the history of logic and thus are constrained to have distorted views of the nature of the subject. As Aristotle first said, we do not understand a discipline until we have seen its development. It is a truism that a person's conceptions of what a discipline is and of what it can become are predicated on their conception of what it has been. (shrink)

The logic of paradox, LP, is a first-order, three-valued logic that has been advocated by Graham Priest as an appropriate way to represent the possibility of acceptable contradictory statements. Second-order LP is that logic augmented with quantification over predicates. As with classical second-order logic, there are different ways to give the semantic interpretation of sentences of the logic. The different ways give rise to different logical advantages and disadvantages, and we (...) canvass several of these, concluding that it will be extremely difficult to appeal to second-order LP for the purposes that its proponents advocate, until some deep, intricate, and hitherto unarticulated metaphysical advances are made. (shrink)

We discuss the differences between first-order set theory and second-order logic as a foundation for mathematics. We analyse these languages in terms of two levels of formalization. The analysis shows that if second-order logic is understood in its full semantics capable of characterizing categorically central mathematical concepts, it relies entirely on informal reasoning. On the other hand, if it is given a weak semantics, it loses its power in expressing concepts categorically. First-order (...) set theory and second-order logic are not radically different: the latter is a major fragment of the former. (shrink)

We try to answer the question which is the “right” foundation of mathematics, second order logic or set theory. Since the former is usually thought of as a formal language and the latter as a first order theory, we have to rephrase the question. We formulate what we call the second order view and a competing set theory view, and then discuss the merits of both views. On the surface these two views seem to (...) be in manifest conflict with each other. However, our conclusion is that it is very difficult to see any real difference between the two. We analyze a phenomenon we call internal categoricity which extends the familiar categoricity results of second order logic to Henkin models and show that set theory enjoys the same kind of internal categoricity. Thus the existence of non-standard models, which is usually taken as a property of first order set theory, and categoricity, which is usually taken as a property of second order axiomatizations, can coherently coexist when put into their proper context. We also take a fresh look at complete second order axiomatizations and give a hierarchy result for second order characterizable structures. Finally we consider the problem of existence in mathematics from both points of view and find that second order logic depends on what we call large domain assumptions, which come quite close to the meaning of the axioms of set theory. (shrink)

Pure second-order logic is second-order logic without functional or first-order variables. In "Pure Second-Order Logic," Denyer shows that pure second-order logic is compact and that its notion of logical truth is decidable. However, his argument does not extend to pure second-order logic with second-order identity. We give a more general argument, based on elimination of quantifiers, which shows that any formula of pure (...) second-order logic with second-order identity is equivalent to a member of a circumscribed class of formulas. As a corollary, pure second-order logic with second-order identity is compact, its notion of logical truth is decidable, and it satisfies a pure second-order analogue of model completeness. We end by mentioning an extension to n th-order pure logics. (shrink)

The study of graph structure has advanced in recent years with great strides: finite graphs can be described algebraically, enabling them to be constructed out of more basic elements. Separately the properties of graphs can be studied in a logical language called monadic second-order logic. In this book, these two features of graph structure are brought together for the first time in a presentation that unifies and synthesizes research over the last 25 years. The author not only (...) provides a thorough description of the theory, but also details its applications, on the one hand to the construction of graph algorithms, and, on the other to the extension of formal language theory to finite graphs. Consequently the book will be of interest to graduate students and researchers in graph theory, finite model theory, formal language theory, and complexity theory. (shrink)

Ignacio Jane has argued that second-order logic presupposes some amount of set theory and hence cannot legitimately be used in axiomatizing set theory. I focus here on his claim that the second-order formulation of the Axiom of Separation presupposes the character of the power set operation, thereby preventing a thorough study of the power set of infinite sets, a central part of set theory. In reply I argue that substantive issues often cannot be separated from (...) a logic, but rather must be presupposed. I call this the logic-metalogic link. There are two facets to the logic-metalogic link. First, when a logic is entangled with a substantive issue, the same position on that issue should be taken at the meta- level as at the object level; and second, if an expression has a clear meaning in natural language, then the corresponding concept can equally well be deployed in a formal language. The determinate nature of the power set operation is one such substantive issue in set theory. Whether there is a determinate power set of an infinite set can only be presupposed in set theory, not proved, so the use of second-order logic cannot be ruled out by virtue of presupposing one answer to this question. Moreover, the legitimacy of presupposing in the background logic that the power set of an infinite set is determinate is guaranteed by the clarity and definiteness of the notions of all and of subset. This is also exactly what is required for the same presupposition to be legitimately made in an axiomatic set theory, so the use of second-order logic in set theory rather than first-order logic does not require any new metatheoretic commitments. (shrink)

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)

Under a weak set-theoretic assumption we interpret second-order logic in the monadic theory of order.

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- (...) class='Hi'>order logic. (shrink)

Second-order logic is the extension of first-order logic obtaining by introducing quantification of predicate and function variables.

In this paper, I shall provide a defence of second-order logic in the context of its use in the philosophy of mathematics. This shall be done by considering three problems that have been recently posed against this logic: (1) According to Resnik [1988], by adopting second-order quantifiers, we become ontologically committed to classes. (2) As opposed to what is claimed by defenders of second-order logic (such as Shapiro [1985]), the existence of (...) non-standard models of first-order theories does not establish the inadequacy of first—order axiomatisations (Melia [1995]). (3) In contrast with Shapiro’s suggestion (in his [1985]), second-order logic does not help us to establish referential access to mathematical objects (Azzouni [1994]). As I shall argue, each of these problems can be neatly solved by the second-order theorist. As a result, a case for second-order logic can be made. The first two problems will beconsidered rather briefly in the next section. The rest of the paper is dedicate to a discussion of the third. (shrink)

Second-order logic has a number of attractive features, in particular the strong expressive resources it offers, and the possibility of articulating categorical mathematical theories (such as arithmetic and analysis). But it also has its costs. Five major charges have been launched against second-order logic: (1) It is not axiomatizable; as opposed to first-order logic, it is inherently incomplete. (2) It also has several semantics, and there is no criterion to choose between them (...) (Putnam, J Symbol Logic 45:464–482, 1980 ). Therefore, it is not clear how this logic should be interpreted. (3) Second-order logic also has strong ontological commitments: (a) it is ontologically committed to classes (Resnik, J Phil 85:75–87, 1988 ), and (b) according to Quine (Philosophy of logic, Prentice-Hall: Englewood Cliffs, 1970 ), it is nothing more than “set theory in sheep’s clothing”. (4) It is also not better than its first-order counterpart, in the following sense: if first-order logic does not characterize adequately mathematical systems, given the existence of non - isomorphic first-order interpretations, second-order logic does not characterize them either, given the existence of different interpretations of second-order theories (Melia, Analysis 55:127–134, 1995 ). (5) Finally, as opposed to what is claimed by defenders of second-order logic [such as Shapiro (J Symbol Logic 50:714–742, 1985 )], this logic does not solve the problem of referential access to mathematical objects (Azzouni, Metaphysical myths, mathematical practice: the logic and epistemology of the exact sciences, Cambridge University Press, Cambridge, 1994 ). In this paper, I argue that the second-order theorist can solve each of these difficulties. As a result, second-order logic provides the benefits of a rich framework without the associated costs. (shrink)

Some widely accepted arguments in the philosophy of mathematics are fallacious because they rest on results that are provable only by using assumptions that the con- clusions of these arguments seek to undercut. These results take the form of bicon- ditionals linking statements of logic with statements of mathematics. George Boolos has given an argument of this kind in support of the claim that certain facts about second-order logic support logicism, the view that mathematics—or at least (...) part of it—reduces to logic. Hilary Putnam has offered a similar argument for the view that it is indifferent whether we take mathematics to be about objects or about what follows from certain postulates. In this paper I present and rebut these arguments. (shrink)

In so-called full second-order logic, the second-order variables range over all subsets and relations of the domain in question. In so-called Henkin second-order logic, every model is endowed with a set of subsets and relations which will serve as the range of the second-order variables. In our Boolean-valued second-order logic, the second-order variables range over all Boolean-valued subsets and relations on the domain. We show that (...) under large cardinal assumptions Boolean-valued second-order logic is more robust than full second-order logic. Its validity is absolute under forcing, and its Hanf and Löwenheim numbers are smaller than those of full second-order logic. (shrink)

In this paper we investigate several extensions of the first order-language with finitely many binary relations. The most interesting of the studied extensions appears to be the monadic second-order one. We show that the extended languages have the same expressive power as the first-order language over the class of all relational structures of equivalence relations in local agreement by providing appropriate translation of formulae. The decidability of the considered extensions over the above mentioned class of structures (...) is also shown. (shrink)

We prove that every monadic second-order property of the unfolding of a transition system is a monadic second-order property of the system itself. An unfolding is an instance of the general notion of graph covering. We consider two more instances of this notion. A similar result is possible for one of them but not for the other.

Second-order logic and modal logic are both, separately, major topics of philosophical discussion. Although both have been criticized by Quine and others, increasingly many philosophers find their strictures uncompelling, and regard both branches of logic as valuable resources for the articulation and investigation of significant issues in logical metaphysics and elsewhere. One might therefore expect some combination of the two sorts of logic to constitute a natural and more comprehensive background logic for metaphysics. (...) So it is somewhat surprising to find that philosophical discussion of secondorder modal logic is almost totally absent, despite the pioneering contribution of Barcan. (shrink)

We develop a set-theoretic semantics for Cocchiarella's second-order logical system . Such a semantics is a modification of the nonstandard sort of second-order semantics described, firstly, by Simms and later extended by Cocchiarella. We formulate a new second order logical system and prove its relative consistency. We call such a system and construct its set-theoretic semantics. Finally, we prove completeness theorems for proper normal extensions of the two systems with respect to certain notions of (...) validity provided by the semantics. (shrink)

Because of its capacity to characterize mathematical concepts and structures?a capacity which first-order languages clearly lack?second-order languages recommend themselves as a convenient framework for much of mathematics, including set theory. This paper is about the credentials of second-order logic:the reasons for it to be considered logic, its relations with set theory, and especially the efficacy with which it performs its role of the underlying logic of set theory.

Neo-Fregean approaches to set theory, following Frege, have it that sets are the extensions of concepts, where concepts are the values of second-order variables. The idea is that, given a second-order entity $X$, there may be an object $\varepsilon X$, which is the extension of X. Other writers have also claimed a similar relationship between second-order logic and set theory, where sets arise from pluralities. This paper considers two interpretations of second-order (...) logic—as being either extensional or intensional—and whether either is more appropriate for this approach to the foundations of set theory. Although there seems to be a case for the extensional interpretation resulting from modal considerations, I show how there is no obstacle to starting with an intensional second-order logic. I do so by showing how the $\varepsilon$ operator can have the effect of “extensionalizing” intensional second-order entities. (shrink)

A back and forth condition on interpretations for those second-order languages without functional variables whose non-logical vocabulary is finite and excludes functional constants is presented. It is shown that this condition is necessary and sufficient for the interpretations to be equivalent in the language. When applied to second-order languages with an infinite non-logical vocabulary, excluding functional constants, the back and forth condition is sufficient but not necessary. It is shown that there is a class of infinitary (...) second-order languages whose non-logical vocabulary is infinite for which the back and forth condition is both necessary and sufficient. It is also shown that some applications of the back and forth construction for second-order languages can be extended to the infinitary second-order languages. (shrink)

The aim of this paper is to point out the equivalence between three notions respectively issued from recursion theory, computational complexity and finite model theory. One the one hand, the rudimentary languages are known to be characterized by the linear hierarchy. On the other hand, this complexity class can be proved to correspond to monadic second‐order logic with addition. Our viewpoint sheds some new light on the close connection between these domains: We bring together the two extremal (...) notions by providing a direct logical characterization of rudimentary languages and a representation result of second‐order logic into these languages. We use natural arithmetical tools, and our proofs contain no ingredient from computational complexity. (shrink)

In this report I motivate and develop a type-free logic with predicate quantifiers within the general ontological framework of properties, relations, and propositions. In Part I, I present the major ideas of the system informally and discuss its philosophical significance, especially with regard to Russell's paradox. In Part II, I prove the soundness, consistency, and completeness of the logic.

In this paper, we generalize the set-theoretic translation method for poly-modal logic introduced in [11] to extended modal logics. Instead of devising an ad-hoc translation for each logic, we develop a general framework within which a number of extended modal logics can be dealt with. We first extend the basic set-theoretic translation method to weak monadic second-order logic through a suitable change in the underlying set theory that connects up in interesting ways with constructibility; then, (...) we show how to tailor such a translation to work with specific cases of extended modal logics. (shrink)

We investigate the expressive power of second-order logic over finite structures, when two limitations are imposed. Let SAA ) be the set of second-order formulas such that the arity of the relation variables is bounded by k and the number of alternations of second-order quantification is bounded by n . We show that this imposes a proper hierarchy on second-order logic, i.e. for every k , n there are problems not (...) definable in AA but definable in AA for some c 1 , d 1 . The method to show this is to introduce the set AUTOSAT of formulas in F which satisfy themselves. We study the complexity of this set for various fragments of second-order loeic. For first-order logic FOL with unbounded alternation of quantifiers AUTOSAT is PSpace complete. For first-order logic FOL n with alternation of quantifiers bounded by n , AUTOSAT is definable in AA . AUTOSAT) is definable in AA for some c 1 , d 1. (shrink)

This paper investigates the claim that the second-order consequence relation is intractable because of the incompleteness result for SOL. The opponents’ claim is that SOL cannot be proper logic since it does not have a complete deductive system. I argue that the lack of a completeness theorem, despite being an interesting result, cannot be held against the status of SOL as a proper logic.

The central contention of this book is that second-order logic has a central role to play in laying the foundations of mathematics. In order to develop the argument fully, the author presents a detailed description of higher-order logic, including a comprehensive discussion of its semantics. He goes on to demonstrate the prevalence of second-order concepts in mathematics and the extent to which mathematical ideas can be formulated in higher-order logic. He (...) also shows how first-order languages are often insufficient to codify many concepts in contemporary mathematics, and thus that both first- and higher-order logics are needed to fully reflect current work. Throughout, the emphasis is on discussing the associated philosophical and historical issues and the implications they have for foundational studies. For the most part, the author assumes little more than a familiarity with logic comparable to that provided in a beginning graduate course which includes the incompleteness of arithmetic and the Lowenheim-Skolem theorems. All those concerned with the foundations of mathematics will find this a thought-provoking discussion of some of the central issues in the field today. (shrink)

Some internal and philosophical remarks are made regarding a system of a second order logic of existence axiomatized by the author. Attributes are distinguished in the system according as their possession entails existence or not, The former being called e-Attributes. Some discussion of the special principles assumed for e-Attributes is given as well as of the two notions of identity resulting from such a distinction among attributes. Non-Existing objects are of course indiscernible in terms of e-Attributes. In (...) addition, However, Existing objects indiscernible in terms of e-Attributes are indiscernible in terms of all attributes. (shrink)

We analyse the concept of a second-order characterisable structure and divide this concept into two parts—consistency and categoricity—with different strength and nature. We argue that categorical characterisation of mathematical structures in second-order logic is meaningful and possible without assuming that the semantics of second-order logic is defined in set theory. This extends also to the so-called Henkin structures.

In my response to Guillermo Rosado-Haddock I discuss the two main issues raised in his paper. The first is that by allowing Henkin’s general models as a legitimate model-theoretic interpretation of second-order logic, I undermine my defense of second-order logic against Quine’s views concerning the primacy of first-order logic. The second is that my treatment of logical truth and logical properties does not take into account various systems of logic and (...) properties of systems of logic such as the Löwenheim-Skolem property.Em minha réplica à Guillermo Rosado-Haddock discuto as duas questões centrais levantadas em seu artigo. A primeira é que ao permitir modelos gerais de Henkin como uma interpretação legítima da lógica de segunda ordem, desvirtuo minha defesa da lógica de segunda ordem contra a visão de Quine respeito à primazia da lógica de primeira ordem. A segunda é que meu tratamento da verdade lógica e das propriedades lógicas não leva em consideração diversos sistemas de lógica e propriedades de sistemas de lógica tais como a propriedade de Löwenheim-Skolem. (shrink)

We introduce a restricted second-order logic $\textrm{SO}^{\textit{plog}}$ for finite structures where second-order quantification ranges over relations of size at most poly-logarithmic in the size of the structure. We demonstrate the relevance of this logic and complexity class by several problems in database theory. We then prove a Fagin’s style theorem showing that the Boolean queries which can be expressed in the existential fragment of $\textrm{SO}^{\textit{plog}}$ correspond exactly to the class of decision problems that can (...) be computed by a non-deterministic Turing machine with random access to the input in time $O^k)$ for some $k \ge 0$, i.e. to the class of problems computable in non-deterministic poly-logarithmic time. It should be noted that unlike Fagin’s theorem which proves that the existential fragment of second-order logic captures NP over arbitrary finite structures, our result only holds over ordered finite structures, since $\textrm{SO}^{\textit{plog}}$ is too weak as to define a total order of the domain. Nevertheless, $\textrm{SO}^{\textit{plog}}$ provides natural levels of expressibility within poly-logarithmic space in a way which is closely related to how second-order logic provides natural levels of expressibility within polynomial space. Indeed, we show an exact correspondence between the quantifier prefix classes of $\textrm{SO}^{\textit{plog}}$ and the levels of the non-deterministic poly-logarithmic time hierarchy, analogous to the correspondence between the quantifier prefix classes of second-order logic and the polynomial-time hierarchy. Our work closely relates to the constant depth quasipolynomial size AND/OR circuits and corresponding restricted second-order logic defined by David A. Mix Barrington in 1992. We explore this relationship in detail. (shrink)