3
$\begingroup$

Let $\mathcal C, \mathcal D\subseteq 2^\omega$. Let $$ \DeclareMathOperator{\Either}{Either} \Either(\mathcal C,\mathcal D)=\{A\oplus B: \text{either }A\in \mathcal C, B\in\mathcal D\text{, or }B\in \mathcal C, A\in\mathcal D\} $$ Has this operation been named and studied in the context of Medvedev degrees (i.e., strong reducibility of mass problems)?

Its interest comes from the fact that from an element of $\Either(\mathcal C,\mathcal D)$ we cannot necessarily compute an element of $\mathcal C$ (or $\mathcal D$) uniformly.

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ Note that this isn't Medvedev-degree-invariant: if every element of $\mathcal{C}$ begins with $0$ and every element of $\mathcal{D}$ begins with $1$ then $\mathsf{Either}(\mathcal{C},\mathcal{D})$ is just their join, and every mass problem is Medvedev-equivalent to one with a "common first bit." $\endgroup$
    – Noah Schweber
    Commented Aug 2, 2021 at 1:53
  • $\begingroup$ @NoahSchweber right. I've edited the title accordingly $\endgroup$
    – Bjørn Kjos-Hanssen
    Commented Aug 2, 2021 at 1:58

1 Answer 1

Reset to default
3
$\begingroup$

Kojiro Higuchi and Takayuki Kihara have studied operations of this flavour in their papers "Inside the Muchnik degrees" I+II (doi Part 1,doi Part 2). It has been a few years since I read those, and I do not remember whether this particular operation plays a role. However, the idea of combining sets in ways that foil uniform reductions features very heavily in this work.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Fantastic thanks @Arno $\endgroup$
    – Bjørn Kjos-Hanssen
    Commented Aug 2, 2021 at 16:45
  • $\begingroup$ Lemma 4 of the 2nd paper concerns a closely related operation. $\endgroup$
    – Bjørn Kjos-Hanssen
    Commented Aug 2, 2021 at 17:47

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .