Computability of fraïssé limits

Journal of Symbolic Logic 76 (1):66 - 93 (2011)

Authors
Valentina Harizanov
George Washington University
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
Edit this record
Mark as duplicate
Export citation
Find it on Scholar
Request removal from index
Revision history

Download options

Our Archive


Upload a copy of this paper     Check publisher's policy     Papers currently archived: 42,993
Through your library

References found in this work BETA

A Shorter Model Theory.Wilfrid Hodges - 2000 - Studia Logica 64 (1):133-134.

View all 13 references / Add more references

Citations of this work BETA

Add more citations

Similar books and articles

Analytics

Added to PP index
2013-09-30

Total views
13 ( #604,932 of 2,259,693 )

Recent downloads (6 months)
2 ( #663,859 of 2,259,693 )

How can I increase my downloads?

Downloads

My notes

Sign in to use this feature