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)

Logics that have many truth values—more than just True and False—have been argued to be useful in the analysis of very many philosophical and linguistic puzzles. In this paper, which is a followup to, we will start with a particularly well-motivated four-valued logic that has been studied mainly in its propositional and first-order versions. And we will then investigate its second-order version. This four-valued logic has two natural three-valued extensions: what is called (...) a “gap logic”, and what is called a “glut logic”. We mention various results about the second-order version of these logics as well. And we then follow our earlier papers, where we had added a specific conditional connective to the three valued logics, and now add that connective to the four-valued logic under consideration. We then show that, although this addition is “conservative” in the sense that no new theorems are generated in the four-valued logic unless they employ this new conditional in their statement, nevertheless the resulting second-order versions of these logics with and without the conditional are quite different in important ways. We close with a moral for logical investigations in this realm. (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)

As they are conventionally formulated, Boolean games assume that players make their choices in ignorance of the choices being made by other players – they are games of simultaneous moves. For many settings, this is clearly unrealistic. In this paper, we show how Boolean games can be enriched by dependency graphs which explicitly represent the informational dependencies between variables in a game. More precisely, dependency graphs play two roles. First, when we say that variable x depends on variable (...) y, then we mean that when a strategy assigns a value to variable x, it can be informed by the value that has been assigned to y. Second, and as a consequence of the first property, they capture a richer and more plausible model of concurrency than the simultaneous-action model implicit in conventional Boolean games. Dependency graphs implicitly define a partial ordering of the run-time events in a game: if x is dependent on y, then the assignment of a value to y must precede the assignment of a value to x; if x and y are independent, however, then we can say nothing about the ordering of assignments to these variables—the assignments may occur concurrently. We refer to Boolean games with dependency graphs as partial-order Boolean games. After motivating and presenting the partial-order Boolean games model, we explore its properties. We show that while some problems associated with our new games have the same complexity as in conventional Boolean games, for others the complexity blows up dramatically. We also show that the concurrency in partial-order Boolean games can be modelled using a closure-operator semantics, and conclude by considering the relationship of our model to Independence-Friendly logic. (shrink)

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)

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)

This paper casts doubt on a recent criticism of Frege's theory of concepts and extensions by showing that it misses one of Frege's most important contributions: the derivation of the infinity of the natural numbers. We show how this result may be incorporated into the conceptual structure of Zermelo- Fraenkel Set Theory. The paper clarifies the bearing of the development of the notion of a real-valued function on Frege's theory of concepts; it concludes with a brief discussion of the (...) claim that the standard interpretation of second-order logic is necessary for the derivation of the Peano Postulates and the proof of their categoricity. (shrink)

We start with a simple proof of Leivant's normal form theorem for ∑11 formulas over finite successor structures. Then we use that normal form to prove the following:1. over all finite structures, every ∑21 formula is equivalent to a ∑21 formula whose first-order part is a Boolean combination of existential formulas, and2. over finite successor structures, the Kolaitis-Thakur hierarchy of minimization problems collapses completely and the Kolaitis-Thakur hierarchy of maximization problems collapses partially.The normal form theorem for ∑21 fails (...) if ∑21 is replaced with ∑11 or if infinite structures are allowed. (shrink)

Monadic second order logic and linear temporal logic are two logical formalisms that can be used to describe classes of infinite words, i.e., first-order models based on the natural numbers with order, successor, and finitely many unary predicate symbols.Monadic second order logic over infinite words can alternatively be described as a first-order logic interpreted in${\cal P}\left$, the power set Boolean algebra of the natural numbers, equipped with modal operators (...) for ‘initial’, ‘next’, and ‘future’ states. We prove that the first-order theory of this structure is the model companion of a class of algebras corresponding to a version of linear temporal logic without until.The proof makes crucial use of two classical, nontrivial results from the literature, namely the completeness of LTL with respect to the natural numbers, and the correspondence between S1S-formulas and Büchi automata. (shrink)

Regarding strictly monadic second‐order logic (SMSOL), which is the fragment of monadic second‐order logic in which all predicate constants are unary and there are no function symbols, we show that a standard deductive system with full comprehension is sound and complete with respect to standard semantics. This result is achieved by showing that in the case of SMSOL, the truth value of any formula in a faithful identity‐standard Henkin structure is preserved when the structure (...) is “standardized”; that is, the predicate domain is expanded into the set of all unary relations. In addition, we obtain a simpler proof of the decidability of SMSOL. (shrink)

Boolean-valued models generalize classical two-valued models by allowing arbitrary complete Boolean algebras as value ranges. The goal of my dissertation is to study Boolean-valued models and explore their philosophical and mathematical applications.In Chapter 1, I build a robust theory of first-order Boolean-valued models that parallels the existing theory of two-valued models. I develop essential model-theoretic notions like “Boolean-valuation,” “diagram,” and “elementary diagram,” and prove a series of theorems on (...) class='Hi'>Boolean-valued models, including the (strengthened) Soundness and Completeness Theorem, the Löwenheim–Skolem Theorems, the Elementary Chain Theorem, and many more.Chapter 2 gives an example of a philosophical application of Boolean-valued models. I apply Boolean-valued models to the language of mereology to model indeterminacy in the parthood relation. I argue that Boolean-valued semantics is the best degree-theoretic semantics for the language of mereology. In particular, it trumps the well-known alternative—fuzzy-valued semantics. I also show that, contrary to what many have argued, indeterminacy in parthood entails neither indeterminacy in existence nor indeterminacy in identity, though being compatible with both.Chapter 3 (joint work with Bokai Yao) gives an example of a mathematical application of Boolean-valued models. Scott and Solovay famously used Boolean-valued models on set theory to obtain relative consistency results. In Chapter 3, I investigate two ways of extending the Scott–Solovay construction to set theory with urelements. I argue that the standard way of extending the construction faces a serious problem, and offer a new way that is free from the problem.Abstract prepared by Xinhe Wu.E-mail: [email protected]. (shrink)

This paper studies the expressive power that an extra first order quantifier adds to a fragment of monadic second order logic, extending the toolkit of Janin and Marcinkowski [JM01].We introduce an operation existsn on properties S that says "there are n components having S". We use this operation to show that under natural strictness conditions, adding a first order quantifier word u to the beginning of a prefix class V increases the expressive power monotonically in (...) u. As a corollary, if the first order quantifiers are not already absorbed in V, then both the quantifier alternation hierarchy and the existential quantifier hierarchy in the positive first order closure of V are strict.We generalize and simplify methods from Marcinkowski [Mar99] to uncover limitations of the expressive power of an additional first order quantifier, and show that for a wide class of properties S, S cannot belong to the positive first order closure of a monadic prefix class W unless it already belongs to W.We introduce another operation alt on properties which has the same relationship with the Circuit Value Problem as reach has with the Directed Reachability Problem. We use alt to show that Πn⊈ FO, Σn⊈ FO, and Δn+1⊈ FOB, solving some open problems raised in [Mat98]. (shrink)

Boolean-valued models for first-order languages generalize two-valued models, in that the value range is allowed to be any complete Boolean algebra instead of just the Boolean algebra 2. Boolean-valued models are interesting in multiple aspects: philosophical, logical, and mathematical. The primary goal of this paper is to extend a number of critical model-theoretic notions and to generalize a number of important model-theoretic results based on these notions to Boolean-valued models. For (...) instance, we will investigate (first-order) Boolean valuations, which are natural generalizations of (first-order) theories, and prove that Boolean-valued models are sound and complete with respect to Boolean valuations. With the help of Boolean valuations, we will also discuss the Löwenheim-Skolem theorems on Boolean-valued models. (shrink)

The most common first- and second-order modal logics either have as theorems every instance of the Barcan and Converse Barcan formulae and of their second-order analogues, or else fail to capture the actual truth of every theorem of classical first- and second-order logic. In this paper we characterise and motivate sound and complete first- and second-order modal logics that successfully capture the actual truth of every theorem of classical first- and (...) class='Hi'>second-order logic and yet do not possess controversial instances of the Barcan and Converse Barcan formulae as theorems, nor of their second-order analogues. What makes possible these results is an understanding of the individual constants and predicates of the target languages as strongly Millian expressions, where a strongly Millian expression is one that has an actually existing entity as its semantic value. For this reason these logics are called ‘strongly Millian’. It is shown that the strength of the strongly Millian second-order modal logics here characterised afford the means to resist an argument by Timothy Williamson for the truth of the claim that necessarily, every property necessarily exists. (shrink)

We prove the following surprising property of Heyting's intuitionistic propositional calculus, IpC. Consider the collection of formulas, φ, built up from propositional variables (p,q,r,...) and falsity $(\perp)$ using conjunction $(\wedge)$ , disjunction (∨) and implication (→). Write $\vdash\phi$ to indicate that such a formula is intuitionistically valid. We show that for each variable p and formula φ there exists a formula Apφ (effectively computable from φ), containing only variables not equal to p which occur in φ, and such that for (...) all formulas ψ not involving $p, \vdash \psi \rightarrow A_p\phi$ if and only if $\vdash \psi \rightarrow \phi$ . Consequently quantification over propositional variables can be modelled in IpC, and there is an interpretation of the second order propositional calculus, IpC2, in IpC which restricts to the identity on first order propositions. An immediate corollary is the strengthening of the usual interpolation theorem for IpC to the statement that there are least and greatest interpolant formulas for any given pair of formulas. The result also has a number of interesting consequences for the algebraic counterpart of IpC, the theory of Heyting algebras. In particular we show that a model of IpC2 can be constructed whose algebra of truth-values is equal to any given Heyting algebra. (shrink)

The paper consists of two parts. The first part begins with the problem of whether the original three-valued calculus, invented by J. Łukasiewicz, really conforms to his philosophical and semantic intuitions. I claim that one of the basic semantic assumptions underlying Łukasiewicz's three-valued logic should be that if under any possible circumstances a sentence of the form "X will be the case at time t" is true (resp. false) at time t, then this sentence must be already (...) true (resp. false) at present. However, it is easy to see that this principle is violated in Lukasiewicz's original calculus (as the cases of the law of excluded middle and the law of contradiction show). Nevertheless it is possible to construct (either with the help of the notion of "supervaluation", or purely algebraically) a different three-valued, semi-classical sentential calculus, which would properly incorporate Łukasiewicz's initial intuitions. Algebraically, this calculus has the ordinary Boolean structure, and therefore it retains all classically valid formulas. Yet because possible valuations are no longer represented by ultrafilters, but by filters (not necessarily maximal), the new calculus displays certain non-classical metalogical features (like, for example, nonextensionality and the lack of the metalogical rule enabling one to derive "p is true or q is true" from" 'p ∨ q' is true"). The second part analyses whether the proposed calculus could be useful in formalizing inferences in situations, when for some reason (epistemological or ontological) our knowledge of certain facts is subject to limitation. Special attention should be paid to the possibility of employing this calculus to the case of quantum mechanics. I am going to compare it with standard non-Boolean quantum logic (in the Jauch-Piron approach), and to show that certain shortcomings of the latter can be avoided in the former. For example, I will argue that in order to properly account for quantum features of microphysics, we do not need to drop the law of distributivity. Also the idea of "reading off" the logical structure of propositions from the structure of Hilbert space leads to some conceptual troubles, which I am going to point out. The thesis of the paper is that all we need to speak about quantum reality can be acquired by dropping the principle of bivalence and extensionality, while accepting all classically valid formulas. (shrink)

This essay examines the philosophical significance of $\Omega$-logic in Zermelo-Fraenkel set theory with choice (ZFC). The categorical duality between coalgebra and algebra permits Boolean-valued algebraic models of ZFC to be interpreted as coalgebras. The hyperintensional profile of $\Omega$-logical validity can then be countenanced within a coalgebraic logic. I argue that the philosophical significance of the foregoing is two-fold. First, because the epistemic and modal and hyperintensional profiles of $\Omega$-logical validity correspond to those of second-order (...) logical consequence, $\Omega$-logical validity is genuinely logical. Second, the foregoing provides a hyperintensional account of the interpretation of mathematical and metamathematical vocabulary. (shrink)

This paper examines the philosophical significance of the consequence relation defined in the $\Omega$-logic for set-theoretic languages. I argue that, as with second-order logic, the hyperintensional profile of validity in $\Omega$-Logic enables the property to be epistemically tractable. Because of the duality between coalgebras and algebras, Boolean-valued models of set theory can be interpreted as coalgebras. In Section \textbf{2}, I demonstrate how the hyperintensional profile of $\Omega$-logical validity can be countenanced within a coalgebraic (...) logic. Finally, in Section \textbf{3}, the philosophical significance of the characterization of the hyperintensional profile of $\Omega$-logical validity for the philosophy of mathematics is examined. I argue (i) that $\Omega$-logical validity is genuinely logical, and (ii) that it provides a hyperintensional account of formal grasp of the concept of `set'. Section \textbf{4} provides concluding remarks. (shrink)

In this paper, we are concerned with the development of a general set theory using the single axiom version of Leśniewski’s mereology. The specification of mereology, and further of Tarski’s geometry of solids will rely on the Calculus of Inductive Constructions (CIC). In the first part, we provide a specification of Leśniewski’s mereology as a model for an atomless Boolean algebra using Clay’s ideas. In the second part, we interpret Leśniewski’s mereology in monadic second-order logic (...) using names and develop a full version of mereology referred to as CIC-based Monadic Mereology (λ-MM) allowing an expressive theory while involving only two axioms. In the third part, we propose a modeling of Tarski’s solid geometry relying on λ-MM. It is intended to serve as a basis for spatial reasoning. All parts have been proved using a translation in type theory. (shrink)

In this paper we prove that $\forall \textrm{FO}$, the universal fragment of first-order logic, is superfluous in $\varSigma _2^p$ and $\varPi _2^p$. As an example, we show that this yields a syntactic proof of the $\varSigma _2^p$-completeness of value-cost satisfiability. The superfluity method is interesting since it gives a way to prove completeness of problems involving numerical data such as lengths, weights and costs and it also adds to the programme started by Immerman and Medina about the syntactic (...) approach in the study of completeness. (shrink)

The 3-valued paraconsistent logic Ciore was developed by Carnielli, Marcos and de Amo under the name LFI2, in the study of inconsistent databases from the point of view of logics of formal inconsistency (LFIs). They also considered a first-order version of Ciore called LFI2*. The logic Ciore enjoys extreme features concerning propagation and retropropagation of the consistency operator: a formula is consistent if and only if some of its subformulas is consistent. In addition, Ciore is algebraizable (...) in the sense of Blok and Pigozzi. On the other hand, the logic LFI2* satisfies a somewhat counter-intuitive property: the universal and the existential quantifier are inter-definable by means of the paraconsistent negation, as it happens in classical first-order logic with respect to the classical negation. This feature seems to be unnatural, given that both quantifiers have the classical meaning in LFI2*, and that this logic does not satisfy the De Morgan laws with respect to its paraconsistent negation. The first goal of the present article is to introduce a first-order version of Ciore (which we call QCiore) preserving the spirit of Ciore, that is, without introducing unexpected relationships between the quantifiers. The second goal of the article is to adapt to QCiore the partial structures semantics for the first-order paraconsistent logic LPT1 introduced by Coniglio and Silvestrini, which generalizes the semantic notion of quasi-truth considered by Mikeberg, da Costa and Chuaqui. Finally, some important results of classical Model Theory are obtained for this logic, such as Robinson’s joint consistency theorem, amalgamation and interpolation. Although we focus on QCiore, this framework can be adapted to other 3-valued first-order LFIs. (shrink)

In this paper, we introduce a variant of second-order propositional modal logic interpreted on general (or Henkin) frames, \(SOPML^{\mathcal {H}}\), and present a decidable fragment of this logic, \(SOPML^{\mathcal {H}}_{dec}\), that preserves important expressive capabilities of \(SOPML^{\mathcal {H}}\). \(SOPML^{\mathcal {H}}_{dec}\) is defined as a _modal loosely guarded fragment_ of \(SOPML^{\mathcal {H}}\). We demonstrate the expressive power of \(SOPML^{\mathcal {H}}_{dec}\) using examples in which modal operators obtain (a) the epistemic interpretation, (b) the dynamic interpretation. \(SOPML^{\mathcal {H}}_{dec}\) partially (...) satisfies the principle of non-Fregean logic: two different _atomic_ propositions with the same truth value can have different contents. In \(SOPML^{\mathcal {H}}_{dec}\), we also define _relating connectives_ and show that the _weak Boethius’ Thesis_ built using these connectives is a valid formula of \(SOPML^{\mathcal {H}}_{dec}\). (shrink)

Paraconsistent Weak Kleene logic is the 3-valued logic with two designated values defined through the weak Kleene tables. This paper is a first attempt to investigate PWK within the perspective and methods of abstract algebraic logic. We give a Hilbert-style system for PWK and prove a normal form theorem. We examine some algebraic structures for PWK, called involutive bisemilattices, showing that they are distributive as bisemilattices and that they form a variety, \, generated by the 3-element (...) algebra WK; we also prove that every involutive bisemilattice is representable as the Płonka sum over a direct system of Boolean algebras. We then study PWK from the viewpoint of AAL. We show that \ is not the equivalent algebraic semantics of any algebraisable logic and that PWK is neither protoalgebraic nor selfextensional, not assertional, but it is truth-equational. We fully characterise the deductive filters of PWK on members of \ and the reduced matrix models of PWK. Finally, we investigate PWK with the methods of second-order AAL—we describe the class \ of PWK-algebras, algebra reducts of basic full generalised matrix models of PWK, showing that they coincide with the quasivariety generated by WK—which differs from \—and explicitly providing a quasiequational basis for it. (shrink)

The Logic & Structure project is about the language of mathematical logic and how it can be of use in the visual arts. It involves a conversation between a mathematical logician and a group of artists. The project is ongoing, and this is a report on its first two phases. This text has two parts. The first, “Logic”, is a short introduction to certain aspects of logic, as it was presented to the participants. The second (...) part, “Structures”, describes some of the outcomes.The inspiration for the project comes from modern model theory whose advances revealed the extent to which formal methods may be helpful in describing and analysing mathematical structures. While the structures that are studied are often immensely complex, the formal language in which their properties can be expressed is simple. Its syntax is precisely defined and well understood, and this understanding often successfully guides us in our explorations of the rich world of mathematical objects. Our goal is to see the extent to which a similar approach could be of value when talking about works of art as structures. To this end, one could try to describe existing art objects in terms of suitably chosen formal languages, but we follow a reverse route. The language is described first, and the participating artists are asked to come up with artwork in which formal elements and their relations are chosen in advance, making it easier to identify those features of the created pieces that can be formally expressed. In other words, we are not thinking of applying formal methods to create art; rather we want to begin with samples that can serve as material for discussion. (shrink)

Context: Second-order cybernetics and its implications have been understood within the cybernetics community for some time. These implications are important for understanding the structure of scientific endeavor, and for researchers in other fields to see the reflexive nature of scientific research. This article is about the role of context in the creation and exploration of our experience. Problem: The purpose of this article is to point out the fundamental nature of the circularity in cybernetics and in scientific work (...) in general. I give a point of view on the nature of objective knowledge by placing it in the context of reflexivity and eigenform. Method: The approach to the topic is based on logical analysis of the nature of circularity. Mathematics and cybernetics are both fundamentally concerned with the structure of distinctions, but there can be no definition of a distinction without circularity, since such a definition would itself be a distinction. The article proceeds by explicating the structure of reflexive domains D where the transformations of the domain are in one-to-one correspondence with the domain itself. Results: I show that every element of a reflexive domain has a fixed point. This means that eigenforms arise naturally in reflexive domains. Furthermore, a reflexive domain is itself an eigenform (at a higher level. This supports the context of a second-order science that would study domains of science as part of a larger cybernetic landscape. Implications: The value of the article is in its concise reformulation of the scientific endeavor as a search for eigenforms in reflexive domains. This new view of science is promising in that it includes the former worlds of apparent objectivity and it embraces those newer worlds of science where the theories and theorists become active participants in the ongoing process of creating knowledge. Constructivist content: I argue that the perspective of reflexive domains constitutes a new way to think about the practice of science, with observers deeply imbedded, and objectivity understood as the mutual search for eigenforms. (shrink)

We introduce a notion of syntactical truth predicate (s.t.p.) for the second order arithmetic PA 2 . An s.t.p. is a set T of closed formulas such that: (i) T(t = u) if and only if the closed first order terms t and u are convertible, i.e., have the same value in the standard interpretation (ii) T(A → B) if and only if (T(A) $\Longrightarrow$ T(B)) (iii) T(∀ x A) if and only if (T(A[x ← t]) for (...) any closed first order term t) (iv) T(∀ X A) if and only if (T(A[X ←▵]) for any closed set definition $\triangle = \{x \mid D(x)\}$ ). S.t.p.'s can be seen as a counterpart to Tarski's notion of (model-theoretical) validity and have main model properties. In particular, their existence is equivalent to the existence of an ω-model of PA 2 , this fact being provable in PA 2 with arithmetical comprehension only. (shrink)

We show how to build various models of first-order theories, which also have properties like: tree with only definable branches, atomic Boolean algebras or ordered fields with only definable automorphisms. For this we use a set-theoretic assertion, which may be interesting by itself on the existence of quite generic subsets of suitable partial orders of power λ + , which follows from ♦ λ and even weaker hypotheses . For a related assertion, which is equivalent to the morass (...) see Shelah and Stanley [16]. The various specific constructions serve also as examples of how to use this set-theoretic lemma. We apply the method to construct rigid ordered fields, rigid atomic Boolean algebras, trees with only definable branches; all in successors of regular cardinals under appropriate set- theoretic assumptions. So we are able to answer the following algebraic question. Saltzman's Question . Is there a rigid real closed field, which is not a subfield of the reals? (shrink)

The major point of contention among the philosophers and mathematicians who have written about the independence results for the continuum hypothesis (CH) and related questions in set theory has been the question of whether these results give reason to doubt that the independent statements have definite truth values. This paper concerns the views of G. Kreisel, who gives arguments based on second order logic that the CH does have a truth value. The view defended here is that (...) although Kreisel's conclusion is correct, his arguments are unsatisfactory. Later sections of the paper advance a different argument that the independence results do not show lack of truth values. (shrink)

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)

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)

§1. Introduction.The motivation of this work comes from two different directions: infinite abelian groups, and ordered algebraic structures. A challenging problem in both cases is that of classification. In the first case, it is known for example (cf. [KA]) that the classification of abelian torsion groups amounts to that of reducedp-groups by numerical invariants called theUlm invariants(given by Ulm in [U]). Ulm's theorem was later generalized by P. Hill to the class of totally projective groups. As to the second (...) case, let us consider for instance the class of divisible ordered abelian groups. These may be viewed as ordered ℚ-vector spaces. Their theory being unstable, we cannot hope to classify them by numerical invariants. On the other hand, being o-minimal, the theory enjoys several good model theoretic properties (cf. [P-S]), so the search for some reasonable invariants is well motivated. The common denominator of the two cases, as well as of many others, is valuation theory. Indeed given an ordered vector space, one can consider it as a valued vector space, endowed with the natural valuation. Also, the socleG[p] of a reduced abelianp-groupG, endowed with the height functionhG, is a valued vector space over(the prime field of characteristicp) with values in the ordinals (cf. [F]). (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)

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)

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)

We obtain a nonasymptotic lower time bound for deciding sentences of bounded second-order arithmetic with respect to a form of the random access machine with stored programs. More precisely, let P be an arbitrary program for the model under consideration which recognized true formulas with a given range of parameters. Let p be the length of P and let N be an arbitrary natural number. We show how to construct a formula G with one free variable with length (...) not more than 400 symbols and a value f of x such that the time required by P to decide the truth of G is at least N+1 steps. Furthermore, the G constructed does not depend on P and the length of f is less than p+400. (shrink)

This paper offers the Boolean many-valued solution to the Sorites Paradox. According to the precisification-based Boolean many-valued theory, from which this solution arises, sentences have not only two truth values, truth (or 1) and falsity (or 0), but many Boolean values between 0 and 1. The Boolean value of a sentence is identified with the set of precisifications in which the sentence is true. Unlike degrees fuzzy logic assigns to sentences, Boolean many (...) values are not linearly but only partially ordered; so there are values that are incomparable. Despite this fact, the sentences in a sorites series can be taken as having values in a linear order, and losing (or gaining) value as we move from sentence to sentence in the series. So there is no sharp borderline between 0 and 1. Assigning Boolean many values instead of the two truth values to sentences for their vagueness values is analogous to assigning propositions instead of the truth values to sentences for their semantic values, as propositions are, from our viewpoint, also Boolean many values. (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)

In noise we hear the possibility of a signal, indeed different signals, and in the multiplicity of signals we hear noise. With variation and selection comes dynamic evolution, a contingent state, one that could be otherwise. The term ‘polemogenous’ (from the French, polémogène) means that which generates polemics. And polemics are creative. If everyone, every system, were to reason in the same way, there would be silence. Every remark would be redundant, having no informational value. Thus noise is not bad. (...) The essence of finance economics, like all that is social in nature, is a forming of meaning. Whatever cannot be formed meaningfully is not available to the system. This unavailability, as ‘noise’, is the dynamic difference (noise/information) that scintillates the system. Information, like morality, is polemogenous – it stirs contention. Without noise and the possibility of its conversion to information there would be no opportunities to exploit. This paper applies a systems theoretical understanding of observation to conceive of finance economics as the economy’s means of observing its noise and capitalizing on that polemic. Niklas Luhmann’s method is utilized to explicate some ideas on noise by financial economist Fischer Black, who suggests the incomprehensible is computable. This is finance. The fact that logical grounds, absolute deductions, and clear calculations are claimed to be rare in finance is no barrier to understanding it. Rather, this polyphonic and polemogenous information-selection is the ‘ground’ of finance, not as totalizing logic, but as different difference-production for the sake of deriving economic opportunity. (shrink)