Computability and the Symmetric Difference Operator

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...

Full description

Saved in:
Bibliographic Details
Published in:Logic journal of the IGPL 2022-05, Vol.30 (3), p.499-518
Main Authors: Andrews, Uri, Gerdes, Peter M, Lempp, Steffen, Miller, Joseph S, Schweber, Noah D
Format: Article
Language:English
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:1367-0751
1368-9894
DOI:10.1093/jigpal/jzab017