For mass problems <InlineEquation ID="IEq1"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="153_2025_973_Article_IEq1.gif" Format="GIF" Height="20" Rendition="HTML" Resolution="72" Type="Linedraw" Width="77" /> </InlineMediaObject> <EquationSource Format="TEX">$P,Q\subseteq {\mathbb {N}^\mathbb {N}}$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>P</mi> <mo>,</mo> <mi>Q</mi> <mo>⊆</mo> <msup> <mrow> <mi mathvariant="double-struck">N</mi> </mrow> <mi mathvariant="double-struck">N</mi> </msup> </mrow> </math></EquationSource> </InlineEquation> (Baire space), P is Medvedev reducible to Q (<InlineEquation ID="IEq2"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="153_2025_973_Article_IEq2.gif" Format="GIF" Height="17" Rendition="HTML" Resolution="72" Type="Linedraw" Width="60" /> </InlineMediaObject> <EquationSource Format="TEX">$P\le _sQ$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>P</mi> <msub> <mo>≤</mo> <mi>s</mi> </msub> <mi>Q</mi> </mrow> </math></EquationSource> </InlineEquation>) if for some Turing funcional <InlineEquation ID="IEq3"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="153_2025_973_Article_IEq3.gif" Format="GIF" Height="14" Rendition="HTML" Resolution="72" Type="Linedraw" Width="13" /> </InlineMediaObject> <EquationSource Format="TEX">$\Phi $</EquationSource> <EquationSource Format="MATHML"><math> <mi mathvariant="normal">Φ</mi> </math></EquationSource> </InlineEquation>, <InlineEquation ID="IEq4"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="153_2025_973_Article_IEq4.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="76" /> </InlineMediaObject> <EquationSource Format="TEX">$\Phi (Q)\subseteq P$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi mathvariant="normal">Φ</mi> <mo stretchy="false">(</mo> <mi>Q</mi> <mo stretchy="false">)</mo> <mo>⊆</mo> <mi>P</mi> </mrow> </math></EquationSource> </InlineEquation>, and Medvedev equivalent to Q if also <InlineEquation ID="IEq5"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="153_2025_973_Article_IEq5.gif" Format="GIF" Height="17" Rendition="HTML" Resolution="72" Type="Linedraw" Width="59" /> </InlineMediaObject> <EquationSource Format="TEX">$Q\le _sP$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>Q</mi> <msub> <mo>≤</mo> <mi>s</mi> </msub> <mi>P</mi> </mrow> </math></EquationSource> </InlineEquation>. Shafer asked if every closed problem P is Medvedev equivalent to a closed problem Q with <InlineEquation ID="IEq6"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="153_2025_973_Article_IEq6.gif" Format="GIF" Height="20" Rendition="HTML" Resolution="72" Type="Linedraw" Width="55" /> </InlineMediaObject> <EquationSource Format="TEX">$Q\subseteq 2^\mathbb {N}$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>Q</mi> <mo>⊆</mo> <msup> <mn>2</mn> <mi mathvariant="double-struck">N</mi> </msup> </mrow> </math></EquationSource> </InlineEquation> (Cantor space). We show that this is not the case.

A closed subset of Baire space not Medvedev equivalent to any closed set of Cantor space

期刊论文
发表日期：

2025年4月25日

查看全文

Joshua A. Cole

摘要

For mass problems $P,Q\subseteq {\mathbb {N}^\mathbb {N}}$ $P, Q \subseteq N^{N}$ (Baire space), P is Medvedev reducible to Q ( $P\le _sQ$ $P \leq_{s} Q$ ) if for some Turing funcional $\Phi $ $Φ$ , $\Phi (Q)\subseteq P$ $Φ (Q) \subseteq P$ , and Medvedev equivalent to Q if also $Q\le _sP$ $Q \leq_{s} P$ . Shafer asked if every closed problem P is Medvedev equivalent to a closed problem Q with $Q\subseteq 2^\mathbb {N}$ $Q \subseteq 2^{N}$ (Cantor space). We show that this is not the case.