A note on parallel and alternating time

A long standing open question in complexity theory over the reals is the relationship between parallel time and quantifier alternation. It is known that alternating digital quantifiers is weaker than parallel time, which in turn is weaker than alternating unrestricted (real) quantifiers. In this note we consider some complexity classes defined through alternation of mixed digital and unrestricted quantifiers in different patterns. We show that the class of sets decided in parallel polynomial time is sandwiched between two such classes for different patterns.     

Demiquantifiers on $$\ell $$-groups

In this paper we introduce two kinds of unary operations on abelian \(\ell \)-groups with a positive distinguished element u. One of them, called demiquantifier of type I, behaves like an existential quantifier (in the sense of Cimadamore and Varela) in the negative cone, and like a universal quantifier in the positive cone. The other kind of unary operation we introduce, called demiquantifier of type II, satisfies analogous properties to demiquantifiers of type I via a translation of the negative cone, by means of the element u. These unary operations are interdefinable with the usual existential quantifiers, provided the distinguished element u is a strong unit. Moreover, if G is an abelian \(\ell \)-group, then the restriction of a demiquantifier of type II to the MV-algebra \(\Gamma (G,u)\) yields a different type of quantifier, where \(\Gamma \) is Mundici’s functor. These quantifiers are interdefinable with the usual existential quantifiers on MV-algebras given by Rutledge, provided that the involution of the corresponding MV-algebras have a fixed point.     

On Spacetime, Points, and Bare Particulars

In his paper Bare Particulars, T. Sider claims that one of the most plausible candidates for bare particulars are spacetime points. The aim of this paper is to shed light on Sider’s reasoning and its consequences. There are three concepts of spacetime points that allow their identification with bare particulars. One of them, Moderate structural realism, is considered to be the most adequate due its appropriate approach to spacetime metric and moderate view of mereological simples. However, it pushes the Substratum theory to dismiss primitive thisness as the only identity condition for bare particulars, but the paper argues that such elimination is a legitimate step.     

On vectorizations of unary generalized quantifiers

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 ).     

Modal Tense and the Absolutely Unrestricted Quantifier

In this paper, I examine Takashi Yagisawa’s response to van Inwagen’s ontic objection against David Lewis. Van Inwagen criticizes Lewis’s commitment to the absolutely unrestricted sense of ‘there is,’ and Yagisawa claims that by adopting modal tenses he avoids commitment to absolutely unrestricted quantification. I argue that Yagisawa faces a problem parallel to the one Lewis faces. Although Yagisawa officially rejects the absolutely unrestricted sense of a quantifying expression, he is still committed to the absolutely unrestricted sense of ‘is _a real.’     

Stationary logic of ordinals

The L(aa)-theory of ordinals—Th_aa(On)—is studied. It is shown that Th_aa(On) is primitive recursive. In a suitable language it is possible to eliminate quantifiers. L(aa)-equivalence invariants are given. Both the complete L(aa)-theories of ordinals and the complete extensions of Th_aa(On) are characterized. An ordering is L(aa)-inductive if every L(aa)-definable subset (with suitable parameters) has a least element. The models of Th_aa(On) are the L(aa)-inductive orderings. A variant of the back and forth method is introduced in order toprove primitive recursive decidability and elimination of quantifier results.     

The quantifier complexity of polynomial‐size iterated definitions in first‐order logic

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 Ω(n /log n) quantifiers are necessary and sufficient. The last lower bounds are obtained with the aid of the Yao‐Håstad switching lemma (© 2010 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

An Alternative Definition of Quantifiers on Four-Valued Łukasiewicz Algebras

An alternative notion of an existential quantifier on four-valued ?ukasiewicz algebras is introduced. The class of four-valued ?ukasiewicz algebras endowed with this existential quantifier determines a variety which is denoted by \(\mathbb {M}_{\frac{2}{3}}\mathbb {L}_4\). It is shown that the alternative existential quantifier is interdefinable with the standard existential quantifier on a four-valued ?ukasiewicz algebra. Some connections between the new existential quantifier and the existential quantifiers defined on bounded distributive lattices and Boolean algebras are given. Finally, a completeness theorem for the monadic four-valued ?ukasiewicz predicate calculus corresponding to the dual of the alternative existential quantifier is proven.     

Vectorization hierarchies of some graph quantifiers

We give a sufficient condition for the inexpressibility of the k-th extended vectorization of a generalized quantifier in , the extension of first-order logic by all k-ary quantifiers. The condition is based on a model construction which, given two -equivalent models with certain additional structure, yields a pair of -equivalent models. We also consider some applications of this condition to quantifiers that correspond to graph properties, such as connectivity and planarity. Received: 15 October 1996     

Can I be an Instantaneous Stage and yet Persist Through Time?

An alternative to the standard endurance/perdurance accounts of persistence has recently been developed: the stage theory (Sider, T. Four-Dimensionalism: an Ontology of Persistence and Time. Oxford: Oxford University Press, 2001; Hawley, K. How Things Persist. Oxford: Oxford University Press, 2001). According to this theory, a persisting object is identical with an instantaneous stage (temporal part). On the basis of Leibniz’s Law, I argue that stage theorists either have to deny the alleged identity (i.e., give up their central thesis) or hold that stages are both instantaneous and continuants. I subsequently show that, although stage theory is flexible enough to accommodate the latter claim, the cost for accommodating it is an excessive proliferation of persistence concepts.     

素数阶群理论的量词消去算法及其上界

在以前的一些工作中,作者已经证明语言(?)={+,0,e)上素数阶群的理论T有量词消去性质并研究了它的判定问题的复杂性.本文在此基础上将利用T的判定问题的复杂性结果给出理论T的量词消去的一个算法,同时给出该算法的复杂性上界.     

Linguistic quantifiers based on Choquet integrals

The introduction of linguistic quantifiers has provided an important tool to model a large number of issues in intelligent systems. Ying [M.S. Ying, Linguistic quantifiers modeled by Sugeno integrals, Artificial Intelligence 170 (2006) 581–606] recently introduced a new framework for modeling quantifiers in natural languages in which each linguistic quantifier is represented by a family of fuzzy measures, and the truth value of a quantified proposition is evaluated by using Sugeno’s integral. Representing linguistic quantifiers by fuzzy measures, this paper evaluates linguistic quantified propositions by the Choquet integral. Some elegant logical properties of linguistic quantifiers are derived within this approach, including a prenex normal form theorem stronger than that in Ying’s model. In addition, our Choquet integral approach to the evaluation of quantified statements is compared with others, in particular with Ying’s Sugeno integral approach.     

Bounding quantification in parametric expansions of Presburger arithmetic

Generalizing Cooper’s method of quantifier elimination for Presburger arithmetic, we give a new proof that all parametric Presburger families \(\{S_t : t \in \mathbb {N}\}\) [as defined by Woods (Electron J Comb 21:P21, 2014)] are definable by formulas with polynomially bounded quantifiers in an expanded language with predicates for divisibility by f(t) for every polynomial \(f \in \mathbb {Z}[t]\). In fact, this quantifier bounding method works more generally in expansions of Presburger arithmetic by multiplication by scalars \(\{\alpha (t): \alpha \in R, t \in X\}\) where R is any ring of functions from X into \(\mathbb {Z}\).     

Existence and Strong Uncountability

On the standard view for something to exist is for one thing to exist: in slogan form, to be is to be countable (cf. van Inwagen 2009). E.J. Lowe (2009, 2003, 1998) argues something can exist without being countable as one, however. His primary example is homogenous “stuff,” i.e., qualitatively uniform and infinitely divisible matter. Lacking nonarbitrary boundaries and being everywhere the same, homogenous stuff lacks a principle of individuation that would yield countably distinct constituents. So, for Lowe, homogenous stuff is strongly uncountable. Olson (2011) rejects Lowe’s view and defends the orthodox connection between existence and number. He argues that if there is any stuff, there is a (determinate) number of portions of stuff. Sider (2011, 2001) also rejects a stuff ontology, claiming it is incompatible with his preferred view that the familiar quantifiers of predicate logic carve at nature’s joints. Against these arguments, I defend the uncountability of stuff and the possibility of existence without countability. If to be is to be countable, more is needed than the arguments that Olson and Sider provide.     

Introduction: Vagueness and Ontology

The article introduces a special issue of the journal Metaphysica on vagueness and ontology. The conventional view has it that all vagueness is semantic or representational. Russell, Dummett, Evans and Lewis, inter alia, have argued that the notion of “ontic” or “metaphysical” vagueness is not even intelligible. In recent years, a growing minority of philosophers have tried to make sense of the notion and have spelled it out in various ways. The article gives an overview and relates the idea of ontic vagueness to the unquestioned phenomenon of fuzzy spatiotemporal boundaries and to the associated “problem of the many”. It briefly discusses the question of whether ontic vagueness can be spelled out in terms of “vague identity”, emphasizes the often neglected role of the difference between sortal and non-sortal ontologies and suggests a deflationary answer to the ill-conceived question of whether the “ultimate source” of vagueness lies either in language or in the world.     

Beth’s theorem in cardinality logics

We prove that the Beth definability theorem fails for a comprehensive class of first-order logics with cardinality quantifiers. In particular, we give a counterexample to Beth’s theorem forL(Q), which is finitary first-order logic (with identity) augmented with the quantifier “there exists uncountably many”. This research was partially supported by NSF GP29254.     

Equilibrium semantics of languages of imperfect information

In this paper, we introduce a new approach to independent quantifiers, as originally introduced in Informational independence as a semantic phenomenon by Hintikka and Sandu (1989) [9] under the header of independence-friendly (IF) languages. Unlike other approaches, which rely heavily on compositional methods, we shall analyze independent quantifiers via equilibriums in strategic games. In this approach, coined equilibrium semantics, the value of an IF sentence on a particular structure is determined by the expected utility of the existential player in any of the game’s equilibriums. This approach was suggested in Henkin quantifiers and complete problems by Blass and Gurevich (1986) [2] but has not been taken up before. We prove that each rational number can be realized by an IF sentence. We also give a lower and upper bound on the expressive power of IF logic under equilibrium semantics.     

Quantifier elimination for the theory of algebraically closed valued fields with analytic structure

The theory of algebraically closed non‐Archimedean valued fields is proved to eliminate quantifiers in an analytic language similar to the one used by Cluckers, Lipshitz, and Robinson. The proof makes use of a uniform parameterized normalization theorem which is also proved in this paper. This theorem also has other consequences in the geometry of definable sets. The method of proving quantifier elimination in this paper for an analytic language does not require the algebraic quantifier elimination theorem of Weispfenning, unlike the customary method of proof used in similar earlier analytic quantifier elimination theorems. (© 2007 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Hierarchies of Partially Ordered Connectives and Quantifiers

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 what is a strengthening of the Walkoe result. MSC: 03C80.