{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,27]],"date-time":"2026-03-27T05:17:38Z","timestamp":1774588658286,"version":"3.50.1"},"reference-count":25,"publisher":"Wiley","issue":"1-2","license":[{"start":{"date-parts":[[2011,12,9]],"date-time":"2011-12-09T00:00:00Z","timestamp":1323388800000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Mathematical Logic Qtrly"],"published-print":{"date-parts":[[2012,2]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We study the structure of \u03a3<jats:sup>1<\/jats:sup><jats:sub>1<\/jats:sub> equivalence relations on hyperarithmetical subsets of \u03c9 under reducibilities given by hyperarithmetical or computable functions, called h\u2010reducibility and FF\u2010reducibility, respectively. We show that the structure is rich even when one fixes the number of properly <jats:styled-content>\\documentclass{article}\\usepackage{amssymb}\\begin{document}\\pagestyle{empty}$\\Sigma ^1_1\\ \\big ($\\end{document}<jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" xlink:href=\"graphic\/tex2gif-ueqn-1.gif\" xlink:title=\"equation image\"\/><\/jats:styled-content>i.e., \u03a3<jats:sup>1<\/jats:sup><jats:sub>1<\/jats:sub> but not <jats:styled-content>\\documentclass{article}\\usepackage{amssymb}\\begin{document}\\pagestyle{empty}$\\Delta ^1_1\\big )$\\end{document}<jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" xlink:href=\"graphic\/tex2gif-ueqn-2.gif\" xlink:title=\"equation image\"\/><\/jats:styled-content> equivalence classes. We also show the existence of incomparable \u03a3<jats:sup>1<\/jats:sup><jats:sub>1<\/jats:sub> equivalence relations that are complete as subsets of \u03c9 \u00d7 \u03c9 with respect to the corresponding reducibility on sets. We study complete \u03a3<jats:sup>1<\/jats:sup><jats:sub>1<\/jats:sub> equivalence relations (under both reducibilities) and show that existence of infinitely many properly \u03a3<jats:sup>1<\/jats:sup><jats:sub>1<\/jats:sub> equivalence classes that are complete as \u03a3<jats:sup>1<\/jats:sup><jats:sub>1<\/jats:sub> sets (under the corresponding reducibility on sets) is necessary but not sufficient for a relation to be complete in the context of \u03a3<jats:sup>1<\/jats:sup><jats:sub>1<\/jats:sub> equivalence relations.<\/jats:p>","DOI":"10.1002\/malq.201020063","type":"journal-article","created":{"date-parts":[[2011,12,9]],"date-time":"2011-12-09T14:26:32Z","timestamp":1323440792000},"page":"113-124","source":"Crossref","is-referenced-by-count":11,"title":["On \u03a3<sup>1<\/sup><sub>1<\/sub> equivalence relations over the natural numbers"],"prefix":"10.1002","volume":"58","author":[{"given":"Ekaterina B.","family":"Fokina","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sy\u2010David","family":"Friedman","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"311","published-online":{"date-parts":[[2011,12,9]]},"reference":[{"key":"e_1_2_11_2_1","doi-asserted-by":"publisher","DOI":"10.2307\/2273443"},{"key":"e_1_2_11_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.apal.2005.10.002"},{"key":"e_1_2_11_4_1","doi-asserted-by":"publisher","DOI":"10.1023\/B:ALLO.0000048827.30718.2c"},{"key":"e_1_2_11_5_1","doi-asserted-by":"publisher","DOI":"10.2178\/jsl\/1203350796"},{"key":"e_1_2_11_6_1","first-page":"99","volume-title":"Lecture Notes in Computer Science Vol. 5635","author":"Cenzer D.","year":"2009"},{"key":"e_1_2_11_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01673573"},{"key":"e_1_2_11_8_1","volume-title":"Definability and Computability, Siberian School of Algebra and Logic","author":"Ershov Yu. L.","year":"1996"},{"key":"e_1_2_11_9_1","first-page":"198","volume-title":"Lecture Notes in Computer Science Vol. 5635","author":"Fokina E.","year":"2009"},{"key":"e_1_2_11_10_1","article-title":"Isomorphism and bi\u2010embeddability relations on computable structures","author":"Fokina E.","journal-title":"J. Symb. Log."},{"key":"e_1_2_11_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.apal.2009.10.002"},{"key":"e_1_2_11_12_1","doi-asserted-by":"publisher","DOI":"10.2307\/2274750"},{"key":"e_1_2_11_13_1","doi-asserted-by":"publisher","DOI":"10.1201\/9781584887942"},{"key":"e_1_2_11_14_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1010521410739"},{"key":"e_1_2_11_15_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1021758312697"},{"key":"e_1_2_11_16_1","volume-title":"Borel Equivalence Relations. Structure And Classification, University Lecture Series Vol. 44","author":"Kanovei V.","year":"2008"},{"key":"e_1_2_11_17_1","doi-asserted-by":"publisher","DOI":"10.2307\/421088"},{"key":"e_1_2_11_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.apal.2008.06.010"},{"key":"e_1_2_11_19_1","first-page":"326","article-title":"Recursively enumerable many\u2010one degrees","volume":"11","author":"Lachlan A.","year":"1972","journal-title":"Algebra Log."},{"key":"e_1_2_11_20_1","doi-asserted-by":"publisher","DOI":"10.1002\/malq.19870330106"},{"key":"e_1_2_11_21_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9939-1994-1169042-2"},{"key":"e_1_2_11_22_1","doi-asserted-by":"publisher","DOI":"10.2178\/bsl\/1174668219"},{"key":"e_1_2_11_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10469-007-0016-0"},{"key":"e_1_2_11_24_1","volume-title":"Theory of Recursive Functions and Effective Computability","author":"Rogers H.","year":"1967"},{"key":"e_1_2_11_25_1","volume-title":"Higher Recursion Theory. Perspectives in Mathematical Logic","author":"Sacks G.","year":"1989"},{"key":"e_1_2_11_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-02460-7"}],"container-title":["Mathematical Logic Quarterly"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Fmalq.201020063","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Fmalq.201020063","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/malq.201020063","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,8,31]],"date-time":"2023-08-31T16:54:17Z","timestamp":1693500857000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/malq.201020063"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,12,9]]},"references-count":25,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2012,2]]}},"alternative-id":["10.1002\/malq.201020063"],"URL":"https:\/\/doi.org\/10.1002\/malq.201020063","archive":["Portico"],"relation":{},"ISSN":["0942-5616","1521-3870"],"issn-type":[{"value":"0942-5616","type":"print"},{"value":"1521-3870","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011,12,9]]}}}