Skip to main content
deleted 83 characters in body
Source Link
Noah Schweber
  • 21.1k
  • 10
  • 110
  • 331

We can modify the proof of the Kreisel/Shoenfield basis theorem (see Theorem 3.7 in Diamondstone/Dzhafarov/Soare):

Let $T\subseteq 2^{<\omega}$ be an infinite binary tree all of whose paths are of PA-degree (this is equivalent to $[T]$, the set of paths through $T$, having top Medvedev degree amongst $\Pi^0_1$ classes). Fix a path $f\in [T]$; we want to find a path $g\in [T]$ with $g<_Tf$.

Consider the following computable $4$-ary tree $S$: a node on $S$ of length $n$ consists of a pair $(\alpha,\beta)$ where $\alpha$ is a node on $T$ of length $n$ and $\beta$ is a binary string of length $n$ such that for each $e<i$ it is not the case that $\Phi_e^\alpha(e)[n]\downarrow=\beta(n)$. Clearly $S$ is infinite, so $S$ has a path $h\le_Tf$$h=(h_0,h_1)\le_Tf$. But the "left part" of $h$$h_0$ is a path through $T$ which does not compute the "right part" ofsuch that $h$$h_0\not\ge_Th_1$, and since that right part is $\le_Tf$$(h_0,h_1)\le_Tf$ we have that the "left part" of $h$ is a path through $T$ not computing $f$$h_0\not\ge_Tf$.

We can modify the proof of the Kreisel/Shoenfield basis theorem (see Theorem 3.7 in Diamondstone/Dzhafarov/Soare):

Let $T\subseteq 2^{<\omega}$ be an infinite binary tree all of whose paths are of PA-degree (this is equivalent to $[T]$, the set of paths through $T$, having top Medvedev degree amongst $\Pi^0_1$ classes). Fix a path $f\in [T]$; we want to find a path $g\in [T]$ with $g<_Tf$.

Consider the following computable $4$-ary tree $S$: a node on $S$ of length $n$ consists of a pair $(\alpha,\beta)$ where $\alpha$ is a node on $T$ of length $n$ and $\beta$ is a binary string of length $n$ such that for each $e<i$ it is not the case that $\Phi_e^\alpha(e)[n]\downarrow=\beta(n)$. Clearly $S$ is infinite, so $S$ has a path $h\le_Tf$. But the "left part" of $h$ is a path through $T$ which does not compute the "right part" of $h$, and since that right part is $\le_Tf$ we have that the "left part" of $h$ is a path through $T$ not computing $f$.

We can modify the proof of the Kreisel/Shoenfield basis theorem (see Theorem 3.7 in Diamondstone/Dzhafarov/Soare):

Let $T\subseteq 2^{<\omega}$ be an infinite binary tree all of whose paths are of PA-degree (this is equivalent to $[T]$, the set of paths through $T$, having top Medvedev degree amongst $\Pi^0_1$ classes). Fix a path $f\in [T]$; we want to find a path $g\in [T]$ with $g<_Tf$.

Consider the following computable $4$-ary tree $S$: a node on $S$ of length $n$ consists of a pair $(\alpha,\beta)$ where $\alpha$ is a node on $T$ of length $n$ and $\beta$ is a binary string of length $n$ such that for each $e<i$ it is not the case that $\Phi_e^\alpha(e)[n]\downarrow=\beta(n)$. Clearly $S$ is infinite, so $S$ has a path $h=(h_0,h_1)\le_Tf$. But $h_0$ is a path through $T$ such that $h_0\not\ge_Th_1$, and since $(h_0,h_1)\le_Tf$ we have that $h_0\not\ge_Tf$.

Source Link
Noah Schweber
  • 21.1k
  • 10
  • 110
  • 331

We can modify the proof of the Kreisel/Shoenfield basis theorem (see Theorem 3.7 in Diamondstone/Dzhafarov/Soare):

Let $T\subseteq 2^{<\omega}$ be an infinite binary tree all of whose paths are of PA-degree (this is equivalent to $[T]$, the set of paths through $T$, having top Medvedev degree amongst $\Pi^0_1$ classes). Fix a path $f\in [T]$; we want to find a path $g\in [T]$ with $g<_Tf$.

Consider the following computable $4$-ary tree $S$: a node on $S$ of length $n$ consists of a pair $(\alpha,\beta)$ where $\alpha$ is a node on $T$ of length $n$ and $\beta$ is a binary string of length $n$ such that for each $e<i$ it is not the case that $\Phi_e^\alpha(e)[n]\downarrow=\beta(n)$. Clearly $S$ is infinite, so $S$ has a path $h\le_Tf$. But the "left part" of $h$ is a path through $T$ which does not compute the "right part" of $h$, and since that right part is $\le_Tf$ we have that the "left part" of $h$ is a path through $T$ not computing $f$.