Skip to main content
edited title
Link
Bjørn Kjos-Hanssen
  • 24.8k
  • 3
  • 58
  • 114

Join-like operation inand Medvedev degreesreducibility

Source Link
Bjørn Kjos-Hanssen
  • 24.8k
  • 3
  • 58
  • 114

Join-like operation in Medvedev degrees

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.