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: 93,296

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

Analytics

Added to PP
2013-09-30

Downloads
26 (#631,520)

6 months
59 (#85,085)

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