We recover the essentials of þ-forking, rosiness and super-rosiness for certain amalgamation classes K, and thence of finite-variable theories of finite structures. This provides a foundation for a model-theoretic analysis of a natural extension of the “LkLk-Canonization Problem” – the possibility of efficiently recovering finite models of T given a finite presentation of an LkLk-theory T. Some of this work is accomplished through different sorts of “transfer” theorem to the first-order theory TlimTlim of the direct limit. Our results include, to (...) start with, a recovery of the basic technology of þ-independence [15]) using a rather straightforward transfer. We also recover an analog of the “þ-Independence theorems” of Ealy and Onshuus [7] for amalgamation classes and their limits by showing how to transfer/lift an abstract independence relation on the amalgamation class to the limit theory TlimTlim. We also work out an appropriate notion of Local Character for independence relations over classes finite structures, and we use this to verify that rosiness and super-rosiness-with-finite-UþUþ-ranks coincide in these amalgamation classes and their limit theories. (shrink)

Model theory is concerned mainly, although not exclusively, with infinite structures. In recent years, finite structures have risen to greater prominence, both within the context of mainstream model theory, e.g., in work of Lachlan, Cherlin, Hrushovski, and others, and with the advent of finite model theory, which incorporates elements of classical model theory, combinatorics, and complexity theory. The purpose of this survey is to provide an overview of what might be called the model theory of finite structures. Some topics in (...) finite model theory have strong connections to theoretical computer science, especially descriptive complexity theory. In fact, it has been suggested that finite model theory really is, or should be, logic for computer science. These connections with computer science will, however, not be treated here.It is well-known that many classical results of ‘infinite model theory’ fail over the class of finite structures, including the compactness and completeness theorems, as well as many preservation and interpolation theorems. The failure of compactness in the finite, in particular, means that the standard proofs of many theorems are no longer valid in this context. At present, there is no known example of a classical theorem that remains true over finite structures, yet must be proved by substantially different methods. It is generally concluded that first-order logic is ‘badly behaved’ over finite structures.From the perspective of expressive power, first-order logic also behaves badly: it is both too weak and too strong. Too weak because many natural properties, such as the size of a structure being even or a graph being connected, cannot be defined by a single sentence. Too strong, because every class of finite structures with a finite signature can be defined by an infinite set of sentences. Even worse, every finite structure is defined up to isomorphism by a single sentence. In fact, it is perhaps because of this last point more than anything else that model theorists have not been very interested in finite structures. Modern model theory is concerned largely with complete first-order theories, which are completely trivial here. (shrink)

We give a complete and elementary proof of the following upward categoricity theorem: let be a local abstract elementary class with amalgamation and joint embedding, arbitrarily large models, and countable Löwenheim–Skolem number. If is categorical in 1 then is categorical in every uncountable cardinal. In particular, this provides a new proof of the upward part of Morley’s theorem in first order logic without any use of prime models or heavy stability theoretic machinery.