Contemporary semantic description of logic is based on the ontology of all possible interpretations, an insufficiently clear metaphysical concept. In this article, logic is described as the internal organization of language. Logical concepts -- logical constants, logical truths, and logical consequence -- are defined using the internal syntactic and semantic structure of language. For a first-order language, it has been shown that its logical constants are connectives and a certain type of quantifiers for which (...) the universal and existential quantifiers form a functionally complete set of quantifiers. Neither equality nor cardinal quantifiers belong to the logical constants of a first-order language. (shrink)

In this article, logical concepts are defined using the internal syntactic and semantic structure of language. For a first-order language, it has been shown that its logical constants are connectives and a certain type of quantifiers for which the universal and existential quantifiers form a functionally complete set of quantifiers. Neither equality nor cardinal quantifiers belong to the logical constants of a first-order language.

This paper presents a simple decidable logic of functional dependence LFD, based on an extension of classical propositional logic with dependence atoms plus dependence quantifiers treated as modalities, within the setting of generalized assignment semantics for first order logic. The expressive strength, complete proof calculus and meta-properties of LFD are explored. Various language extensions are presented as well, up to undecidable modal-style logics for independence and dynamic logics of changing dependence models. Finally, more concrete settings for dependence are (...) discussed: continuous dependence in topological models, linear dependence in vector spaces, and temporal dependence in dynamical systems and games. (shrink)

This paper establishes a sound and complete semantics for the impure logic of ground. Fine (Review of Symbolic Logic, 5(1), 1–25, 2012a) sets out a system for the pure logic of ground, one in which the formulas between which ground-theoretic claims hold have no internal logical complexity; and it provides a sound and complete semantics for the system. Fine (2012b) [§§6-8] sets out a system for an impure logic of ground, one that extends the rules of the (...) original pure system with rules for the truth-functional connectives, the first-order quantifiers, and λ-abstraction. However, no semantics has yet been provided for this system. The present paper partly fills this lacuna by providing a sound and complete semantics for a system GG containing the truth-functional operators that is closely related to the truth-functional part of the system of Fine (2012b). (shrink)

The quantified relevant logic RQ is given a new semantics in which a formula for all xA is true when there is some true proposition that implies all x-instantiations of A. Formulae are modelled as functions from variable-assignments to propositions, where a proposition is a set of worlds in a relevant model structure. A completeness proof is given for a basic quantificational system QR from which RQ is obtained by adding the axiom EC of 'extensional confinement': for all x(A V (...) B) -> (A V for all xB). with x not free in A. Validity of EC requires an additional model condition involving the boolean difference of propositions. A QR-model falsifying EC is constructed by forming the disjoint union of two natural arithmetical structures in which negation is interpreted by the minus operation. (shrink)

A classical result by Słupecki states that a logic L is functionally complete for the 3-element set of truth-values THREE if, in addition to functionally including Łukasiewicz’s 3-valued logic Ł3, what he names the ‘$T$-function’ is definable in L. By leaning upon this classical result, we prove a general theorem for defining binary expansions of Kleene’s strong logic that are functionally complete for THREE.

Here is an account of logical consequence inspired by Bolzano and Tarski. Logical validity is a property of arguments. An argument is a pair of a set of interpreted sentences (the premises) and an interpreted sentence (the conclusion). Whether an argument is logically valid depends only on its logical form. The logical form of an argument is fixed by the syntax of its constituent sentences, the meanings of their logical constituents and the syntactic differences between (...) their non-logical constituents, treated as variables. A constituent of a sentence is logical just if it is formal in meaning, in the sense roughly that its application is invariant under permutations of individuals.1 Thus ‘=’ is a logical constant because no permutation maps two individuals to one or one to two; ‘∈’ is not a logical constant because some permutations interchange the null set and its singleton. Truth functions, the usual quantifiers and bound variables also count as logical constants. An argument is logically valid if and only if the conclusion is true under every assignment of semantic values to variables (including all non-logical expressions) under which all its premises are true. A sentence is logically true if and only if the argument with no premises of which it is the conclusion is logically valid, that is, if and only if the sentence is true under every assignment of semantic values to variables. An interpretation assigns values to all variables. (shrink)

A set of propositional connectives is said to be functionally complete if all propositional formulae can be expressed using only connectives from that set. In this paper we give sufficient and necessary conditions for a one-element set of propositional connectives to be functionally complete. These conditions provide a simple and elegant characterization of functionally complete one-element sets of propositional connectives.

We present an algebraic-style of semantics, which we call a content semantics, for quantified relevant logics based on the weak system BBQ. We show soundness and completeness for all quantificational logics extending BBQ and also treat reduced modelling for all systems containing BB d Q. The key idea of content semantics is that true entailments AB are represented under interpretation I as content containments, i.e. I(A)I(B) (or, the content of A contains that of B). This is opposed to the truth-functional (...) way which represents true entailments as truth-preservations over all set-ups (or worlds), i.e. (VaK) (if I(A, a) = T then I(B, a)= T). (shrink)

We can think of functional completeness in systems of propositional logic as a form of expressive completeness: while every logical constant in such system expresses a truth-function of finitely many arguments, functional completeness garantees that every truth-function of finitely many arguments can be expressed with the constants in the system. From this point of view, a functionnaly complete system of propositionnal logic can thus be seen as one where no logical constant is missing. Can a similar question (...) be formulated for quantified first-order logics ? How to make sense of the question whether, e.g., ordinary first-order logic is "functionaly" complete or have no logical constant missing ? In this note, we build on a suggestive proposal made by Bonnay(2006) and shows that it is equivalent to the criterion that a first-order logic L be functionaly complete if and only if every class of structures closed under L-elementary equivalence is L-elementary. Ordinary first-order logic is not complete in this sense. We raise the question whether any logic can be. -/- . (shrink)

Ordinary equational logic is a connective-free fragment of first-order logic which is concerned with total functions under the relation of ordinary equality. In [AN] (see also [AN1]) and in [Cr] it has been extended in two equivalent ways into a near-equational system of logic for partial functions. The extension given in [Cr] deals with partial functions under two relationships: a relationship of existence-dependent existence and one of existence-dependent Kleene equality. For the language that involves both relationships a set of rules (...) was given that is complete. Those rules in the set that involve only existence-dependent existence turned out to be complete for the sublanguage that involves this relationship only. In the present paper we give a set of rules that is complete for the other sublanguage, namely the language of partial functions under existence-dependent Kleene equality.This language lacks a certain, often needed, power of expressing existence and fails, in particular, to be an extension of the language that underlies ordinary equational logic. That it possesses a fairly simple complete set of rules is therefore perhaps more of theoretical than of practical interest. The present paper is thus intended to serve as a supplement to [Cr] and, less directly, to [AN]. The subject is further rounded out, and some contrast is provided, by [Rob]. The systems of logic treated there are based on the weaker language in which partial functions are considered under the more basic relation of Kleene equality. (shrink)

Here is an account of logical consequence inspired by Bolzano and Tarski. Logical validity is a property of arguments. An argument is a pair of a set of interpreted sentences (the premises) and an interpreted sentence (the conclusion). Whether an argument is logically valid depends only on its logical form. The logical form of an argument is fixed by the syntax of its constituent sentences, the meanings of their logical constituents and the syntactic differences between (...) their non-logical constituents, treated as variables. A constituent of a sentence is logical just if it is formal in meaning, in the sense roughly that its application is invariant under permutations of individuals.1 Thus ‘=’ is a logical constant because no permutation maps two individuals to one or one to two; ‘∈’ is not a logical constant because some permutations interchange the null set and its singleton. Truth functions, the usual quantifiers and bound variables also count as logical constants. An argument is logically valid if and only if the conclusion is true under every assignment of semantic values to variables (including all non-logical expressions) under which all its premises are true. A sentence is logically true if and only if the argument with no premises of which it is the conclusion is logically valid, that is, if and only if the sentence is true under every assignment of semantic values to variables. An interpretation assigns values to all variables. (shrink)

Combining modalities has proven to have interesting applications and many approaches that combine time with other types of modalities have been developed. One of these approaches uses accessibility functions between flows of time to study the basic properties of the functions, such as being total or partial, injective, surjective, etc. The completeness of certain systems expressing many of these properties, with the exception of surjectivity, has been proven. In this paper we propose a language with nominals to denote the initial (...) and final sets of each function in a model in order to obtain a complete system for reasoning about surjective partial functions. (shrink)

This thesis is concerned with extending the underlying logical approach as well as the breadth of applications of the proof mining program to various (mostly previously untreated) areas of nonlinear analysis and optimization, with a particular focus being placed on topics which involve set-valued operators.For this, we extend the current logical methodology of proof mining by new systems and corresponding so-called logical metatheorems that cover these more involved areas of nonlinear analysis. Most of these systems crucially rely (...) on the use of intensional methods, treating sets with potentially high quantifier complexity in the defining matrix via characteristic functions and axioms that describe only their properties and do not completely characterize the elements of the sets.The applicability of all of these metatheorems is then substantiated by a range of case studies for the respective areas which in particular also highlight the naturalness of the use of intensional methods in the design of the corresponding systems.The first new area covered thereby is the theory of nonlinear semigroups induced by corresponding evolution equations for accretive operators. In that context, we present (besides an initial foray into the area from 2015) essentially the first applications of proof mining to the theory of partial differential equations. Concretely, we provide quantitative versions of four central results on the asymptotic behavior of solutions to such equations.The second new area unlocked in this thesis is that of the continuous dual of a Banach space and its norm (which are also approached via intensional methods). This in particular relies on a proof-theoretically tame treatment of suprema over (certain) bounded sets in this intensional context which is further exploited later on. These systems, which give access to this until now untreated fundamental notion from functional analysis, are then used to provide further substantial extensions to treat various notions from convex analysis like the Fréchet derivative of a convex function, Fenchel conjugates, Bregman distances, and monotone operators on Banach spaces in the sense of Browder.These systems are then utilized to provide applications in the context of Picard- and Halpern-style iterations of so-called Bregman strongly nonexpansive mappings where we provide both new quantitative and qualitative results.Lastly, we discuss the key notion of extensionality of a set-valued operator and its relation to set-theoretic maximality principles in more depth (which was already singled out—to some degree—in previous work). We thereby exhibit an issue arising with treating full extensionality in the context of these intensional approaches to set-valued operators and present useful fragments of the full extensionality statement where these issues are avoided.Corresponding to these fragments, we discuss a range of uniform continuity statements for set-valued operators beyond the usual notion involving the Hausdorff-metric. In particular, in that context, we utilize the previous tame treatment of suprema over bounded sets to also provide the first proof-theoretic treatment of that Hausdorff-metric in the context of systems for proof mining.The applicability of this treatment of the Hausdorff-metric is then in particular substantiated by a last case study where we provide quantitative information for a Mann-type iteration of set-valued mappings which are nonexpansive w.r.t. the Hausdorff-metric.The abstract was taken directly from the thesis.Abstract prepared by Nicholas Pischke, Technische Universität Darmstadt, Darmstadt, GermanyE-mail: [email protected]: https://doi.org/10.26083/tuprints-00026584. (shrink)

Volume II of Classical Recursion Theory describes the universe from a local (bottom-up or synthetical) point of view, and covers the whole spectrum, from the recursive to the arithmetical sets. The first half of the book provides a detailed picture of the computable sets from the perspective of Theoretical Computer Science. Besides giving a detailed description of the theories of abstract Complexity Theory and of Inductive Inference, it contributes a uniform picture of the most basic complexity classes, ranging from small (...) time and space bounds to the elementary functions, with a particular attention to polynomial time and space computability. It also deals with primitive recursive functions and larger classes, which are of interest to the proof theorist. The second half of the book starts with the classical theory of recursively enumerable sets and degrees, which constitutes the core of Recursion or Computability Theory. Unlike other texts, usually confined to the Turing degrees, the book covers a variety of other strong reducibilities, studying both their individual structures and their mutual relationships. The last chapters extend the theory to limit sets and arithmetical sets. The volume ends with the first textbook treatment of the enumeration degrees, which admit a number of applications from algebra to the Lambda Calculus. The book is a valuable source of information for anyone interested in Complexity and Computability Theory. The student will appreciate the detailed but informal account of a wide variety of basic topics, while the specialist will find a wealth of material sketched in exercises and asides. A massive bibliography of more than a thousand titles completes the treatment on the historical side. (shrink)

This paper investigates a problem related to quantifiers which has some analogies to that of propositional completeness I give a definition of quantifier in many-valued logics generalizing the cases which already occur in first order many- valued logics. Though other definitions are possible, this particular one, which I call distribution quantifiers, generalizes the classical quantifiers in a very natural way, and occurs in finite numbers in every m-valued logic. We then call the problem of quantificationa2 completeness in (...) m-valued logic the problem of characterizing which are the quantifiers in a given language which can generate all other quantifiers in this language, using the connectives, as is the case, for example, of the universal and exis- tential quantifiers in classical logic, using negation. We are interested, in particular, in those many-valued quantifiers which closely mimic the behavior of existential an universal quantifiers in generating all other quantifiers using negation: these I call perfect quantifiers, as defined below. The main result of this paper is the characterization of all perfect quantifiers in 3-valued logics, which are complete if the logic is functionally complete. As a byproduct, we obtain the same result for the classical logic, which we include mainly for motivation. (shrink)

The Routley-Meyer relational semantics for relevant logics is extended to give a sound and complete model theory for many propositionally quantified relevant logics (and some non-relevant ones). This involves a restriction on which sets of worlds are admissible as propositions, and an interpretation of propositional quantification that makes ∀ pA true when there is some true admissible proposition that entails all p -instantiations of A . It is also shown that without the admissibility qualification many of the systems considered (...) are semantically incomplete, including all those that are sub-logics of the quantified version of Anderson and Belnap’s system E of entailment, extended by the mingle axiom and the Ackermann constant t . The incompleteness proof involves an algebraic semantics based on atomless complete Boolean algebras. (shrink)

The present paper is a sequel to Robles et al. :349–374, 2020. https://doi.org/10.1007/s10849-019-09306-2). A class of implicative expansions of Kleene’s 3-valued logic functionally including Łukasiewicz’s logic Ł3 is defined. Several properties of this class and/or some of its subclasses are investigated. Properties contemplated include functional completeness for the 3-element set of truth-values, presence of natural conditionals, variable-sharing property and vsp-related properties.

We give a completeness theorem for a logic with probability quantifiers which is equivalent to the logics described in a recent survey paper of Keisler [K]. This result improves on the completeness theorems in [K] in that it works for languages with function symbols and produces a model whose universe is an analytic subset of the real line, and whose relations and functions are Borel relative to this universe.

In many-valued logic the decision of functional completeness is a basic and important problem, and the thorough solution to this problem depends on determining all maximal closed sets in the set of many-valued logic functions. It includes three famous problems, i.e., to determine all maximal closed sets in the set of the total, of the partial and of the unary many-valued logic functions, respectively. The first two problems have been completely solved , and the solution to the third problem boils (...) down to determining all maximal subgroups in the k-degree symmetric group Sk, which is an open problem in the finite group theory. In this paper, all maximal closed sets in the set of unary p-valued logic functions are determined, where p is a prime. (shrink)

Table of Contents Volume I Preface to Volumes I and II: A Guide to the Primer Chapter 1, Basic Ideas and Tools Chapter 2, Transcription between English and Sentence Logic Chapter 3, Logical Equivalence, Logical Truths, and Contradictions Chapter 4, Validity and Conditionals Chapter 5, Natural Deduction for Sentence Logic: Fundamentals Chapter 6, Natural Deduction for Sentence Logic: Strategies Chapter 7, Natural Deduction for Sentence Logic: Derived Rules and Derivations without Premises Chapter 8, Truth Tree for Sentence Logic: (...) Fundamentals Chapter 9, Truth Trees for Sentence Logic: Applications Index for Volume 1 Solutions Manual for Volume 1 Table of Contents to Volume II Introduction to Predicate Logic Notes Chapter 1, Predicate Logic: Syntax Chapter 2, Predicate Logic: Semantics and Validity Chapter 3, More about Quantifiers Chapter 4, Transcription Chapter 5, Natural Deduction for Predicate Logic: Fundamentals Chapter 6, More on Natural Deduction for Predicate Logic Chapter 7, Truth Tress for Predicate Logic: Fundamentals Chapter 8, More on Truth Tress for Predicate Logic Chapter 9, Identity, Functions, and Definite Descriptions Chapter 10, Metatheory: The Basic Concepts Chapter 11, Mathematical Induction Chapter 12, Soundness and Completeness for Sentence Logic Trees Chapter 13, Soundness and Completeness for Sentence Logic Derivations Chapter 14, Koenig’s Lemma, Compactness, and Generalization to Infinite Sets of Premises Chapter 15, Interpretations, Soundness, and Completeness for Predicate Logic Index for Volume II Solutions Manual for Volume II Diagrammatic Summary of Rules Corrections to the Text. (shrink)

The question motivating my investigation is: Are the basic philosophical principles underlying the "core" system of contemporary logic exhausted by the standard version? In particular, is the accepted narrow construal of the notion "logical term" justified? ;As a point of comparison I refer to systems of 1st-order logic with generalized quantifiers developed by mathematicians and linguists . Based on an analysis of the Tarskian conception of the role of logic I show that the standard division of terms into (...) logical and extra-logical is partly arbitrary. I argue that the semantic principles of Tarskian logic allow any higher order mathematical predicate or relation to function as a logical term in a 1st-order system, provided it is introduced in the right way into the syntactic-semantic apparatus. ;Formally, I propose a new, "constructive", semantic characterization of logical terms. A logical term is defined by a function which, given a model, "shows" how to construct relations, sets, or n-tuples of individuals which satisfy it. I discuss the linguistic applicability of the extended logic and bring numerous examples. ;One chapter is devoted to branching quantification--a non-standard logico-linguistic construction obtained by affixing a non-linear, partially-ordered quantifier-prefix to a well-formed formula. Although standard branching quantifiers were given a complete account by Henkin and Walkoe, it is not altogether clear what the meaning of branching generalized quantifiers is. I propose a new analysis of the generalized branching prefix which extends the existent, partial, definitions due to Barwise, and I develop a generalization leading to a "family" of branching structures. ;In conclusion I discuss the philosophical impact of the generalized conception of logic on such issues as the logicist thesis, the interaction between mathematics and logic, ontological commitment via logic, metaphysics and logical semantics. (shrink)

LetMbe a countably infinite ω-categorical structure. Consider Aut(M) as a complete metric space by definingd(g, h) = Ω{2−n:g(xn) ≠h(xn) org−1(xn) ≠h−1(xn)} where {xn:n∈ ω} is an enumeration ofMAn automorphism α ∈ Aut(M) is generic if its conjugacy class is comeagre. J. Truss has shown in [11] that if the set P of all finite partial isomorphisms contains a co-final subset P1closed under conjugacy and having the amalgamation property and the joint embedding property then there is a generic automorphism. In (...) the present paper we give a weaker condition of this kind which is equivalent to the existence of generic automorphisms. Really we give more: a characterization of the existence of generic expansions (defined in an appropriate way) of an ω-categorical structure. We also show that Truss' condition guarantees the existence of a countable structure consisting of automorphisms ofMwhich can be considered as an atomic model of some theory naturally associated toM. We do it in a general context of weak models for second-order quantifiers.The author thanks Ludomir Newelski for pointing out a mistake in the first version of Theorem 1.2 and for interesting discussions. Also, the author is grateful to the referee for very helpful remarks. (shrink)

Kooi and Tamminga's correspondence analysis is a technique for designing proof systems, mostly, natural deduction and sequent systems. In this paper it is used to generate sequent calculi with invertible rules, whose only branching rule is the rule of cut. The calculi pertain to classical propositional logic and any of its fragments that may be obtained from adding a set of rules characterizing a two-argument Boolean function to the negation fragment of classical propositional logic. The properties of soundness and completeness (...) of the calculi are demonstrated. The proof of completeness is conducted by Kalmár's method. Most of the presented sequent-calculus rules have been obtained automatically, by a rule-generating algorithm implemented in Python. Correctness of the algorithm is demonstrated. This automated approach allowed us to analyse thousands of possible rules' schemes, hundreds of rules corresponding to Boolean functions, and to nd dozens of those invertible. Interestingly, the analysis revealed that the presented proof-theoretic framework provides a syntactic characteristics of such an important semantic property as functional completeness. (shrink)

In this paper we study the logic of relational and partial variable sets, seen as a generalization of set-valued presheaves, allowing transition functions to be arbitrary relations or arbitrary partial functions. We find that such a logic is the usual intuitionistic and co-intuitionistic first order logic without Beck and Frobenius conditions relative to quantifiers along arbitrary terms. The important case of partial variable sets is axiomatizable by means of the substitutivity schema for equality. Furthermore, completeness, incompleteness and independence results (...) are obtained for different kinds of Beck and Frobenius conditions. (shrink)

This paper presents an extended version of the Quantified Argument Calculus (Quarc). Quarc is a logic comparable to the first-order predicate calculus. It employs several nonstandard syntactic and semantic devices, which bring it closer to natural language in several respects. Most notably, quantifiers in this logic are attached to one-place predicates; the resulting quantified constructions are then allowed to occupy the argument places of predicates. The version presented here is capable of straightforwardly translating natural-language sentences involving defining clauses. A (...) three-valued, model-theoretic semantics for Quarc is presented. Interpretations in this semantics are not equipped with domains of quantification: they are just interpretation functions. This reflects the analysis of natural-language quantification on which Quarc is based. A proof system is presented, and a completeness result is obtained. The logic presented here is capable of straightforward translation of the classical first-order predicate calculus, the translation preserving truth values as well as entailment. The first-order predicate calculus and its devices of quantification can be seen as resulting from Quarc on certain semantic and syntactic restrictions, akin to simplifying assumptions. An analogous, straightforward translation of Quarc into the first-order predicate calculus is impossible. (shrink)

A Border Disputeintegrates the latest work in logic and semantics into a theory of language learning and presents six worked examples of how that theory revolutionizes cognitive psychology. Macnamara's thesis is set against the background of a fresh analysis of the psychologism debate of the 19th-century, which led to the current standoff between logic and psychology. The book presents psychologism through the writings of John Stuart Mill and Immanuel Kant, and its rejection by Gottlob Frege and Edmund Husserl. It then (...) works out the general thesis that logic ideally presents a competence theory for part of human reasoning and explains how logical intuition is grounded in properties of the mind. The next six chapters present examples that illustrate the relevance of logic to psychology. These problems are all in the semantics of child language (the learning of proper names, personal pronouns, sortals or common nouns, quantifiers, and the truth-functional connectives) and reflect Macnamara's rich background in developmental psychology, particularly child language - a field, he points out, that embraces all of cognition. Technical problems raised by but not included in the examples in the main part of the text are dealt with in a separate chapter. The book concludes by describing laws in cognitive psychology, or the type of science made possible by Macnamara's new theory. John Macnamara is Professor of Psychology and Director of the Program in the History and Philosophy of Science, McGill University. A Bradford Book. (shrink)

The research presented in this paper was motivated by our aim to study a problem due to J. Bourgain [3]. The problem in question concerns the uniform boundedness of the classical separation rank of the elements of a separable compact set of the first Baire class. In the sequel we shall refer to these sets (separable or non-separable) as Rosenthal compacta and we shall denote by ∝(f) the separation rank of a real-valued functionfinB1(X), withXa Polish space. Notice that in [3], (...) Bourgain has provided a positive answer to this problem in the case ofKsatisfyingwithXa compact metric space. The key ingredient in Bourgain's approach is that whenever a sequence of continuous functions pointwise converges to a functionf, then the possible discontinuities of the limit function reflect a local ℓ1-structure to the sequence (fn)n. More precisely the complexity of this ℓ1-structure increases as the complexity of the discontinuities offdoes. This fruitful idea was extensively studied by several authors (c.f. [5], [7], [8]) and for an exposition of the related results we refer to [1]. It is worth mentioning that A.S. Kechris and A. Louveau have invented the rank rND(f) which permits the link between thec0-structure of a sequence (fn)nof uniformly bounded continuous functions and the discontinuities of its pointwise limit. Rosenthal'sc0-theorem [11] and thec0-index theorem [2] are consequences of this interaction.Passing to the case where either (fn)nare not continuous orXis a non-compact Polish space, this nice interaction is completely lost. (shrink)

We study several modal languages in which some (sets of) generalized quantifiers can be represented; the main language we consider is suitable for defining any first order definable quantifier, but we also consider a sublanguage thereof, as well as a language for dealing with the modal counterparts of some higher order quantifiers. These languages are studied both from a modal logic perspective and from a quantifier perspective. Thus the issues addressed include normal forms, expressive power, completeness both of (...) modal systems and of systems in the quantifier tradition, complexity as well as syntactic characterizations of special semantic constraints. Throughout the paper several techniques current in the theory of generalized quantifiers are used to obtain results in modal logic, and conversely. (shrink)

We study several modal languages in which some (sets of) generalized quantifiers can be represented; the main language we consider is suitable for defining any first order definable quantifier, but we also consider a sublanguage thereof, as well as a language for dealing with the modal counterparts of some higher order quantifiers. These languages are studied both from a modal logic perspective and from a quantifier perspective. Thus the issues addressed include normal forms, expressive power, completeness both of (...) modal systems and of systems in the quantifier tradition, complexity as well as syntactic characterizations of special semantic constraints. Throughout the paper several techniques current in the theory of generalized quantifiers are used to obtain results in modal logic, and conversely. (shrink)

Many proposals for logic-based formalisations of argumentation consider an argument as a pair (Φ,α), where the support Φ is understood as a minimal consistent subset of a given knowledge base which has to entail the claim α. In case the arguments are given in the full language of classical propositional logic reasoning in such frameworks becomes a computationally costly task. For instance, the problem of deciding whether there exists a support for a given claim has been shown to be - (...) class='Hi'>complete. In order to better understand the sources of complexity (and to identify tractable fragments), we focus on arguments given over formulæ in which the allowed connectives are taken from certain sets of Boolean functions. We provide a complexity classification for four different decision problems (existence of a support, checking the validity of an argument, relevance and dispensability) with respect to all possible sets of Boolean functions. Moreover, we make use of a general schema to enumerate all arguments to show that certain restricted fragments permit polynomial delay. Finally, we give a classification also in terms of counting complexity. (shrink)

We give an axiomatic characterization for complete elementary extensions, that is, elementary extensions of the first-order structure consisting of all finitary relations and functions on the underlying set. Such axiom systems have been studied using various types of primitive notions . Our system uses the notion of partial functions as primitive. Properties of nonstandard extensions are derived from five axioms in a rather algebraic way, without the use of metamathematical notions such as formulas or satisfaction. For example, when applied (...) to the real number system, it provides a complete framework for developing nonstandard analysis based on hyperreals without having to construct them and without any use of logic. This has possible pedagogical and expository applications as presented in, e.g., [5], [6]. © 2011 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim. (shrink)

We take a fresh look at the logics of informational dependence and independence of Hintikka and Sandu and Väänänen, and their compositional semantics due to Hodges. We show how Hodges’ semantics can be seen as a special case of a general construction, which provides a context for a useful completeness theorem with respect to a wider class of models. We shed some new light on each aspect of the logic. We show that the natural propositional logic carried by the semantics (...) is the logic of Bunched Implications due to Pym and O’Hearn, which combines intuitionistic and multiplicative connectives. This introduces several new connectives not previously considered in logics of informational dependence, but which we show play a very natural rôle, most notably intuitionistic implication. As regards the quantifiers, we show that their interpretation in the Hodges semantics is forced, in that they are the image under the general construction of the usual Tarski semantics; this implies that they are adjoints to substitution, and hence uniquely determined. As for the dependence predicate, we show that this is definable from a simpler predicate, of constancy or dependence on nothing. This makes essential use of the intuitionistic implication. The Armstrong axioms for functional dependence are then recovered as a standard set of axioms for intuitionistic implication. We also prove a full abstraction result in the style of Hodges, in which the intuitionistic implication plays a very natural rôle. (shrink)

In the dissertation we study the complexity of generalized quantifiers in natural language. Our perspective is interdisciplinary: we combine philosophical insights with theoretical computer science, experimental cognitive science and linguistic theories. -/- In Chapter 1 we argue for identifying a part of meaning, the so-called referential meaning (model-checking), with algorithms. Moreover, we discuss the influence of computational complexity theory on cognitive tasks. We give some arguments to treat as cognitively tractable only those problems which can be computed in polynomial (...) time. Additionally, we suggest that plausible semantic theories of the everyday fragment of natural language can be formulated in the existential fragment of second-order logic. -/- In Chapter 2 we give an overview of the basic notions of generalized quantifier theory, computability theory, and descriptive complexity theory. -/- In Chapter 3 we prove that PTIME quantifiers are closed under iteration, cumulation and resumption. Next, we discuss the NP-completeness of branching quantifiers. Finally, we show that some Ramsey quantifiers define NP-complete classes of finite models while others stay in PTIME. We also give a sufficient condition for a Ramsey quantifier to be computable in polynomial time. -/- In Chapter 4 we investigate the computational complexity of polyadic lifts expressing various readings of reciprocal sentences with quantified antecedents. We show a dichotomy between these readings: the strong reciprocal reading can create NP-complete constructions, while the weak and the intermediate reciprocal readings do not. Additionally, we argue that this difference should be acknowledged in the Strong Meaning hypothesis. -/- In Chapter 5 we study the definability and complexity of the type-shifting approach to collective quantification in natural language. We show that under reasonable complexity assumptions it is not general enough to cover the semantics of all collective quantifiers in natural language. The type-shifting approach cannot lead outside second-order logic and arguably some collective quantifiers are not expressible in second-order logic. As a result, we argue that algebraic (many-sorted) formalisms dealing with collectivity are more plausible than the type-shifting approach. Moreover, we suggest that some collective quantifiers might not be realized in everyday language due to their high computational complexity. Additionally, we introduce the so-called second-order generalized quantifiers to the study of collective semantics. -/- In Chapter 6 we study the statement known as Hintikka's thesis: that the semantics of sentences like ``Most boys and most girls hate each other'' is not expressible by linear formulae and one needs to use branching quantification. We discuss possible readings of such sentences and come to the conclusion that they are expressible by linear formulae, as opposed to what Hintikka states. Next, we propose empirical evidence confirming our theoretical predictions that these sentences are sometimes interpreted by people as having the conjunctional reading. -/- In Chapter 7 we discuss a computational semantics for monadic quantifiers in natural language. We recall that it can be expressed in terms of finite-state and push-down automata. Then we present and criticize the neurological research building on this model. The discussion leads to a new experimental set-up which provides empirical evidence confirming the complexity predictions of the computational model. We show that the differences in reaction time needed for comprehension of sentences with monadic quantifiers are consistent with the complexity differences predicted by the model. -/- In Chapter 8 we discuss some general open questions and possible directions for future research, e.g., using different measures of complexity, involving game-theory and so on. -/- In general, our research explores, from different perspectives, the advantages of identifying meaning with algorithms and applying computational complexity analysis to semantic issues. It shows the fruitfulness of such an abstract computational approach for linguistics and cognitive science. (shrink)

The aim of this article is to give an introduction to functional interpretations of set theory given by the authorin Burr (2000a). The first part starts with some general remarks on Gödel's functional interpretation with a focus on aspects related to problems that arise in the context of set theory. The second part gives an insight in the techniques needed to perform a functional interpretation of systems of set theory. However, the first part of this article is not intended to (...) be a complete survey of functional interpretations and here we recommend, for example, Avigad and Feferman (1998),Troelstra (1990) and Troelstra (1973). (shrink)

In their recent paper Bi-facial truth: a case for generalized truth values Zaitsev and Shramko [7] distinguish between an ontological and an epistemic interpretation of classical truth values. By taking the Cartesian product of the two disjoint sets of values thus obtained, they arrive at four generalized truth values and consider two “semi-classical negations” on them. The resulting semantics is used to define three novel logics which are closely related to Belnap’s well-known four valued logic. A syntactic characterization of these (...) logics is left for further work. In this paper, based on our previous work on a functionally complete extension of Belnap’s logic, we present a sound and complete tableau calculus for these logics. It crucially exploits the Cartesian nature of the four values, which is reflected in the fact that each proof consists of two tableaux. The bi-facial notion of truth of Z&S is thus augmented with a bi-facial notion of proof. We also provide translations between the logics for semi-classical negation and classical logic and show that an argument is valid in a logic for semi-classical negation just in case its translation is valid in classical logic. (shrink)

We describe an extension to our quantifier-free computational logic to provide the expressive power and convenience of bounded quantifiers and partial functions. By quantifier we mean a formal construct which introduces a bound or indicial variable whose scope is some subexpression of the quantifier expression. A familiar quantifier is the Σ operator which sums the values of an expression over some range of values on the bound variable. Our method is to represent expressions of the logic as objects in (...) the logic, to define an interpreter for such expressions as a function in the logic, and then define quantifiers as "mapping functions." The novelty of our approach lies in the formalization of the interpreter and its interaction with the underlying logic. Our method has several advantages over other formal systems that provide quantifiers and partial functions in a logical setting. The most important advantage is that proofs not involving quantification or partial recursive functions are not complicated by such notions as "capturing," "bottom," or "continuity." Naturally enough, our formalization of the partial functions is nonconstructive. The theorem prover for the logic has been modified to support these new features. We describe the modifications. The system has proved many theorems that could not previously be stated in our logic. Among them are. (shrink)

The paper develops a set of quantified temporal alethic boulesic doxastic systems. Every system in this set consists of five parts: a ‘quantified’ part, a temporal part, a modal (alethic) part, a boulesic part and a doxastic part. There are no systems in the literature that combine all of these branches of logic. Hence, all systems in this paper are new. Every system is defined both semantically and proof-theoretically. The semantic apparatus consists of a kind of$$T \times W$$T×Wmodels, and the (...) proof-theoretical apparatus of semantic tableaux. The ‘quantified part’ of the systems includes relational predicates and the identity symbol. The quantifiers are, in effect, a kind of possibilist quantifiers that vary over every object in the domain. The tableaux rules are classical. The alethic part contains two types of modal operators for absolute and historical necessity and possibility. According to ‘boulesic logic’ (the logic of the will), ‘willing’ (‘consenting’, ‘rejecting’, ‘indifference’ and ‘non-indifference’) is a kind of modal operator. Doxastic logic is the logic of beliefs; it treats ‘believing’ (and ‘conceiving’) as a kind of modal operator. I will explore some possible relationships between these different parts, and investigate some principles that include more than one type of logical expression. I will show that every tableau system in the paper is sound and complete with respect to its semantics. Finally, I consider an example of a valid argument and an example of an invalid sentence. I show how one can use semantic tableaux to establish validity and invalidity and read off countermodels. These examples illustrate the philosophical usefulness of the systems that are introduced in this paper. (shrink)

This paper investigates structural properties of monotone function classes within the framework of three-valued logic (3VL), aiming to characterize dependencies and constraints that ensure structural finiteness and order-preserving properties. This research delves into characteristics of structurally finite classes of order-preserving 3VL map. Monotonicity plays a critical role in understanding functional behaviour, which is essential for structuring closed logical operations within $ P_{k} $. We define $ F $ as a closed class in $ P_{k} $, consisting only of mappings (...) that comply with specified operations and are strictly confined to $ P_{k} $. The notation $ F(n) $ represents the subset of mappings in $ F $ dependent on $ n $ variables, highlighting the limited scope of inputs and their respective outputs. Further analysis through $ CR(F) $ facilitates the identification of precursor subclasses within $ F $, which have not yet achieved closure under all necessary operations—a pivotal step in constructing intermediate mapping classes. Within the framework of 3VL, the study examines order-preserving maps $ f_{D}, f_{K}, f_{M^{(2)}}, f_{DM^{(2)}}, f_{KM^{(2)}} $, deliberately excluding the sets $ D, K, M^{(2)} $, where $ DM^{(2)} $ is defined as $ D \cap M^{(2)} $ and $ KM^{(2)} $ as $ K \cap M^{(2)} $. The lattice framework in $ P_{k}(1) $ for $ k = 3 $ systematically organizes these mapping classes based on their completeness properties, with particular emphasis on classes such as $ M $, which is characterized as a comprehensive set governed by the operations of maximum and minimum. Our theorems establish structural finiteness for classes of unary order-preserving maps, emphasizing their two-variable dependency in class construction. This study extends existing findings on single-variable monotonic functions within 3VL by integrating criteria of linear order. Key results include the classification of mapping classes $ F \subseteq M $ containing $ M^{(1)}_{3} $, categorized into distinct groups: $ M^{(1)}_{3}, KM^{(2)}, DM^{(2)}, M^{(2)}, K, D, M $. Inclusion relations are visualized diagrammatically, showing the hierarchical structure of these monotone classes, ultimately validating the structural finiteness of classes incorporating all unary order-preserving maps within the broader context of 3VL. (shrink)

The article deals with finding finite total equivalence systems for formulas based on an arbitrary closed class of functions of several variables defined on the set {0, 1, 2} and taking values in the set {0,1} with the property that the restrictions of its functions to the set {0, 1} constitutes a closed class of Boolean functions. We consider all classes whose restriction closure is either the set of all functions of two-valued logic or the set T a of functions (...) preserving \. In each of these cases, we find a finite total equivalence system, construct a canonical type for formulas, and present a complete algorithm for determining whether any two formulas are equivalent. (shrink)

This recent addition to the Studies in Logic series is a systematic treatise on the set-theoretic, or semantic, approach to mathematical logic and axiomatic method. The basic notions for the discussion are those of different kinds of languages, their realizations, and the models of a formula. The book begins with a preliminary "chapter 0," giving some general theorems about classes of functions defined by finite schemas. These results are directly applicable to the language of truth-functional propositional logic, and such application (...) is accomplished in detail in chapter 1, in which interpolation, finiteness and compactness theorems are proved for propositional calculus. Chapters 2 and 3 deal with the predicate calculus without and with identity, respectively. More advanced topics dealt with in subsequent chapters include elimination of quantifiers. Certain algebraic structures such as real closed fields and some Boolean rings are given in the form of axiomatic systems in which every formula is equivalent to a quantifier-free formula. This leads to completeness. Also covered are type theory and alternate methods for developing predicate logic, the theory of definability, and the theory of principal models and infinite formulas. Appendices deal with some additional matters of philosophic interest, including a detailed discussion of set-theoretic vs. combinatorial foundations of mathematics. The book lacks an index and a bibliography, but these are not serious defects. This is a highly rewarding work.—H. P. K. (shrink)

The paper is dedicated to the 80th birthday of the outstanding Russian logician A.V. Kuznetsov. It is addressing a history of the ideas and research conducted by him in non-classical and intermediate logics.