Agreement reducibility. Issue 4 (15th January 2021)

• Record Type: Journal Article
• Authors: Epstein, Rachel; Lange, Karen
• Is Part Of: Mathematical logic quarterly. Volume 66:Issue 4(2020)
• Page Start: 448
• Page End: 465
• Publication Date: 2021-01-15
• Subjects: Mathematics -- Periodicals; Logic, Symbolic and mathematical -- Periodicals; 511.3
• DOI: 10.1002/malq.201900088
• Languages: English
• ISSNs: 0942-5616

Abstract

Abstract: We introduce agreement reducibility and highlight its major features. Given subsets A and B of N, we write A ≤ agree B if there is a total computable function f : N → N satisfying for all e, e ′, W e ∩ A = W e ′ ∩ A if and only if W f ( e ) ∩ B = W f ( e ′ ) ∩ B . We shall discuss the central role N plays in this reducibility and its connection to strong‐hyper‐hyper‐immunity. We shall also compare agreement reducibility to other well‐known reducibilities, in particular s1 ‐ and s‐reducibility. We came upon this reducibility while studying the computable reducibility of a class of equivalence relations on N based on set‐agreement. We end by describing the origin of agreement reducibility and presenting some results in that context.