One well known problem regarding quantifiers, in particular the 1st order 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 functor-function 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)

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)

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 1st-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)

Second-order quantifier elimination in the context of classical logic emerged as a powerful technique in many applications, including the correspondence theory, relational databases, deductive and knowledge databases, knowledge representation, commonsense reasoning and approximate reasoning. In the current paper we first generalize the result of Nonnengart and Szałas [17] by allowing second-order variables to appear within higher-order contexts. Then we focus on a semantical analysis of conditionals, using the introduced technique and Gabbay’s semantics provided in [10] and substantially (...) using a third-order accessibility relation. The analysis is done via finding correspondences between axioms involving conditionals and properties of the underlying third-order relation. (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)

In this paper, I present what I call the symmetry conception of God within 1st order, extensional, non-well-founded set theory. The symmetry conception comes in two versions. According to the first, God is that unique being that is universally symmetrical with respect to set membership. According to the second, God is the universally symmetrical set of all sets that are universally symmetrical with respect to set membership. I present a number of theorems, most importantly that any universally symmetrical set (...) is identical to its essence, that show that the two symmetry conceptions intersect with some dominant theological conceptions of God. The theorems also show that both of the symmetry conceptions of God entail that God has a fractal like structure. (shrink)

The purpose of this paper is to communicate - as a proposal - a general method of assigning a 'truthmaker' to any 1st order sentence in each of its models. The respective construct is derived from the standard model theoretic (recursive) satisfaction definition for 1st order languages and is a conservative extension thereof. The heuristics of the proposal (which has been somewhat idiosyncratic from the current point of view) and some more technical detail of the construction may be (...) found in my article on part I of Spinoza's 'ethica, ordine geometrico demonstrata', which is the context within which I elaborated the assignment. But this context need not be repeated here, the presentation of the truthmaker assignment will be comprehensible to anybody with solid basic knowledge in 1st order model theory, anything used is standard and no advanced techniques are required. (shrink)

My original reaction to Yosh’s paper was to grumble. It seemed to me to contain a number of terminological infelicities, unpersuasive arguments, and counterintuitive implications. And while I think that some of my superficial complaints are worth pointing out (and I can’t help myself), a commentary consisting only of grumbling would be neither interesting nor helpful. Paul Viminitz would describe such a commentary as “unseemly”. And so I revisited Yosh’s paper with a more sympathetic eye. My second reaction was to (...) suppose that what Yosh had actually done was to provide a Russellian analysis of sentences containing descriptions but in a 2nd order logical system – a system in which quantification over properties is permitted and in which 1st order quantifiers are reinterpreted as 2nd order properties. This would be an interesting albeit modest contribution to the description literature. But as I reread Yosh’s paper in preparation for writing this commentary, I realized that given the account of individual kinds that was being developed this wasn’t right. Individual kinds are not properties at all, they are a new sort of individual – teams of one. Yosh’s proposal is hardly modest at all. So, in these comments, I am going to focus on the notion of an individual kind and whether or not we ought to endorse such entities in our semantic theorizing. But first, some preliminary grumbling – I really can’t help myself. (shrink)

\ is a 7000 line Prolog parser/theorem-prover for logical categorial grammar. In such logical categorial grammar syntax is universal and grammar is reduced to logic: an expression is grammatical if and only if an associated logical statement is a theorem of a fixed calculus. Since the syntactic component is invariant, being the logic of the calculus, logical categorial grammar is purely lexicalist and a particular language model is defined by just a lexical dictionary. The foundational logic of continuity was established (...) by Lambek while a corresponding extension including also logic of discontinuity was established by Morrill and Valentín :167–192, 2010). \ implements a logic including as primitive connectives the continuous and discontinuous connectives of the displacement calculus, additives, 1st order quantifiers, normal modalities, bracket modalities, and universal and existential subexponentials. In this paper we review the rules of inference for these primitive connectives and their linguistic applications, and we survey the principles of Andreoli’s focusing, and of a generalisation of van Benthem’s count-invariance, on the basis of which \ is implemented. (shrink)

While second-order quantifiers have long been known to admit nonstandard, or interpretations, first-order quantifiers (when properly viewed as predicates of predicates) also allow a kind of interpretation that does not presuppose the full power-set of that interpretationgeneral” interpretations for (unary) first-order quantifiers in a general setting, emphasizing the effects of imposing various further constraints that the interpretation is to satisfy.

Special quantifiers are quantifiers like 'something', 'everything', and 'several things'. They are special both semantically and syntactically and play quite an important role in philosophy, in discussions of ontological commitment to abstract objects, of higher-order metaphysics, and of the apparent need for propositions. This paper will review and discuss in detail the syntactic and semantic peculiarities of special quantifiers and show that they are incompatible with substitutional and higher-order analyses that have recently been proposed. It (...) instead defends and develops in formal detail a semantic analysis of special quantifiers as nominalizing quantifiers. On this analysis, special quantifiers involve both singular objectual quantification and implicit on non-singular (higher-order, plural, or mass) quantification. The analysis rests on a range of recent insights and proposals in generative syntactic theory, in particular the recognition of '–thing' as a light noun and a potential classifier as well as recent views of the decomposition of attitudinal and locutionary verbs in syntax. (shrink)

Novel varieties of interplay between humans, robots and software agents are on the rise. Computer-based artefacts are no longer mere tools but have become interaction partners. Distributed problem solving and social agency may be modelled by social computing systems based on multi-agent systems. MAS and agent-based modelling approaches focus on the simulation of complex interactions and relationships of human and/or non-human agents. MAS may be deployed both in virtual environments and cyber-physical systems. With regard to their impact on the physical (...) environment, such systems possess a virtual actuality in a testbed. They have a real actuality when they are employed in real time in order to govern processes in the natural world. Constellations of inter-agency and distributed agency materialize. This paper presents a multidimensional, gradual classification framework for individual and joint agency. Activity level, adaptivity, interaction and personification of others are essential dimensions. The framework allows constellations of distributed and collective agency in socio-technical systems to be analysed in detail. Scenarios where solely humans act can be compared to testbed simulations based on this classification scheme. (shrink)

Nondeterministic exponential time complexity bounds are established for recognizing true propositional formulas with partially ordered quantifiers on propositional variables.

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)

It is the purpose of this paper to address ethical issues concerning the development and application of Assistive Technology at Workplaces (ATW). We shall give a concrete technical concept how such technology might be constructed and propose eight technical functions it should adopt in order to serve its purpose. Then, we discuss the normative questions why one should use ATW, and by what means. We argue that ATW is good to the extent that it ensures social inclusion and consider (...) four normative domains in which its worth might consists in. In addition, we insist that ATW must satisfy two requirements of good workplaces, which we specify as (a) an exploitation restraint and (b) a duty of care. (shrink)

We refine the constructions of Ferrante-Rackoff and Solovay on iterated definitions in first-order logic and their expressibility with polynomial size formulas. These constructions introduce additional quantifiers; however, we show that these extra quantifiers range over only finite sets and can be eliminated. We prove optimal upper and lower bounds on the quantifier complexity of polynomial size formulas obtained from the iterated definitions. In the quantifier-free case and in the case of purely existential or universal quantifiers, we (...) show that Ω quantifiers are necessary and sufficient. The last lower bounds are obtained with the aid of the Yao-Håstad switching lemma. (shrink)

Let H be a proof system for quantified propositional calculus (QPC). We define the Σqj-witnessing problem for H to be: given a prenex Σqj-formula A, an H-proof of A, and a truth assignment to the free variables in A, find a witness for the outermost existential quantifiers in A. We point out that the Σq1-witnessing problems for the systems G*1and G1 are complete for polynomial time and PLS (polynomial local search), respectively. We introduce and study the systems G*0 and (...) G0, in which cuts are restricted to quantifier-free formulas, and prove that the Σqj-witnessing problem for each is complete for NC1. Our proof involves proving a polynomial time version of Gentzen’s midsequent theorem for G*0 and proving that G0-proofs are TC0-recognizable. We also introduce QPC systems for TC0 and prove witnessing theorems for them. We introduce a finitely axiomatizable second-order system VNC1 of bounded arithmetic which we prove isomorphic to Arai’s first order theory AID + Σb0-CA for uniform NC1. We describe simple translations of VNC1 proofs of all bounded theorems to polynomial size families of G*0 proofs. From this and the above theorem we get alternative proofs of the NC1 witnessing theorems for VNC1 and AID. (shrink)

Let ℜ = (R, + R , ...) be the ordered field of real numbers. It will be shown that the L(Q n 1 ∣ n ≥ 1)-theory of ℜ is decidable, where Q n 1 denotes the Malitz quantifier of order n in the ℵ 1 -interpretation.

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)

We study first-order concatenation theory with bounded quantifiers. We give axiomatizations with interesting properties, and we prove some normal-form results. Finally, we prove a number of decidability and undecidability results.

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)

Using a variation of the rainbow construction and various pebble and colouring games, we prove that RRA, the class of all representable relation algebras, cannot be axiomatised by any first-order relation algebra theory of bounded quantifier depth. We also prove that the class At(RRA) of atom structures of representable, atomic relation algebras cannot be defined by any set of sentences in the language of RA atom structures that uses only a finite number of variables.

Connections between partially ordered connectives and Henkin quantifiers are considered. It is proved that the logic with all partially ordered connectives and the logic with all Henkin quantifiers coincide. This implies that the hierarchy of partially ordered connectives is strongly hierarchical and gives several nondefinability results between some of them. It is also deduced that each Henkin quantifier can be defined by a quantifier of the form equation imagewhat is a strengthening of the Walkoe result. MSC: 03C80.

Van Lambalgen (1990) proposed a translation from a language containing a generalized quantifierQ into a first-order language enriched with a family of predicatesR i, for every arityi (or an infinitary predicateR) which takesQxg(x, y1,..., yn) to x(R(x, y1,..., y1) (x,y1,...,yn)) (y 1,...,yn are precisely the free variables ofQx). The logic ofQ (without ordinary quantifiers) corresponds therefore to the fragment of first-order logic which contains only specially restricted quantification. We prove that it is decidable using the method of (...) analytic tableaux. Related results were obtained by Andréka and Németi (1994) using the methods of algebraic logic. (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)

We examine second order intuitionistic propositional logic, IPC². Let $F_\exists $ be the set of formulas with no universal quantification. We prove Glivenko's theorem for formulas in $F_\exists $ that is, for φ € $F_\exists $ φ is a classical tautology if and only if ¬¬φ is a tautology of IPC². We show that for each sentence φ € $F_\exists $ (without free variables), φ is a classical tautology if and only if φ is an intuitionistic tautology. As a (...) corollary we obtain a semantic argument that the quantifier V is not definable in IPC² from ⊥, V, ^, →. (shrink)

We study definability of second-order generalized quantifiers. We show that the question whether a second-order generalized quantifier $\sQ_1$ is definable in terms of another quantifier $\sQ_2$, the base logic being monadic second-order logic, reduces to the question if a quantifier $\sQ^{\star}_1$ is definable in $\FO(\sQ^{\star}_2,<,+,\times)$ for certain first-order quantifiers $\sQ^{\star}_1$ and $\sQ^{\star}_2$. We use our characterization to show new definability and non-definability results for second-order generalized quantifiers. In particular, we show that the (...) monadic second-order majority quantifier $\most^1$ is not definable in second-order logic. (shrink)

This paper obtains lower and upper bounds for the number of alternations of bounded quantifiers needed to express all formulas in certain ordered Abelian groups admitting elimination of unbounded quantifiers. The paper also establishes model-theoretic tests for equivalence to a formula with a given number of alternations of bounded quantifiers.

We here examine the expressive power of first order logic with generalized quantifiers over finite ordered structures. In particular, we address the following problem: Given a family Q of generalized quantifiers expressing a complexity class C, what is the expressive power of first order logic FO(Q) extended by the quantifiers in Q? From previously studied examples, one would expect that FO(Q) captures L C , i.e., logarithmic space relativized to an oracle in C. We show (...) that this is not always true. However, after studying the problem from a general point of view, we derive sufficient conditions on C such that FO(Q) captures L C . These conditions are fulfilled by a large number of relevant complexity classes, in particular, for example, by NP. As an application of this result, it follows that first order logic extended by Henkin quantifiers captures L NP . This answers a question raised by Blass and Gurevich [Ann. Pure Appl. Logic, vol. 32, 1986]. Furthermore we show that for many families Q of generalized quantifiers (including the family of Henkin quantifiers), each FO(Q)-formula can be replaced by an equivalent FO(Q)-formula with only two occurrences of generalized quantifiers. This generalizes and extends an earlier normal-form result by I. A. Stewart [Fundamenta Inform. vol. 18, 1993]. (shrink)

We study second order generalized quantifiers on finite structures. One starting point of this research has been the notion of definability of Lindström quantifiers. We formulate an analogous notion for second order generalized quantifiers and study definability of second order generalized quantifiers in terms of Lindström quantifiers.

In [2], Singer proved that the theory of ordered differential fields has a model completion, i.e, the theory of closed ordered differential fields, CODF. As a result, CODF admits elimination of quantifiers. In this paper we give an algorithm to eliminate the quantifiers of CODF-formulas.

We investigate the extension of monadic second-order logic of order with cardinality quantifiers "there exists uncountably many sets such that... " and "there exists continuum many sets such that... ". We prove that over the class of countable linear orders the two quantifiers are equivalent and can be effectively and uniformly eliminated. Weaker or partial elimination results are obtained for certain wider classes of chains. In particular, we show that over the class of ordinals the uncountability (...) quantifier can be effectively and uniformly eliminated. Our argument makes use of Shelah's composition method and Ramsey-like theorem for dense linear orders. (shrink)