Super/rosy L k -theories and classes of finite structures

Annals of Pure and Applied Logic 164 (10):907-927 (2013)
  Copy   BIBTEX

Abstract

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.

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 91,219

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

Similar books and articles

Amalgamation properties and finite models in L n -theories.John Baldwin & Olivier Lessmann - 2002 - Archive for Mathematical Logic 41 (2):155-167.
Independence in finitary abstract elementary classes.Tapani Hyttinen & Meeri Kesälä - 2006 - Annals of Pure and Applied Logic 143 (1-3):103-138.
Forking in Finite Models.Tapani Hyttinen - 2015 - Notre Dame Journal of Formal Logic 56 (2):307-320.
Canonical Finite Diagrams and Quantifier Elimination.Tapani Hyttinen - 2002 - Mathematical Logic Quarterly 48 (4):533-554.
Characterizing Rosy Theories.Clifton Ealy & Alf Onshuus - 2007 - Journal of Symbolic Logic 72 (3):919 - 940.
Modal characterisation theorems over special classes of frames.Anuj Dawar & Martin Otto - 2010 - Annals of Pure and Applied Logic 161 (1):1-42.
Stable types in rosy theories.Assaf Hasson & Alf Onshuus - 2010 - Journal of Symbolic Logic 75 (4):1211-1230.
Hereditary undecidability of some theories of finite structures.Ross Willard - 1994 - Journal of Symbolic Logic 59 (4):1254-1262.
Finite Model Theory and Finite Variable Logics.Eric Barry Rosen - 1995 - Dissertation, University of Pennsylvania
Locally finite weakly minimal theories.James Loveys - 1991 - Annals of Pure and Applied Logic 55 (2):153-203.
A first-order axiomatization of the theory of finite trees.Rolf Backofen, James Rogers & K. Vijay-Shanker - 1995 - Journal of Logic, Language and Information 4 (1):5-39.
On second-order generalized quantifiers and finite structures.Anders Andersson - 2002 - Annals of Pure and Applied Logic 115 (1--3):1--32.
Finiteness Classes and Small Violations of Choice.Horst Herrlich, Paul Howard & Eleftherios Tachtsis - 2016 - Notre Dame Journal of Formal Logic 57 (3):375-388.

Analytics

Added to PP
2013-12-12

Downloads
22 (#669,532)

6 months
3 (#902,269)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

Add more citations

References found in this work

A geometric introduction to forking and thorn-forking.Hans Adler - 2009 - Journal of Mathematical Logic 9 (1):1-20.
Characterizing Rosy Theories.Clifton Ealy & Alf Onshuus - 2007 - Journal of Symbolic Logic 72 (3):919 - 940.
Properties and Consequences of Thorn-Independence.Alf Onshuus - 2006 - Journal of Symbolic Logic 71 (1):1 - 21.
Deux ou trois choses que je sais de ln.Bruno Poizat - 1982 - Journal of Symbolic Logic 47 (3):641 - 658.
Thorn-forking as local forking.Hans Adler - 2009 - Journal of Mathematical Logic 9 (1):21-38.

View all 11 references / Add more references