The purpose of this paper is twofold: (1) to clarify Ludwig Wittgenstein’s thesis that colours possess logical structures, focusing on his ‘puzzle proposition’ that “there can be a bluish green but not a reddish green”, (2) to compare modeltheoretical and gametheoretical approaches to the colour exclusion problem. What is gained, then, is a new gametheoretical framework for the logic of ‘forbidden’ (e.g., reddish green and bluish yellow) colours. My larger aim is to discuss phenomenological principles of the demarcation of the (...) bounds of logic as formal ontology of abstract objects. (shrink)

We consider the expressive power of second - order generalized quantifiers on finite structures, especially with respect to the types of the quantifiers. We show that on finite structures with at most binary relations, there are very powerful second - order generalized quantifiers, even of the simplest possible type. More precisely, if a logic is countable and satisfies some weak closure conditions, then there is a generalized second - order quantifier which is monadic, unary and simple, and a uniformly obtained (...) sublogic of which is equivalent to. We show some other results of the above kind, relating other classes of quantifiers to other classes of structures. For example, if the quantifiers are of the simplest non-monadic type, then the result extends to finite structures of any arity. We further show that there are second - order generalized quantifiers which do not increase expressive power of first- order logic but do increase the power significantly when added to stronger logics. (shrink)

Vectorization of a class of structures is a natural notion in finite model theory. Roughly speaking, vectorizations allow tuples to be treated similarly to elements of structures. The importance of vectorizations is highlighted by the fact that if the complexity class PTIME corresponds to a logic with reasonable syntax, then it corresponds to a logic generated via vectorizations by a single generalized quantifier (Dawar in J Log Comput 5(2):213–226, 1995). It is somewhat surprising, then, that there have been few systematic (...) studies of the expressive power of vectorizations of various quantifiers. In the present paper, we consider the simplest case: the cardinality quantifiers C S. We show that, in general, the expressive power of the vectorized quantifier logic $${{\rm FO}(\{{\mathsf C}_S^{(n)}\, | \, n \in \mathbb{Z}_+\})}$$ is much greater than the expressive power of the non-vectorized logic FO(C S ). (shrink)

Although the invariance criterion of logicality first emerged as a criterion of a purely mathematical interest, it has developed into a criterion of considerable linguistic and philosophical interest. In this paper I compare two different perspectives on this criterion. The first is the perspective of natural language. Here, the invariance criterion is measured by its success in capturing our linguistic intuitions about logicality and explaining our logical behavior in natural-linguistic settings. The second perspective is more theoretical. Here, the invariance criterion (...) is used as a tool for developing a theoretical foundation of logic, focused on a critical examination, explanation, and justification of its veridicality and modal force. (shrink)

We extend the languages of both basic and graded modal logic with the infinity diamond, a modality that expresses the existence of infinitely many successors having a certain property. In both cases we define a natural notion of bisimilarity for the resulting formalisms, that we dub $\mathtt {ML}^{\infty }$ and $\mathtt {GML}^{\infty }$, respectively. We then characterise these logics as the bisimulation-invariant fragments of the naturally corresponding predicate logic, viz., the extension of first-order logic with the infinity quantifier. Furthermore, for (...) both $\mathtt {ML}^{\infty }$ and $\mathtt {GML}^{\infty }$ we provide a sound and complete axiomatisation for the set of formulas that are valid in every Kripke frame, we prove a small model property with respect to a widened class of weighted models, and we establish decidability of the satisfiability problem. (shrink)

Properties and relations in general have a certain degree of invariance, and some types of properties/relations have a stronger degree of invariance than others. In this paper I will show how the degrees of invariance of different types of properties are associated with, and explain, the modal force of the laws governing them. This explains differences in the modal force of laws/principles of different disciplines, starting with logic and mathematics and proceeding to physics and biology.

One well known problem regarding quantifiers, in particular the 1storder quantifiers, is connected with their syntactic categories and denotations. The unsatisfactory efforts to establish the syntactic and ontological categories of quantifiers in formalized first-order languages can be solved by means of the so called principle of categorial compatibility formulated by Roman Suszko, referring to some innovative ideas of Gottlob Frege and visible in syntactic and semantic compatibility of language expressions. In the paper the principle is introduced for categorial languages generated (...) by the Ajdukiewicz’s classical categorial grammar. The 1st-order quantifiers are typically ambiguous. Every 1st-order quantifier of the type k > 0 is treated as a two-argument functorfunction defined on the variable standing at this quantifier and its scope (the sentential function with exactly k free variables, including the variable bound by this quantifier); a binary function defined on denotations of its two arguments is its denotation. Denotations of sentential functions, and hence also quantifiers, are defined separately in Fregean and in situational semantics. They belong to the ontological categories that correspond to the syntactic categories of these sentential functions and the considered quantifiers. The main result of the paper is a solution of the problem of categories of the 1st-order quantifiers based on the principle of categorial compatibility. (shrink)

On Zermelo's view, any mathematical theory presupposes a non-empty domain, the elements of which enjoy equal status; furthermore, mathematical axioms must be chosen from among those propositions that reflect the equal status of domain elements. As for which propositions manage to do this, Zermelo's answer is, those that are ?symmetric?, meaning ?invariant under domain permutations?. We argue that symmetry constitutes Zermelo's conceptual analysis of ?general proposition?. Further, although others are commonly associated with the extension of Klein's Erlanger Programme to logic, (...) Zermelo's name has a place in that story. (shrink)

What is the source of logical and mathematical truth? This book revitalizes conventionalism as an answer to this question. Conventionalism takes logical and mathematical truth to have their source in linguistic conventions. This was an extremely popular view in the early 20th century, but it was never worked out in detail and is now almost universally rejected in mainstream philosophical circles. Shadows of Syntax is the first book-length treatment and defense of a combined conventionalist theory of logic and mathematics. It (...) argues that our conventions, in the form of syntactic rules of language use, are perfectly suited to explain the truth, necessity, and a priority of logical and mathematical claims, as well as our logical and mathematical knowledge. (shrink)

This paper is a continuation of the investigation from [13]. The main theorem states that the general and the existential quantifiers are (, -reducible in some Grothendieck toposes. Using this result and Theorems 4.1, 4.2 [13] we get the downward Skolem-Löwenheim theorem for semantics in these toposes.

This paper investigates how naive theories of truth fare with respect to a set of extremely plausible principles of restricted quantification. It is first shown that both nonsubstructural theories as well as certain substructural theories cannot validate all those principles. Then, pursuing further an approach to the semantic paradoxes that the author has defended elsewhere, the theory of restricted quantification available in a specific naive theory that rejects the structural property of contraction is explored. It is shown that the theory (...) validates all the principles in question, and it is argued that other prima facie plausible principles that the theory fails to validate are objectionable on independent grounds. (shrink)

In his 1936 paper,On the Concept of Logical Consequence, Tarski introduced the celebrated definition oflogical consequence: “The sentenceσfollows logicallyfrom the sentences of the class Γ if and only if every model of the class Γ is also a model of the sentenceσ.” [55, p. 417] This definition, Tarski said, is based on two very basic intuitions, “essential for the proper concept of consequence” [55, p. 415] and reflecting common linguistic usage: “Consider any class Γ of sentences and a sentence which (...) follows from the sentences of this class. From an intuitive standpoint it can never happen that both the class Γ consists only of true sentences and the sentenceσis false. Moreover, … we are concerned here with the concept of logical, i.e.,formal, consequence.” [55, p. 414] Tarski believed his definition of logical consequence captured the intuitive notion: “It seems to me that everyone who understands the content of the above definition must admit that it agrees quite well with common usage. … In particular, it can be proved, on the basis of this definition, that every consequence of true sentences must be true.” [55, p. 417] The formality of Tarskian consequences can also be proven. Tarski's definition of logical consequence had a key role in the development of the model-theoretic semantics of modern logic and has stayed at its center ever since. (shrink)

The paper elaborates two points: i) There is no principal opposition between predicate logic and adherence to subject-predicate form, ii) Aristotle's treatment of quantifiers fits well into a modern study of generalized quantifiers.

The Craig Interpolation Theorem is intimately connected with the emergence of abstract logic and continues to be the driving force of the field. I will argue in this paper that the interpolation property is an important litmus test in abstract model theory for identifying “natural,” robust extensions of first order logic. My argument is supported by the observation that logics which satisfy the interpolation property usually also satisfy a Lindström type maximality theorem. Admittedly, the range of such logics is small.

In this paper (except in Section 5) all quantifiers are assumedto be so called simple unaryquantifiers, and all models are assumedto be finite. We give a necessary and sufficientcondition for a quantifier to be definablein terms of monotone quantifiers. For amonotone quantifier we give a necessaryand sufficient condition for beingdefinable in terms of a given set of bounded monotonequantifiers. Finally, we give a necessaryand sufficient condition for a monotonequantifier to be definable in terms of agiven monotone quantifier.Our analysis shows that (...) the quantifierat least one half and its relatives behavedifferently than other monotone quantifiers. (shrink)

We show that the predicate “x is the power set of y” is ‐definable, if V = L[E] is an extender model constructed from a coherent sequences of extenders, provided that there is no inner model with a Woodin cardinal. Here is a predicate true of just the infinite cardinals. From this we conclude: the validities of second order logic are reducible to, the set of validities of the Härtig quantifier logic. Further we show that if no L[E] model has (...) a cardinal strong up to one of its ℵ‐fixed points, and, the Löwenheim number of this logic, is less than the least weakly inaccessible δ, then (i) is a limit of measurable cardinals of K, and (ii) the Weak Covering Lemma holds at δ. (shrink)

One logic or many? I say—many. Or rather, I say there is one logic for each way of specifying the class of all possible circumstances, or models, i.e., all ways of interpreting a given language. But because there is no unique way of doing this, I say there is no unique logic except in a relative sense. Indeed, given any two competing logical theories T1 and T2 (in the same language) one could always consider their common core, T, and settle (...) on that theory. So, given any language L, one could settle on the minimal logic T0 corresponding to the common core shared by all competitors. That would be a way of resisting relativism, as long as one is willing to redraw the bounds of logic accordingly. However, such a minimal theory T0 may be empty if the syntax of L contains no special ingredients the interpretation of which is independent of the specification of the relevant L-models. And generally—I argue—this is indeed the case. (shrink)

In this work, we propose a meaningful extension of description logics for non-monotonic reasoning. We introduce \, a logic allowing for the representation of and reasoning about both typical class-membership and typical instances of a relation. We propose a preferential semantics for \ in terms of partially-ordered DL interpretations which intuitively captures the notions of typicality we are interested in. We define a tableau-based algorithm for checking \ knowledge-base consistency that always terminates and we show that it is sound and (...) complete w.r.t. our preferential semantics. The general framework we here propose can serve as the foundation for further exploration of non-monotonic reasoning in description logics and similarly structured logics. (shrink)

We present a number of, somewhat unusual, ways of describing what Craig’s interpolation theorem achieves, and use them to identify some open problems and further directions.

The first section of this paper is concerned with the intrinsic properties of elementary monadic logic (EM), and characterizations in the spirit of Lindström [2] are given. His proofs do not apply to monadic logic since relations are used, and intrinsic properties of EM turn out to differ in certain ways from those of the elementary logic of relations (i.e., the predicate calculus), which we shall call EL. In the second section we investigate connections between higher-order monadic and polyadic logics.EM (...) is the subsystem of EL which results by the restriction to one-place predicate letters. We omit constants (for simplicity) but take EM to contain identity. Let atypebe any finite sequence (possibly empty) of one-place predicate letters. A modelMof typehas a nonempty universe ∣M∣ and assigns to each predicate letterPofa subsetPMof ∣M∣.Let us take a monadic logicLto be any collection of classes of models, calledL-classes, satisfying the following:1. All models in a givenL-class are of the same type (called the type of the class).2. Isomorphic models lie in the sameL-classes.3. IfandareL-classes of the same type, thenandareL-classes. (shrink)

The purpose of this paper is to investigate continuity properties arising in elementary (i.e., first-order) logic in the hope of illuminating the special status of this logic. The continuity properties turn out to be closely related to conditions which characterize elementary logic uniquely, and lead to various further questions.

Symmetric propositions over domain $\mathfrak{D}$ and signature $\Sigma = \langle R^{n_1}_1, \ldots, R^{n_p}_p \rangle$ are characterized following Zermelo, and a correlation of such propositions with logical type- $\langle \vec{n} \rangle$ quantifiers over $\mathfrak{D}$ is described. Boolean algebras of symmetric propositions over $\mathfrak{D}$ and Σ are shown to be isomorphic to algebras of logical type- $\langle \vec{n} \rangle$ quantifiers over $\mathfrak{D}$. This last result may provide empirical support for Tarski’s claim that logical terms over fixed domain are all and only those (...) invariant under domain permutations. (shrink)

We study the computational complexity of polyadic quantifiers in natural language. This type of quantification is widely used in formal semantics to model the meaning of multi-quantifier sentences. First, we show that the standard constructions that turn simple determiners into complex quantifiers, namely Boolean operations, iteration, cumulation, and resumption, are tractable. Then, we provide an insight into branching operation yielding intractable natural language multi-quantifier expressions. Next, we focus on a linguistic case study. We use computational complexity results to investigate semantic (...) distinctions between quantified reciprocal sentences. We show a computational dichotomy<br>between different readings of reciprocity. Finally, we go more into philosophical speculation on meaning, ambiguity and computational complexity. In particular, we investigate a possibility to<br>revise the Strong Meaning Hypothesis with complexity aspects to better account for meaning shifts in the domain of multi-quantifier sentences. The paper not only contributes to the field of the formal<br>semantics but also illustrates how the tools of computational complexity theory might be successfully used in linguistics and philosophy with an eye towards cognitive science. (shrink)

According to the contemporary consensus, when reaching in the lexicon grammar looks for items like nouns, verbs, and prepositions while logic sees items like predicates, connectives, and quantifiers. In fact, there doesn’t seem to be a single lexical category contemporary grammar and logic both make use of. I hope to show that while a perfect match between the lexical categories of grammar and logic is impossible there can be a substantial overlap. I propose semantic definitions for all the major parts (...) of speech . I argue that the differences among these categories can be captured in terms of distinctions recognized in logic. (shrink)

A special kind of substitution on languages called iteration is presented and studied. These languages arise in the application of semantic automata to iterations of generalized quantifiers. We show that each of the star-free, regular, and deterministic context-free languages are closed under iteration and that it is decidable whether a given regular or determinstic context-free language is an iteration of two such languages. This result can be read as saying that the van Benthem/Keenan ‘Frege Boundary’ is decidable for large subclasses (...) of natural language quantifiers. We also determine the state complexity of iteration of regular languages. (shrink)

The semantic automata framework, developed originally in the 1980s, provides computational interpretations of generalized quantifiers. While recent experimental results have associated structural features of these automata with neuroanatomical demands in processing sentences with quantifiers, the theoretical framework has remained largely unexplored. In this paper, after presenting some classic results on semantic automata in a modern style, we present the first application of semantic automata to polyadic quantification, exhibiting automata for iterated quantifiers. We also discuss the role of semantic automata in (...) linguistic theory and offer new empirical predictions for sentence processing with embedded quantifiers. (shrink)

The semantic automata framework, developed originally in the 1980s, provides computational interpretations of generalized quantifiers. While recent experimental results have associated structural features of these automata with neuroanatomical demands in processing sentences with quantifiers, the theoretical framework has remained largely unexplored. In this paper, after presenting some classic results on semantic automata in a modern style, we present the first application of semantic automata to polyadic quantification, exhibiting automata for iterated quantifiers. We also discuss the role of semantic automata in (...) linguistic theory and offer new empirical predictions for sentence processing with embedded quantifiers. (shrink)

Ontological pluralism is the view that there are different fundamental ways of being. Recent defenders of this view—such as Kris McDaniel and Jason Turner—have taken these ways of being to be best captured by semantically primitive quantifier expressions ranging over different domains. They have thus endorsed, what I shall call, quantificational pluralism. I argue that this focus on quantification is a mistake. For, on this view, a quantificational structure—or a quantifier for short—will be whatever part or aspect of reality’s structure (...) that a quantifier expression carves out and reflects. But if quantificational pluralism is true, then a quantifier should be more natural than its corresponding domain; and since it does not appear to be the case that a quantifier is more natural than its corresponding domain, quantificational pluralism does not appear to be true. Thus, I claim, an ontological pluralist should not be a quantificational pluralist. (shrink)

Branching quantifiers were first introduced by L. Henkin in his 1959 paper ‘Some Remarks on Infmitely Long Formulas’. By ‘branching quantifiers’ Henkin meant a new, non-linearly structured quantiiier-prefix whose discovery was triggered by the problem of interpreting infinitistic formulas of a certain form} The branching (or partially-ordered) quantifier-prefix is, however, not essentially infinitistic, and the issues it raises have largely been discussed in the literature in the context of finitistic logic, as they will be here. Our discussion transcends, however, the (...) resources of standard lst-order languages and we will consider the new form in the context of 1st-order logic with 1- and 2-place ‘Mostowskian` generalized quantifiers.2.. (shrink)

In this paper I examine a cluster of concepts relevant to the methodology of truth theories: 'informative definition', 'recursive method', 'semantic structure', 'logical form', 'compositionality', etc. The interrelations between these concepts, I will try to show, are more intricate and multi-dimensional than commonly assumed.

In a recent paper, “The Concept of Logical Consequence,” W. H. Hanson criticizes a formal-structural characterization of logical consequence in Tarski and Sher. Hanson accepts many principles of the formal-structural view. Relating to Sher 1991 and 1996a, he says.

This paper offers a response to William’s Hanson’s criticism of Sher’s formal-structural conception of logical consequence and logical constants.

The construction of a systematic philosophical foundation for logic is a notoriously difficult problem. In Part One I suggest that the problem is in large part methodological, having to do with the common philosophical conception of “providing a foundation”. I offer an alternative to the common methodology which combines a strong foundational requirement with the use of non-traditional, holistic tools to achieve this result. In Part Two I delineate an outline of a foundation for logic, employing the new methodology. The (...) outline is based on an investigation of why logic requires a veridical justification, i.e., a justification which involves the world and not just the mind, and what features or aspect of the world logic is grounded in. Logic, the investigation suggests, is grounded in the formal aspect of reality, and the outline proposes an account of this aspect, the way it both constrains and enables logic, logic's role in our overall system of knowledge, the relation between logic and mathematics, the normativity of logic, the characteristic traits of logic, and error and revision in logic. (shrink)

We define the concept of a logic frame , which extends the concept of an abstract logic by adding the concept of a syntax and an axiom system. In a recursive logic frame the syntax and the set of axioms are recursively coded. A recursive logic frame is called complete , if every finite consistent theory has a model. We show that for logic frames built from the cardinality quantifiers “there exists at least λ ” completeness always implies .0-compactness. On (...) the other hand we show that a recursively compact logic frame need not be ℵ0-compact. (shrink)

Lindström’s Theorem characterizes first order logic as the maximal logic satisfying the Compactness Theorem and the Downward Löwenheim-Skolem Theorem. If we do not assume that logics are closed under negation, there is an obvious extension of first order logic with the two model theoretic properties mentioned, namely existential second order logic. We show that existential second order logic has a whole family of proper extensions satisfying the Compactness Theorem and the Downward Löwenheim-Skolem Theorem. Furthermore, we show that in the context (...) of negation-less logics, _positive logics_, as we call them, there is no strongest extension of first order logic with the Compactness Theorem and the Downward Löwenheim-Skolem Theorem. (shrink)

Following Henkin's discovery of partially-ordered (branching) quantification (POQ) with standard quantifiers in 1959, philosophers of language have attempted to extend his definition to POQ with generalized quantifiers. In this paper I propose a general definition of POQ with 1-place generalized quantifiers of the simplest kind: namely, predicative, or "cardinality" quantifiers, e.g., "most", "few", "finitely many", "exactly α", where α is any cardinal, etc. The definition is obtained in a series of generalizations, extending the original, Henkin definition first to a general (...) definition of monotone-increasing (M↑) POQ and then to a general definition of generalized POQ, regardless of monotonicity. The extension is based on (i) Barwise's 1979 analysis of the basic case of M↑ POQ and (ii) my 1990 analysis of the basic case of generalized POQ. POQ is a non-compositional Ist-order structure, hence the problem of extending the definition of the basic case to a general definition is not trivial. The paper concludes with a sample of applications to natural and mathematical languages. (shrink)

The paper offers a new analysis of the difficulties involved in the construction of a general and substantive correspondence theory of truth and delineates a solution to these difficulties in the form of a new methodology. The central argument is inspired by Kant, and the proposed methodology is explained and justified both in general philosophical terms and by reference to a particular variant of Tarski's theory. The paper begins with general considerations on truth and correspondence and concludes with a brief (...) outlook on the "family" of theories of truth generated by the new methodology. (shrink)

Philosophers are divided on whether the proof- or truth-theoretic approach to logic is more fruitful. The paper demonstrates the considerable explanatory power of a truth-based approach to logic by showing that and how it can provide (i) an explanatory characterization —both semantic and proof-theoretical—of logical inference, (ii) an explanatory criterion for logical constants and operators, (iii) an explanatory account of logic’s role (function) in knowledge, as well as explanations of (iv) the characteristic features of logic —formality, strong modal force, generality, (...) topic neutrality, basicness, and (quasi-)apriority, (v) the veridicality of logic and its applicability to science, (v) the normativity of logic, (vi) error, revision, and expansion in/of logic, and (vii) the relation between logic and mathematics. The high explanatory power of the truth-theoretic approach does not rule out an equal or even higher explanatory power of the proof-theoretic approach. But to the extent that the truth-theoretic approach is shown to be highly explanatory, it sets a standard for other approaches to logic, including the proof-theoretic approach. (shrink)

In this paper I discuss Mark Steiner’s view of the contribution of mathematics to physics and take up some of the questions it raises. In particular, I take up the question of discovery and explore two aspects of this question – a metaphysical aspect and a related epistemic aspect. The metaphysical aspect concerns the formal structure of the physical world. Does the physical world have mathematical or formal features or constituents, and what is the nature of these constituents? The related (...) epistemic question concerns humans’ cognitive ability to reach the formal structure of the physical world. Among other things, I explore the interaction of mathematical and non-mathematical cognition in physical discovery. (shrink)

Many philosophers are baffled by necessity. Humeans, in particular, are deeply disturbed by the idea of necessary laws of nature. In this paper I offer a systematic yet down to earth explanation of necessity and laws in terms of invariance. The type of invariance I employ for this purpose generalizes an invariance used in meta-logic. The main idea is that properties and relations in general have certain degrees of invariance, and some properties/relations have a stronger degree of invariance than others. (...) The degrees of invariance of highly-invariant properties are associated with high degrees of necessity of laws governing/describing these properties, and this explains the necessity of such laws both in logic and in science. This non-mysterious explanation has rich ramifications for both fields, including the formality of logic and mathematics, the apparent conflict between the contingency of science and the necessity of its laws, the difference between logical-mathematical, physical, and biological laws/principles, the abstract character of laws, the applicability of logic and mathematics to science, scientific realism, and logical-mathematical realism. (shrink)

In his 1936 paper,On the Concept of Logical Consequence, Tarski introduced the celebrated definition oflogical consequence: “The sentenceσfollows logicallyfrom the sentences of the class Γ if and only if every model of the class Γ is also a model of the sentenceσ.” [55, p. 417] This definition, Tarski said, is based on two very basic intuitions, “essential for the proper concept of consequence” [55, p. 415] and reflecting common linguistic usage: “Consider any class Γ of sentences and a sentence which (...) follows from the sentences of this class. From an intuitive standpoint it can never happen that both the class Γ consists only of true sentences and the sentenceσis false. Moreover, … we are concerned here with the concept of logical, i.e.,formal, consequence.” [55, p. 414] Tarski believed his definition of logical consequence captured the intuitive notion: “It seems to me that everyone who understands the content of the above definition must admit that it agrees quite well with common usage. … In particular, it can be proved, on the basis of this definition, that every consequence of true sentences must be true.” [55, p. 417] The formality of Tarskian consequences can also be proven. Tarski's definition of logical consequence had a key role in the development of the model-theoretic semantics of modern logic and has stayed at its center ever since. (shrink)