Second-order quantifiers and the complexity of theories.

In this paper 1 we classify all theories of the form (, <) where (, ) is the collection of < sentences valid on the models of the complete first-order theory T and < is one of the following: second-order logic, permutational logic, or monadic logic. We regard any theory into which second-order logic can be interpreted (in the strong sense used here) as hopelessly complicated. We partition those theories in which such an interpretation does not exist into four classes and find a prototype for each class. One of the classes contains unstable theories; the other three are stable. In the unstable case we show the following. First, the permutational theory of the class interprets second-order logic so only the monadic theory is interesting. We show the monadic theory of the class is at least as complicated as the monadic theory of order. Now by one measure the members of this class cannot be differentiated: (under weak set theoretic hypotheses) all the monadic theories have the same Lwenheim number-that of second-order logic. In contrast we show that the Hanf number of the monadic theory of order is strictly less than the Hanf number of second-order logic. This proof requires the computations of Hanf and Lwenheim numbers of various theories of (well) orderings. These computations are interesting in their own right. If is stable we use a Feferman-Vaught type of theorem to decompose models of these theories into trees. The nodes of these trees are small models and the height of the tree is uniformly bounded over all models of T. The other three cases arise when this tree is: (a) well-founded, (b) imbeddable in < , or (c) otherwise. This allows us to compute the Hanf and Lwenheim numbers of such theories. A more detailed exposition of the methodology and aims of the paper appears in the survey (Section 1.2) of results which follow.