Isomorphism relations on computable structures

We study the complexity of the isomorphism relation on classes of computable structures. We use the notion of FF-reducibility introduced in [9] to show completeness of the isomorphism relation on many familiar classes in the context of all ${\mathrm{\Sigma }}_{1}^{1}$ equivalence relations on hypera...

Full description

Saved in:
Bibliographic Details
Published in:The Journal of symbolic logic 2012-03, Vol.77 (1), p.122-132
Main Authors: Fokina, Ekaterina B., Friedman, Sy-David, Harizanov, Valentina, Knight, Julia F., Mccoy, Charles, Montalbán, Antonio
Format: Article
Language:English
Subjects:
Algebra
College mathematics
Descriptive set theory
Equivalence relation
Index sets
Isomorphism
Mathematical logic
Mathematical relations
Mathematical set theory
Mathematical theorems
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We study the complexity of the isomorphism relation on classes of computable structures. We use the notion of FF-reducibility introduced in [9] to show completeness of the isomorphism relation on many familiar classes in the context of all ${\mathrm{\Sigma }}_{1}^{1}$ equivalence relations on hyperarithmetical subsets of ω.
ISSN:0022-4812
1943-5886
DOI:10.2178/jsl/1327068695