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)

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.

This paper obtains lower and upper bounds for the number of alternations of bounded quantifiers needed to express all formulas in certain ordered Abelian groups admitting elimination of unbounded quantifiers. The paper also establishes model-theoretic tests for equivalence to a formula with a given number of alternations of bounded quantifiers.

C. U. Jensen suggested the following construction, starting from a fieldK:and asked when two fieldsKαandKβare equivalent. We give a complete answer in the case of a fieldKof characteristic 0.