Computability of fraïssé limits

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

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

Download options

PhilArchive



    Upload a copy of this work     Papers currently archived: 72,743

External links

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

Through your library

Analytics

Added to PP
2013-09-30

Downloads
29 (#399,260)

6 months
1 (#387,390)

Historical graph of downloads
How can I increase my downloads?

Author's Profile

Valentina Harizanov
George Washington University

Citations of this work

Add more citations