Computability of fraïssé limits

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

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

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 92,347

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
59 (#274,113)

6 months
28 (#110,211)

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

References found in this work

Computable structures and the hyperarithmetical hierarchy.C. J. Ash - 2000 - New York: Elsevier. Edited by J. Knight.
Degrees coded in jumps of orderings.Julia F. Knight - 1986 - Journal of Symbolic Logic 51 (4):1034-1042.
Degrees of structures.Linda Jean Richter - 1981 - Journal of Symbolic Logic 46 (4):723-731.

View all 13 references / Add more references