Computability and the Symmetric Difference Operator. (8th June 2021)

• Record Type: Journal Article
• Authors: Andrews, Uri; Gerdes, Peter M; Lempp, Steffen; Miller, Joseph S; Schweber, Noah D
• Is Part Of: Logic journal of the IGPL. Volume 30:Number 3(2022)
• Page Start: 499
• Page End: 518
• Publication Date: 2021-06-08
• Subjects: Turing degrees -- recursively enumerable sets -- symmetric difference -- computability theory -- recursion theory; Logic, Symbolic and mathematical -- Periodicals; 511.3
• DOI: 10.1093/jigpal/jzab017
• Languages: English
• ISSNs: 1367-0751

Abstract

Abstract: Combinatorial operations on sets are almost never well defined on Turing degrees, a fact so obvious that counterexamples are worth exhibiting. The case we focus on is the symmetric-difference operator; there are pairs of (nonzero) degrees for which the symmetric-difference operation is well defined. Some examples can be extracted from the literature, e.g. from the existence of nonzero degrees with strong minimal covers. We focus on the case of incomparable r.e. degrees for which the symmetric-difference operation is well defined.