We correct a mistake in [V. Astier, Some model-theoretic results in the algebraic theory of quadratic forms, Ann. Pure Appl. Logic 112 189–223].

Alfred Tarski’s influence on computer science was indirect but significant in a number of directions and was in certain respects fundamental. Here surveyed is Tarski’s work on the decision procedure for algebra and geometry, the method of elimination of quantifiers, the semantics of formal languages, model-theoretic preservation theorems, and algebraic logic; various connections of each with computer science are taken up.

We study the class of l-groups of the form C with X an essential P-space. Many such l-groups are non-projectable and their elementary theories may often be reduced to that of an associated Boolean algebra with distinguished ideal. In this paper we establish the decidability of the theories of two classes of such l-groups via corresponding results for the associated structures.

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.

The Feferman–Vaught theorem provides a way of evaluating a first order sentence \(\varphi \) on a disjoint union of structures by producing a decomposition of \(\varphi \) into sentences which can be evaluated on the individual structures and the results of these evaluations combined using a propositional formula. This decomposition can in general be non-elementarily larger than \(\varphi \). We introduce a “tree” generalization of the prenex normal form (PNF) for first order sentences, and show that for an input sentence (...) in this form having a fixed number of quantifier alternations, a Feferman–Vaught decomposition can be obtained in time elementary in the size of the sentence. The sentences in the decomposition are also in tree PNF, and further have the same number of quantifier alternations and the same quantifier rank as the input sentence. We extend this result by considering binary operations other than disjoint union, in particular sum-like operations such as join, ordered sum and NLC-sum, that are definable using quantifier-free translation schemes. (shrink)

A monadic formula ψ is a selector for a monadic formula φ in a structure if ψ defines in a unique subset P of the domain and this P also satisfies φ in . If is a class of structures and φ is a selector for ψ in every , we say that φ is a selector for φ over .For a monadic formula φ and ordinals α≤ω1 and δ<ωω, we decide whether there exists a monadic formula ψ such that (...) for every Pα of order-type smaller than δ, ψ selects φ in . If so, we construct such a ψ.We introduce a criterion for a class of ordinals to have the property that every monadic formula φ has a selector over it. We deduce the existence of Sωω such that in the structure every formula has a selector.Given a monadic sentence π and a monadic formula φ, we decide whether φ has a selector over the class of countable ordinals satisfying π, and if so, construct one for it. (shrink)

On the basis of the Klingler–Levy classification of finitely generated modules over commutative noetherian rings we approach the old problem of classifying finite commutative rings R with a decidable theory of modules. We prove that if R is wild, then the theory of all R-modules is undecidable, and verify decidability of this theory for some classes of tame finite commutative rings.

Already after sending the first two parts of this paper ([5], [6]) to the editor, two new results on the subject have appeared — namely the results of G. Wilmers and Z. Ratajczyk. So for the sake of completeness let us review them here.

We show in this paper that the theory of ordinal addition of any fixed ordinal ωα, with α less than ωω, admits a quantifier elimination. This in particular gives a new proof for the decidability result first established in 1965 by R. Büchi using transfinite automata. Our proof is based on the Ehrenfeucht games, and we show that quantifier elimination go through generalized power.RésuméOn montre ici que, pour tout ordinal α inférieur à ωω, la théorie additive de ωα admet une (...) élimination des quantificateurs. On obtient ainsi une nouvelle preuve de la décidabilité de ces théories . On utilise ici les jeux d'Ehrenfeucht, avec un formalisme à la Ferrante et Rackoff, et on montre que le fait d'admettre une élimination des quantificateurs se transmet par produit généralisé. (shrink)

Hird, G.R., Recursive properties of relations on models, Annals of Pure and Applied Logic 63 241–269. We prove general existence theorems for recursive models on which various relations have specified recursive properties. These capture common features of results in the literature for particular algebraic structures. For a useful class of models with new relations R, S, where S is r.e., we characterize those for which there is a recursive model isomorphic to on which the relation corresponding to S remains r.e., (...) while that corresponding to R is not r.e.; immune; hyperimmune. The results are applied to vector spaces, Boolean algebras and abelian groups. In the case of vector spaces, this leads to a new kind supermaximal subspace of V∞. (shrink)

We present some results concerning elimination of quantifiers and elementary equivalence for Boolean products of real closed valuation rings and fields. We also study rings of continuous functions and rings of definable functions over real closed valuation rings under this point of view.

In this paper, inspired by methods of Bigard, Keimel, and Wolfenstein , we develop an approach to sheaf representations of MV-algebras which combines two techniques for the representation of MV-algebras devised by Filipoiu and Georgescu and by Dubuc and Poveda . Following Davey approach , we use a subdirect representation of MV-algebras that is based on local MV-algebras. This allowed us to obtain: a representation of any MV-algebras as MV-algebra of all global sections of a sheaf of local MV-algebras on (...) the spectruum of its prime ideals; a representation of MV-algebras, having the space of minimal prime ideals compact, as MV-algebra of all global sections of a Hausdorff sheaf of MV-chains on the space of minimal prime ideals, which is a Stone space; an adjunction between the category of all MV-algebras and the category of MV-algebraic spaces, where an MV-algebraic space is a pair , where X is a compact topological space and F is a sheaf of MV-algebras with stalks that are local. (shrink)

I had the pleasure of renewing my acquaintance with Per Lindström at the meeting of the Seventh Scandinavian Logic Symposium, held in Uppsala in August 1996. There at lunch one day, Per said he had long been curious about the development of some of the ideas in my paper [1960] on the arithmetization of metamathematics. In particular, I had used the construction of a non-standard definition !* of the set of axioms of P (Peano Arithmetic) to show that P + (...) {¬ Con!} is interpretable in P, where ! is a standard definition of the axioms of P and Con! expresses the consistency of P via that presentation. Per pointed out that there is a simple “two-line” proof of this interpretability result which does not require the use of such formulas as !*, and he wondered whether I had been aware of that. In fact, his proof had never occurred to me, and if it had at the time, it is possible I would never have been led to the use of non-natural definitions. Per regarded this as a happy accident, since subsequent work by him and others on interpretability made essential use of such definitions. In our conversation, I enlarged a bit on the background to my work on arithmetization, and when I was invited to contribute to this special issue of Theoria dedicated to Lindström, it seemed a natural choice to use the occasion to fill out the story. One caveat, though: the following is drawn largely from memory, not always reliable, supplemented by consultation of the 1960 paper and the 1957 dissertation from which it was drawn. (shrink)

We give foundational results for the model theory of AfinK, the ring of finite adeles over a number field, construed as a restricted product of local fields. In contrast to Weispfenning we work in the language of ring theory, and various sortings interpretable therein. In particular we give a systematic treatment of the product valuation and the valuation monoid. Deeper results are given for the adelic version of Krasner's hyperfields, relating them to the Basarab–Kuhlmann formalism.

We generalize a theorem of Mundici relating compactness of a regular logic L to a strong form of normality of the associated spaces of models. Moreover, it is shown that compactness is in fact equivalent to ordinary normality of the model spaces when L has uniform reduction for infinite disjoint sums of structures. Some applications follow. For example, a countably generated logic is countably compact if and only if every clopen class in the model spaces is elementary. The model spaces (...) of L are not normal for vocabularies of uncountable power ωα. It also follows that first-order logic is the only finite-dependence logic having normal model spaces and satisfying at the same time the downward Löwenheim-Skolem theorem and uniform reduction for pairs. (shrink)

This paper studies some model-theoretic properties of special groups of finite type. Special groups are a first-order axiomatization of the algebraic theory of quadratic forms, introduced by Dickmann and Miraglia, which is essentially equivalent to abstract Witt rings. More precisely, we consider elementary equivalence, saturation, elementary embeddings, quantifier elimination, stability and Morley rank.

We characterize elementary equivalences and inclusions between von Neumann regular real closed rings in terms of their boolean algebras of idempotents, and prove that their theories are always decidable. We then show that, under some hypotheses, the map sending an L-structure R to the L-structure of definable functions from R n to R preserves elementary inclusions and equivalences and gives a structure with a decidable theory whenever R is decidable. We briefly consider structures of definable functions satisfying an extra condition (...) such as continuity. (shrink)