The study of pairs of modules (over a Dedekind domain) arises from two different perspectives, as a starting step in the analysis of tuples of submodules of a given module, or also as a particular case in the analysis of Abelian structures made by two modules and a morphism between them. We discuss how these two perspectives converge to pairs of modules, and we follow the latter one to obtain an alternative approach to the classification of pairs of torsionfree objects. (...) Then we restrict our attention to pairs of free modules. Our main results are that the theory of pairs of free Abelian groups is co-recursively enumerable, and that a few remarkable extensions of this theory are decidable. (shrink)

A new method for obtaining lower bounds on the computational complexity of logical theories is presented. It extends widely used techniques for proving the undecidability of theories by interpreting models of a theory already known to be undecidable. New inseparability results related to the well known inseparability result of Trakhtenbrot and Vaught are the foundation of the method. Their use yields hereditary lower bounds . By means of interpretations lower bounds can be transferred from one theory to another. Complicated machine (...) codings are replaced by much simpler definability considerations, viz., the kinds of binary relations definable with short formulas on large finite sets. Numerous examples are given, including new proofs of essentially all previously known lower bounds for theories, and lower bounds for various theories of finite trees, which turn out to be particularly useful. (shrink)

Let G be a finite group, T denote the theory of Z[G]-lattices . It is shown that T is undecidable when there are a prime p and a p-subgroup S of G such that S is cyclic of order p4, or p is odd and S is non-cyclic of order p2, or p = 2 and S is a non-cyclic abelian group of order 8 . More precisely, first we prove that T is undecidable because it interprets the word problem (...) for finite groups; then we lift undecidability from T to T. (shrink)