We shall prove quantifier elimination theorems for neocompact formulas, which define neocompact sets and are built from atomic formulas using finite disjunctions, infinite conjunctions, existential quantifiers, and bounded universal quantifiers. The neocompact sets were first introduced to provide an easy alternative to nonstandard methods of proving existence theorems in probability theory, where they behave like compact sets. The quantifier elimination theorems in this paper can be applied in a general setting to show that the family of (...) neocompact sets is countably compact. To provide the necessary setting we introduce the notion of a law structure. This notion was motivated by the probability law of a random variable. However, in this paper we discuss a variety of model theoretic examples of the notion in the light of our quantifier elimination results. (shrink)

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

From classical, Fraïissé-homogeneous, ($\leq \omega$)-categorical theories over finite relational languages, we construct intuitionistic theories that are complete, prove negations of classical tautologies, and admit quantifier elimination. We also determine the intuitionistic universal fragments of these theories.

This work presents a model-theoretic approach to the study of first-order theories of classes of BL-chains. Among other facts, we present several classes of BL-algebras, generating the whole variety of BL-algebras, whose first-order theory has quantifier elimination. Model-completeness and decision problems are also investigated. Then we investigate classes of BL-algebras having (or not having) the amalgamation property or the joint embedding property and we relate the above properties to the existence of ultrahomogeneous models.

We identify the locally finite graphs that are quantifier-eliminable and their first order theories in the signature of distance predicates. © 2011 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim.

We shall prove quantifier elimination theorems for neocompact formulas, which define neocompact sets and are built from atomic formulas using finite disjunctions, infinite conjunctions, existential quantifiers, and bounded universal quantifiers. The neocompact sets were first introduced to provide an easy alternative to nonstandard methods of proving existence theorems in probability theory, where they behave like compact sets. The quantifier elimination theorems in this paper can be applied in a general setting to show that the family of (...) neocompact sets is countably compact. To provide the necessary setting we introduce the notion of a law structure. This notion was motivated by the probability law of a random variable. However, in this paper we discuss a variety of model theoretic examples of the notion in the light of our quantifier elimination results. (shrink)

We consider valued fields with a distinguished isometry or contractive derivation as valued modules over the Ore ring of difference operators. Under certain assumptions on the residue field, we prove quantifier elimination first in the pure module language, then in that language augmented with a chain of additive subgroups, and finally in a two-sorted language with a valuation map. We apply quantifier elimination to prove that these structures do not have the independence property.

We introduce new first-order languages for the elementary n-dimensional geometry and elementary n-dimensional affine geometry , based on extending equation image and equation image, respectively, with new function symbols. Here, β stands for the betweenness relation and ≡ for the congruence relation. We show that the associated theories admit effective quantifier elimination.

We study conditions for structures based on Banach spaces having the property that each set definable by neocompact formula is equivalent to the countable intersection of sets definable by quantifier-free formulas. We show that this property is invariant with respect to different nonstandard hull constructions and it is the same as Henson's Quantifier Elimination in sufficiently saturated nonstandard hulls of internal Banach spaces.

Van den Dries, L. and J. Holly, Quantifier elimination for modules with scalar variables, Annals of Pure and Applied Logic 57 161–179. We consider modules as two-sorted structures with scalar variables ranging over the ring. We show that each formula in which all scalar variables are free is equivalent to a formula of a very simple form, uniformly and effectively for all torsion-free modules over gcd domains . For the case of Presburger arithmetic with scalar variables the result (...) takes a still simpler form, and we derive in this way the polynomial-time decidability of the sets defined by such formulas. (shrink)

Genera connections between quantifier elimination and decidability for first order theories are studied and exemplified.

In 1985, van den Dries showed that the theory of the reals with a predicate for the integer powers of two admits quantifier elimination in an expanded language, and is hence decidable. He gave a model-theoretical argument, which provides no apparent bounds on the complexity of a decision procedure. We provide a syntactical argument that yields a procedure that is primitive recursive, although not elementary.

This work presents a model-theoretic approach to the study of the amalgamation property for varieties of semilinear commutative residuated lattices. It is well-known that if a first-order theory T enjoys quantifier elimination in some language L, the class of models of the set of its universal consequences \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\rm T_\forall}$$\end{document} has the amalgamation property. Let \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${{\rm Th}(\mathbb{K})}$$\end{document} be the theory of an (...) elementary subclass \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathbb{K}}$$\end{document} of the linearly ordered members of a variety \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathbb{V}}$$\end{document} of semilinear commutative residuated lattices. We show that whenever \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${{\rm Th}(\mathbb{K})}$$\end{document} has elimination of quantifiers, and every linearly ordered structure in \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathbb{V}}$$\end{document} is a model of \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${{\rm Th}_\forall(\mathbb{K})}$$\end{document}, then \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathbb{V}}$$\end{document} has the amalgamation property. We exploit this fact to provide a purely model-theoretic proof of amalgamation for particular varieties of semilinear commutative residuated lattices. (shrink)

We consider the theoryT IT of infinite terms. The axioms for the theoryT IT are analogous to the Mal'cev's axioms for the theoryT IT of finite terms whose models are the locally free algebras. Recently Maher [Ma] has proved that the theoryT IT in a finite non singular signature plus the Domain Closure Axiom is complete. We give a description of all the complete extension ofT IT from which an effective decision procedure forT IT is obtained. Our approach considers formulas (...) built up with syntactic terms containing pointers. Using such a technique, the analysis of the theoryT IT can be carried out in analogy with Mal'cev's analysis ofT FT. Our results follow from an effective quantifier elimination procedure for formulas with pointers. (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)

The Joint Non-Trivialization Theorem, two Definability Theorems and the generalized Quantifier Elimination Theorem are proved for J 3-theories. These theories are three-valued with more than one distinguished truth-value, reflect certain aspects of model type logics and can. be paraconsistent. J 3-theories were introduced in the author's doctoral dissertation.

Work of Eagle, Farah, Goldbring, Kirchberg, and Vignati shows that the only separable C*‐algebras that admit quantifier elimination in continuous logic are,,, and the continuous functions on the Cantor set. We show that, among finite dimensional C*‐algebras, quantifier elimination does hold if the language is expanded to include two new predicate symbols: One for minimal projections, and one for pairs of unitarily conjugate elements. Both of these predicates are definable, but not quantifier‐free definable, in the (...) usual language of C*‐algebras. We also show that adding just the predicate for minimal projections is sufficient in the case of full matrix algebras, but that in general both new predicate symbols are required. (shrink)

We give an answer to the question as to whether quantifier elimination is possible in some infinite algebraic extensions of Qp (‘infinite p-adic fields’) using a natural language extension. The present paper deals with those infinite p-adic fields which admit only tamely ramified algebraic extensions (so-called tame fields). In the case of tame fields whose residue fields satisfy Kaplansky’s condition of having no extension of p-divisible degree quantifier elimination is possible when the language of valued fields (...) is extended by the power predicates Pn introduced by Macintyre and, for the residue field, further predicates and constants. For tame infinite p-adic fields with algebraically closed residue fields an extension by Pn predicates is sufficient. (shrink)

We revisit the theory of amalgamation classes but we do not insist on staying within elementary classes.

In this paper we investigate the connections between quantifier elimination, decidability and Uniform Craig Interpolation in Δ-core fuzzy logics added with propositional quantifiers. As a consequence, we are able to prove that several propositional fuzzy logics have a conservative extension which is a Δ-core fuzzy logic and has Uniform Craig Interpolation.

In the paper we present a technique for eliminating quantifiers of arbitrary order, in particular of first-order. Such a uniform treatment of the elimination problem has been problematic up to now, since techniques for eliminating first-order quantifiers do not scale up to higher-order contexts and those for eliminating higher-order quantifiers are usually based on a form of monotonicity w.r.t implication (set inclusion) and are not applicable to the first-order case. We make a shift to arbitrary relations “ordering” the underlying (...) universe. This allows us to incorporate background theories into higher-order quantifier elimination methods which, up to now, has not been achieved. The technique we propose subsumes many other results, including the Ackermann's lemma and various forms of fixpoint approaches when the “ordering” relations are interpreted as implication and reveals the common principle behind these approaches. (shrink)

A semantic embedding of quantified conditional logic in classical higher-order logic is utilized for reducing cut-elimination in the former logic to existing results for the latter logic. The presented embedding approach is adaptable to a wide range of other logics, for many of which cut-elimination is still open. However, special attention has to be payed to cut-simulation, which may render cut-elimination as a pointless criterion.

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 consider two-sorted theories of vector spaces and prove a criterion for the assertion that such a theory allows elimination of quantifiers over vector variables.

Elimination of quantifiers is shown to fail dramatically for a group of well‐known mathematical theories (classically enjoying the property) against a wide range of relevant logical backgrounds. Furthermore, it is suggested that only by moving to more extensional underlying logics can we get the property back.

Extending previous results from work on the complexity of cut elimination for the sequent calculus LK, we discuss the role of quantifier alternations and develop a measure to describe the complexity of cut elimination in terms of quantifier alternations in cut formulas and contractions on such formulas.

This paper extends theorems of Belegradek about poly-regular groups of finite rank to certain poly-regular groups of infinite rank. A model-theoretic property aiding these investigations is the elimination of unbounded quantifiers, and the paper establishes both a general model-theoretic test for this property and results about bounded quantifiers in the special context of ordered Abelian groups.

Mathematical theory of voting and social choice has attracted much attention. In the general setting one can view social choice as a method of aggregating individual, often conflicting preferences and making a choice that is the best compromise. How preferences are expressed and what is the “best compromise” varies and heavily depends on a particular situation. The method we propose in this paper depends on expressing individual preferences of voters and specifying properties of the resulting ranking by means of first-order (...) formulas. Then, as a technical tool, we use methods of second-order quantifier elimination to analyze and compute results of voting. We show how to specify voting, how to compute resulting rankings and how to verify voting protocols. (shrink)

We obtain an almost everywhere quantifier elimination for (the noncritical fragment of) the logic with probability quantifiers, introduced by the first author in [10]. This logic has quantifiers like $\exists ^{ \ge 3/4} y$ which says that "for at least 3/4 of all y". These results improve upon the 0-1 law for a fragment of this logic obtained by Knyazev [11]. Our improvements are: 1. We deal with the quantifier $\exists ^{ \ge r} y$ , where y (...) is a tuple of variables. 2. We remove the closedness restriction, which requires that the variables in y occur in all atomic subformulas of the quantifier scope. 3. Instead of the unbiased measure where each model with universe n has the same probability, we work with any measure generated by independent atomic probabilities pR for each predicate symbol R. 4. We extend the results to parametric classes of finite models (for example, the classes of bipartite graphs, undirected graphs, and oriented graphs). 5. We extend the results to a natural (noncritical) fragment of the infinitary logic with probability quantifiers. 6. We allow each pR , as well as each r in the probability quantifier $(\exists ^{ \ge r} y)$ , to depend on the size of the universe. (shrink)

One of the central logical ideas in Wittgenstein’sTractatus logico-philosophicusis the elimination of the identity sign in favor of the so-called “exclusive interpretation” of names and quantifiers requiring different names to refer to different objects and (roughly) different variables to take different values. In this paper, we examine a recent development of these ideas in papers by Kai Wehmeier. We diagnose two main problems of Wehmeier’s account, the first concerning the treatment of individual constants, the second concerning so-called “pseudo-propositions” (Scheinsätze) (...) of classical logic such as$a=a$or$a=b \wedge b=c \rightarrow a=c$. We argue that overcoming these problems requires two fairly drastic departures from Wehmeier’s account: (1) Not every formula of classical first-order logic will be translatable into asingleformula of Wittgenstein’s exclusive notation. Instead, there will often be a multiplicity of possible translations, revealing the original “inclusive” formulas to beambiguous. (2) Certain formulas of first-order logic such as$a=a$will not be translatable into Wittgenstein’s notation at all, being thereby revealed as nonsensical pseudo-propositions which should be excluded from a “correct” conceptual notation. We provide translation procedures from inclusive quantifier-free logic into the exclusive notation that take these modifications into account and define a notion of logical equivalence suitable for assessing these translations. (shrink)

The aim of this paper is to provide an addendum to a paper by Rose with the same title which has appeared in an earlier issue of this Journal [2]. Our new result is: Theorem. A ring of characteristic zero which admits elimination of quantifiers in the language {0, 1, +, ·} is an algebraically closed field.