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.

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.

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.

We say that a ring admits elimination of quantifiers, if in the language of rings, {0, 1, +, ·}, the complete theory of R admits elimination of quantifiers. Theorem 1. Let D be a division ring. Then D admits elimination of quantifiers if and only if D is an algebraically closed or finite field. A ring is prime if it satisfies the sentence: ∀ x ∀ y ∃ z (x = 0 ∨ y = (...) 0 ∨ xzy ≠ 0). Theorem 2. If R is a prime ring with an infinite center and R admits elimination of quantifiers, then R is an algebraically closed field. Let A be the class of finite fields. Let B be the class of 2 × 2 matrix rings over a field with a prime number of elements. Let C be the class of rings of the form $GF(p^n) \bigoplus GF(p^k)$ such that either n = k or g.c.d. (n, k) = 1. Let D be the set of ordered pairs (f, Q) where Q is a finite set of primes and f: Q → A ∪ B ∪ C such that the characteristic of the ring f(q) is q. Finally, let E be the class of rings of the form $\bigoplus_{q \in Q}f(q)$ for some (f, Q) in D. Theorem 3. Let R be a finite ring without nonzero trivial ideals. Then R admits elimination of quantifiers if and only if R belongs to E. Theorem 4. Let R be a ring with the descending chain condition of left ideals and without nonzero trivial ideals. Then R admits elimination of quantifiers if and only if R is an algebraically closed field or R belongs to E. In contrast to Theorems 2 and 4, we have Theorem 5. If R is an atomless p-ring, then R is finite, commutative, has no nonzero trivial ideals and admits elimination of quantifiers, but is not prime and does not have the descending chain condition. We also generalize Theorems 1, 2 and 4 to alternative rings. (shrink)

A structure of finite signature is constructed so that: for all existential formulas $\exists ??\varphi (??,??)$ and for all tuples of elements $??$ of the same length as the tuple $??$, one can decide in a quadratic time depending only on the length of the formula, if $\exists ??\varphi (??,??)$ holds in the structure. In other words, the structure satisfies the relativized model-theoretic version of P=NP in the sense of [4]. This is a model-theoretical approach to results of Hemmerling and (...) Gaßner. (shrink)

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.

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.

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.

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)

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.

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)

A uniform construction for sequent calculi for finite-valued first-order logics with distribution quantifiers is exhibited. Completeness, cut-elimination and midsequent theorems are established. As an application, an analog of Herbrand’s theorem for the four-valued knowledge-representation logic of Belnap and Ginsberg is presented. It is indicated how this theorem can be used for reasoning about knowledge bases with incomplete and inconsistent information.

Although it was traditionally thought that self-reference is a crucial ingredient of semantic paradoxes, Yablo (1993, 2004) showed that this was not so by displaying an infinite series of sentences none of which is self-referential but which, taken together, are paradoxical. Yablo's paradox consists of a countable series of linearly ordered sentences s(0), s(1), s(2),... , where each s(i) says: For each k > i, s(k) is false (or equivalently: For no k > i is s(k) true). We generalize Yablo's (...) results along two dimensions. First, we study the behavior of generalized Yablo-series in which each sentence s(i) has the form: For Q k > i, s(k) is true, where Q is a generalized quantifier (e.g., no, every, infinitely many, etc). We show that under broad conditions all the sentences in the series must have the same truth value, and we derive a characterization of those values of Q for which the series is paradoxical. Second, we show that in the Strong Kleene trivalent logic Yablo's results are a special case of a more general fact: under certain conditions, any semantic phenomenon that involves self-reference can be emulated without self-reference. Various translation procedures that eliminate self-reference from a non-quantificational language are defined and characterized. An Appendix sketches an extension to quantificational languages, as well as a new argument that Yablo's paradox and the translations we offer do not involve self-reference. (shrink)

In this paper a new method, elimination of Skolem functions for monotone formulas, is developed which makes it possible to determine precisely the arithmetical strength of instances of various non-constructive function existence principles. This is achieved by reducing the use of such instances in a given proof to instances of certain arithmetical principles. Our framework are systems ${\cal T}^{\omega} :={\rm G}_n{\rm A}^{\omega} +{\rm AC}$ -qf $+\Delta$ , where (G $_n$ A $^{\omega})_{n \in {\Bbb N}}$ is a hierarchy of (weak) (...) subsystems of arithmetic in all finite types (introduced in [14]), AC-qf is the schema of quantifier-free choice in all types and $\Delta$ is a set of certain analytical principles which e.g. includes the binary König's lemma. We apply this method to show that the arithmetical closures of single instances of $\Pi^0_1$ -comprehension and -choice contribute to the growth of extractable bounds from proofs relative to ${\cal T}^\omega$ only by a primitive recursive functional in the sense of Kleene. In subsequent papers these results are widely generalized and the method is used to determine the arithmetical content of single sequences of instances of the Bolzano-Weierstraß principle for bounded sequences in ${\Bbb R}^d$ , the Ascoli-lemma and others. (shrink)

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

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

Most of the early proofs of the decidability or completeness of certain mathematical theories were based on the method of eliminations of quantifiers. Various more recent results on completeness were obtained independently of such procedures. However, it is shown in the present paper that, conversely, the completeness of a mathematical theory will in certain circumstances entail the existence of an elimination method. The proof involves the application of the extended first ε‐theorem of Hilbert‐Bernays.ZusammenfassungDie meisten früheren Beweise der Vollständigkeit (...) oder Entscheidbarkeit gewisser mathematischer Theorien benutzten die sogenannte Quantoren‐eliminierungsmethode. Dagegen sind einige neuere Ergebnisse über Voll‐ständigkeit unabhängig von diesem Verfahren. Es ist deshalb von Interesse festzustellen, dass umgekehrt die Vollständigkeit einer mathematischen Theorie unter Umständen die Existenz einer Eliminierungsmethode fürdiese Theorie nach sich zieht. Der Beweis benutzt das erweiterte erste ε‐Theorem von Hilbert‐Bernays.SommaireBeaucoup de démonstrations concernant la complétude de certaines théories mathématiques, ou concernant l'existence d'un procédé de décision pour une telle théorie, sont basées sur des méthodes d'élimination de quantificateurs. Or, il y a des résultats plus récents sur la complétude de certaines théories qui ne dépendent pas de telles méthodes d'élimination. Toutefois on démontre ici que la complétude d'une théorie mathématique entraîne sous certaines conditions l'existence d'une méthode d'élimination. Au cours de la démonstration on se sert d'un des théorèmes‐ε de Hilbert‐Bernays. (shrink)

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.

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)

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

The article rebutts Michael Kremer’s contention that Russell’s contextual definition of set-theoretic language in Principia Mathematica constituted the ontological achievement of eliminating commitment to classes. Although Russell’s higher-order quantifiers, used in the definition, need not range over classes, none of the plausible substitutes provide a solid basis for eliminating them. This point is used to defend the presentation, in The Dawn of Analysis, of Russell’s logicist reduction, using a first-order version of naive set theory.

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