On Σ11 equivalence relations over the natural numbers

✍ Scribed by Ekaterina B. Fokina; Sy-David Friedman

• Publisher: John Wiley and Sons
• Year: 2011
• Tongue: English
• Weight: 155 KB
• Volume: 58
• Category: Article
• ISSN: 0044-3050
• DOI: 10.1002/malq.201020063

✦ Synopsis

Abstract

We study the structure of Σ^1^~1~ equivalence relations on hyperarithmetical subsets of ω under reducibilities given by hyperarithmetical or computable functions, called h‐reducibility and FF‐reducibility, respectively. We show that the structure is rich even when one fixes the number of properly \documentclass{article}\usepackage{amssymb}\begin{document}\pagestyle{empty}$\Sigma ^1_1\ \big ($\end{document}i.e., Σ^1^~1~ but not \documentclass{article}\usepackage{amssymb}\begin{document}\pagestyle{empty}$\Delta ^1_1\big )$\end{document} equivalence classes. We also show the existence of incomparable Σ^1^~1~ equivalence relations that are complete as subsets of ω × ω with respect to the corresponding reducibility on sets. We study complete Σ^1^~1~ equivalence relations (under both reducibilities) and show that existence of infinitely many properly Σ^1^~1~ equivalence classes that are complete as Σ^1^~1~ sets (under the corresponding reducibility on sets) is necessary but not sufficient for a relation to be complete in the context of Σ^1^~1~ equivalence relations.