On Σ1 1 equivalence relations over the natural numbers

Mathematical Logic Quarterly 58 (1-2):113-124 (2012)
  Copy   BIBTEX

Abstract

We study the structure of Σ11 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 equation imagei.e., Σ11 but not equation image equivalence classes. We also show the existence of incomparable Σ11 equivalence relations that are complete as subsets of ω × ω with respect to the corresponding reducibility on sets. We study complete Σ11 equivalence relations and show that existence of infinitely many properly Σ11 equivalence classes that are complete as Σ11 sets is necessary but not sufficient for a relation to be complete in the context of Σ11 equivalence relations

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 90,616

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

? 0 N -equivalence relations.Andrea Sorbi - 1982 - Studia Logica 41 (4):351-358.
$\sum_{0}^{n}$ -Equivalence Relations.Andrea Sorbi - 1982 - Studia Logica 41 (4):351 - 358.
Classifying positive equivalence relations.Claudio Bernardi & Andrea Sorbi - 1983 - Journal of Symbolic Logic 48 (3):529-538.
Maximal R.e. Equivalence relations.Jeffrey S. Carroll - 1990 - Journal of Symbolic Logic 55 (3):1048-1058.
Infinite Time Decidable Equivalence Relation Theory.Samuel Coskey & Joel David Hamkins - 2011 - Notre Dame Journal of Formal Logic 52 (2):203-228.
Analytic equivalence relations and bi-embeddability.Sy-David Friedman & Luca Motto Ros - 2011 - Journal of Symbolic Logic 76 (1):243 - 266.
Reference to numbers in natural language.Friederike Moltmann - 2013 - Philosophical Studies 162 (3):499 - 536.

Analytics

Added to PP
2013-10-31

Downloads
36 (#385,180)

6 months
5 (#247,092)

Historical graph of downloads
How can I increase my downloads?

Author's Profile