Journal of Symbolic Logic 76 (1):66 - 93 (2011)
Authors |
|
Abstract |
Fraïssé studied countable structures S through analysis of the age of S i.e., the set of all finitely generated substructures of S. We investigate the effectiveness of his analysis, considering effectively presented lists of finitely generated structures and asking when such a list is the age of a computable structure. We focus particularly on the Fraïssé limit. We also show that degree spectra of relations on a sufficiently nice Fraïssé limit are always upward closed unless the relation is definable by a quantifier-free formula. We give some sufficient or necessary conditions for a Fraïssé limit to be spectrally universal. As an application, we prove that the computable atomless Boolean algebra is spectrally universal
|
Keywords | No keywords specified (fix it) |
Categories | (categorize this paper) |
DOI | 10.2178/jsl/1294170990 |
Options |
![]() ![]() ![]() ![]() |
Download options
References found in this work BETA
Degree Spectra and Computable Dimensions in Algebraic Structures.Denis R. Hirschfeldt, Bakhadyr Khoussainov, Richard A. Shore & Arkadii M. Slinko - 2002 - Annals of Pure and Applied Logic 115 (1-3):71-113.
Degrees Coded in Jumps of Orderings.Julia F. Knight - 1986 - Journal of Symbolic Logic 51 (4):1034-1042.
Enumerations in Computable Structure Theory.Sergey Goncharov, Valentina Harizanov, Julia Knight, Charles McCoy, Russell Miller & Reed Solomon - 2005 - Annals of Pure and Applied Logic 136 (3):219-246.
View all 13 references / Add more references
Citations of this work BETA
Hanf Number for Scott Sentences of Computable Structures.S. S. Goncharov, J. F. Knight & I. Souldatos - 2018 - Archive for Mathematical Logic 57 (7-8):889-907.
Similar books and articles
Spectra of Structures and Relations.Valentina S. Harizanov & Russel G. Miller - 2007 - Journal of Symbolic Logic 72 (1):324 - 348.
On Ehrenfeucht-Fraïssé Equivalence of Linear Orderings.Juha Oikkonen - 1990 - Journal of Symbolic Logic 55 (1):65-73.
Intrinsic Bounds on Complexity and Definability at Limit Levels.John Chisholm, Ekaterina B. Fokina, Sergey S. Goncharov, Valentina S. Harizanov, Julia F. Knight & Sara Quinn - 2009 - Journal of Symbolic Logic 74 (3):1047-1060.
Kolmogorov Complexity and Symmetric Relational Structures.W. L. Fouché & P. H. Potgieter - 1998 - Journal of Symbolic Logic 63 (3):1083-1094.
A Group-Theoretical Invariant for Elementary Equivalence and its Role in Representations of Elementary Classes.Daniele Mundici - 1981 - Studia Logica 40 (3):253 - 267.
Computable Isomorphisms of Boolean Algebras with Operators.Bakhadyr Khoussainov & Tomasz Kowalski - 2012 - Studia Logica 100 (3):481-496.
Dress or Patchwork? Visions of Excess in Proust’s In Search of Lost Time.Miguel de Beistegui - unknown
Über Die Geschicklichkeit der Geschlechterdifferenz.Geneviève Fraisse - 1993 - Die Philosophin 4 (7):19-22.
Analytics
Added to PP index
2013-09-30
Total views
27 ( #385,261 of 2,411,471 )
Recent downloads (6 months)
4 ( #188,489 of 2,411,471 )
2013-09-30
Total views
27 ( #385,261 of 2,411,471 )
Recent downloads (6 months)
4 ( #188,489 of 2,411,471 )
How can I increase my downloads?
Downloads