Necessary and sufficient conditions are presented for the (first-order) theory of a universal class of algebraic structures (algebras) to have a model completion, extending a characterization provided by Wheeler. For varieties of algebras that have equationally definable principal congruences and the compact intersection property, these conditions yield a more elegant characterization obtained (in a slightly more restricted setting) by Ghilardi and Zawadowski. Moreover, it is shown that under certain further assumptions on congruence lattices, the existence of a model (...) completion implies that the variety has equationally definable principal congruences. This result is then used to provide necessary and sufficient conditions for the existence of a model completion for theories of Hamiltonian varieties of pointed residuated lattices, a broad family of varieties that includes lattice-ordered abelian groups and MV-algebras. Notably, if the theory of a Hamiltonian variety of pointed residuated lattices has a model completion, it must have equationally definable principal congruences. In particular, the theories of lattice-ordered abelian groups and MV-algebras do not have a model completion, as first proved by Glass and Pierce, and Lacava, respectively. Finally, it is shown that certain varieties of pointed residuated lattices generated by their linearly ordered members, including lattice-ordered abelian groups and MV-algebras, can be extended with a binary operation to obtain theories that do have a model completion. (shrink)

We prove the model completeness of expansions of the reals by restricted elliptic and abelian functions. We make use of an auxiliary structure admitting quantifier elimination, where the basic relations are strongly definable in the original structure.

Let p be prime number, K be a p‐adically closed field, a semi‐algebraic set defined over K and the lattice of semi‐algebraic subsets of X which are closed in X. We prove that the complete theory of eliminates quantifiers in a certain language, the ‐structure on being an extension by definition of the lattice structure. Moreover it is decidable, contrary to what happens over a real closed field for. We classify these ‐structures up to elementary equivalence, and get in (...) particular that the complete theory of only depends on m, not on K nor even on p. As an application we obtain a classification of semi‐algebraic sets over countable p‐adically closed fields up to so‐called “pre‐algebraic” homeomorphisms. (shrink)

We find the model completion of the theory modules over ������, where ������ is a finitely generated commutative algebra over a field K. This is done in a context where the field K and the module are represented by sorts in the theory, so that constructible sets associated with a module can be interpreted in this language. The language is expanded by additional sorts for the Grassmanians of all powers of $K^n $ , which are necessary to achieve quantifier (...) elimination. The result turns out to be that the model completion is the theory of a certain class of "big" injective modules. In particular, it is shown that the class of injective modules is itself elementary. We also obtain an explicit description of the types in this theory. (shrink)

We characterize when the elementary diagram of a mutually algebraic structure has a model complete theory, and give an explicit description of a set of existential formulas to which every formula is equivalent. This characterization yields a new, more constructive proof that the elementary diagram of any model of a strongly minimal, trivial theory is model complete.

We show that if T is a trivial uncountably categorical theory of Morley Rank 1 then T is model complete after naming constants for a model.

Under some assumptions on an equational theory S , we give a necessary and sufficient condition so that S admits a model completion. These assumptions are often met by the equational theories arising from logic. They say that the dual of the category of finitely presented S-algebras has some categorical stucture. The results of this paper combined with those of [7] show that all the 8 theories of amalgamable varieties of Heyting algebras [12] admit a model completion. Further (...) applications to varieties of modal algebras are given in [8]. (shrink)

Universal theories with model completions are characterized. A new omitting types theorem is proved. These two results are used to prove the existence of a universal ℵ 0 -categorical partial order with an interesting embedding property. Other aspects of these results also are considered.

The notion of a D-ring, generalizing that of a differential or a difference ring, is introduced. Quantifier elimination and a version of the Ax-Kochen-Eršov principle is proven for a theory of valued D-fields of residual characteristic zero.

We study the implications of model completeness of a theory for the effectiveness of presentations of models of that theory. It is immediate that for a computable model A\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathcal {A}$$\end{document} of a computably enumerable, model complete theory, the entire elementary diagram E\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$E$$\end{document} must be decidable. We prove that indeed a c.e. theory T is model complete if (...) and only if there is a uniform procedure that succeeds in deciding E\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$E$$\end{document} from the atomic diagram Δ\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\varDelta $$\end{document} for all countable models A\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathcal {A}$$\end{document} of T. Moreover, if every presentation of a single isomorphism type A\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathcal {A}$$\end{document} has this property of relative decidability, then there must be a procedure with succeeds uniformly for all presentations of an expansion \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$$$\end{document} by finitely many new constants. (shrink)

The projective plane of Baldwin 695) is model complete in a language with additional constant symbols. The infinite rank bicolored field of Poizat 1339) is not model complete. The finite rank bicolored fields of Baldwin and Holland 371; Notre Dame J. Formal Logic , to appear) are model complete. More generally, the finite rank expansions of a strongly minimal set obtained by adding a ‘random’ unary predicate are almost strongly minimal and model (...) class='Hi'>complete provided the strongly minimal set is ‘well-behaved’ and admits ‘exactly rank k formulas’. The last notion is a geometric condition on strongly minimal sets formalized in this paper. (shrink)

We define a Lie differential field as a field of characteristic 0 with an action, as derivations on , of some given Lie algebra . We assume that is a finite-dimensional vector space over some sub-field given in advance. As an example take the field of rational functions on a smooth algebraic variety, with .For every simple extension of Lie differential fields we find a finite system of differential equations that characterizes it. We then define, using first-order conditions, a collection (...) of allowed systems of differential equations s.t. the above characteristic systems are allowed. We prove that for every allowed system there exists a generic solution in some extension, and this solution is unique .We construct the model completion of the theory of Lie differential fields by adding axioms stating that every allowed system has almost generic solutions. The construction is a generalization of Blum's axioms for DCF0. We also show that this model completion is ω-stable. (shrink)

The notion of a D-ring, generalizing that of a differential or a difference ring, is introduced. Quantifier elimination and a version of the Ax-Kochen-Ersov principle is proven for a theory of valued D-fields of residual characteristic zero.

Let \ be an ab initio amalgamation class with an unbounded increasing concave function f. We show that if the predimension function has a rational coefficient and f satisfies a certain assumption then the generic structure of \ has a model complete theory.

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 prove that given any first order formula φ in the language L' = {+,., <, (f i ) i ∈ I , (c i ) i ∈ I }, where the f i are unary function symbols and the c i are constants, one can find an existential formula ψ such that φ and ψ are equivalent in any L'-structure $\langle {\Bbb R},+,.,<,(x^{c_{i}})_{i\in I},(c_{i})_{i\in I}\rangle $.

Extending the language of rings to include predicates for Jacobson radical relations, we show that the theory of regular rings defined by Carson, Lipshitz and Saracino is the model completion of the theory of semisimple rings. Removing the requirement on the Jacobson radical (reduced to {0}), we prove that the theory of rings with no nilpotents does not admit a model companion relative to this augmented language.

In the present paper, we start studying epistemic updates using the standard toolkit of duality theory. We focus on public announcements, which are the simplest epistemic actions, and hence on Public Announcement Logic without the common knowledge operator. As is well known, the epistemic action of publicly announcing a given proposition is semantically represented as a transformation of the model encoding the current epistemic setup of the given agents; the given current model being replaced with its submodel relativized (...) to the announced proposition. We dually characterize the associated submodel-injection map as a certain pseudo-quotient map between the complex algebras respectively associated with the given model and with its relativized submodel. As is well known, these complex algebras are complete atomic BAOs . The dual characterization we provide naturally generalizes to much wider classes of algebras, which include, but are not limited to, arbitrary BAOs and arbitrary modal expansions of Heyting algebras . Thanks to this construction, the benefits and the wider scope of applications given by a point-free, intuitionistic theory of epistemic updates are made available. As an application of this dual characterization, we axiomatize the intuitionistic analogue of PAL, which we refer to as IPAL, prove soundness and completeness of IPAL w.r.t. both algebraic and relational models, and show that the well known Muddy Children Puzzle can be formalized in IPAL. (shrink)

A class of models is presented, in the form of continuation monads polymorphic for first-order individuals, that is sound and complete for minimal intuitionistic predicate logic . The proofs of soundness and completeness are constructive and the computational content of their composition is, in particular, a β-normalisation-by-evaluation program for simply typed lambda calculus with sum types. Although the inspiration comes from Danvyʼs type-directed partial evaluator for the same lambda calculus, the use of delimited control operators is avoided. The role (...) of polymorphism is crucial – dropping it allows one to obtain a notion of model complete for classical predicate logic. (shrink)

In this paper we give a differential lifting principle which provides a general method to geometrically axiomatize the model companion (if it exists) of some theories of differential topological fields. The topological fields we consider here are in fact topological systems in the sense of van den Dries, and the lifting principle we develop is a generalization of the geometric axiomatization of the theory DCF₀ given by Pierce and Pillay. Moreover, it provides a geometric alternative to the axiomatizations obtained (...) by Tressl and Guzy/Point in separate papers where the authors also build general schemes of axioms for some model complete theories of differential fields. We first characterize the existentially closed models of a given theory of differential topological fields and then, under an additional hypothesis of largeness, we show how to modify this characterization to get a general scheme of first-order axioms for the model companion of any large theory of differential topological fields. We conclude with an application of this lifting principle proving that, in existentially closed models of a large theory of differential topological fields, the jet-spaces are dense in their ambient topological space. (shrink)

We approach the subject of o-minimality from the point of view of tame systems, following the work of Charbonnel and Wilkie. This gives some general sufficient conditions for a system to be model complete and o-minimal. We are then able to obtain the following generalisation of a recent result of Gabrielov : A polynomially bounded o-minimal expansion of the real ordered field by a collection of restricted C∝ functions, which is closed under partial differentiation, is model (...) class='Hi'>complete. (shrink)

We build a new spectrum of recursive models (SRM(T)) of a strongly minimal theory. This theory is non-disintegrated, flat, model complete, and in a language with a finite structure.