Affordable Access

Decidability and undecidability of theories of abelian groups with predicates for subgroups

Authors
Publication Date
Disciplines
  • Law
  • Logic

Abstract

Decidability and undecidability of theories of abelian groups with predicates for subgroups COMPOSITIO MATHEMATICA WALTERBAUR Decidability and undecidability of theories of abelian groups with predicates for subgroups Compositio Mathematica, tome 31, no 1 (1975), p. 23-30. <http://www.numdam.org/item?id=CM_1975__31_1_23_0> © Foundation Compositio Mathematica, 1975, tous droits réservés. L’accès aux archives de la revue « Compositio Mathematica » (http:// http://www.compositio.nl/) implique l’accord avec les conditions générales d’utilisation (http://www.numdam.org/legal.php). Toute utilisation commer- ciale ou impression systématique est constitutive d’une infraction pé- nale. Toute copie ou impression de ce fichier doit contenir la pré- sente mention de copyright. Article numérisé dans le cadre du programme Numérisation de documents anciens mathématiques http://www.numdam.org/ 23 DECIDABILITY AND UNDECIDABILITY OF THEORIES OF ABELIAN GROUPS WITH PREDICATES FOR SUBGROUPS Walter Baur1 COMPOSITIO MATHEMATICA, Vol. 31, Fasc. 1, 1975, pag. 23-30 Noordhoff International Publishing Printed in the Netherlands 0. Introduction Let n &#x3E; l, k ~ 5 be natural numbers and let T(n, k) be the first-order theory of the class of all structures A, A0, ···, Ak-1&#x3E; where A is an n-bounded abelian group (i.e. nA = 0) and A0, ···, Ak-1 are arbitrary subgroups of A. In the present paper the following results concerning decidability of T(n, k) are ‘obtained : (i) T(n, 5) is undecidable, (ii) if n contains a square then T(n, 4) is undecidable, (iii) if n is squarefree then T(n, 3) is decidable. A trivial consequence of (ii) is that the theory of abelian groups with four distinguished subgroups is undecidable 2 Terminology: ’group’ means ’abelian group’ except where stated other- wise. ’Countable’ means ’finite or countably infinite’. For all undefined notions from logic we refer to [5]. 1. Undecidability The first-order language L of abelian groups consists of a binary fun

There are no comments yet on this publication. Be the first to share your thoughts.