Second-order quantifiers and the complexity of theories (Q1078169)

The study of properties of models which are not first-order expressible and the study of the relative complexity of various theories in an arbitrary logic are combined in the following programme. Consider two theories \(T_ 1\) and \(T_ 2\) formulated in a logic L. To compare their strengths, choose a stronger logic \(L^ 1\). Now think of \(T_ 1\) and \(T_ 2\) as \(L^ 1\)-theories and investigate their properties. The authors classify all theories of the form (T,L) where (T,L) is the collection of L sentences valid on the models of the complete first-order theory T and L is one of the following: second-order logic, permutational logic, or monadic logic. They partition those theories, in which second- order logic cannot be interpreted, 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 it is shown that the permutational theory of the class interprets second-order logic and that the monadic theory of the class is at least as complicated as the monadic theory of order. All the monadic theories have the same Löwenheim number - that of second-order logic. But the Hanf number of the monadic theory of order is strictly less than the Hanf number of second-order logic. In the other three cases each model of the theory with cardinality \(\lambda\) is associated with a tree of height \(<\aleph_ 1\). The three cases correspond to \(\lambda^{<\aleph_ 1}\), the full tree \(\lambda^{<\omega}\) and well-founded subtrees of \(\lambda^{<\omega}\). The Löwenheim and Hanf numbers of such theories are computed. Much of the paper is devoted to answering the following question: why does research in monadic logic focus on theories of order and trees and why is research in permutational logic concerned entirely with the theory of equality? The paper can be viewed ''as propaganda for classification theory as the present material demonstrates the importance of the earlier work on classification theory by applying it in a nontrivial context''.