Skip to main content
added 444 characters in body
Source Link
Jing Zhang
  • 3k
  • 1
  • 17
  • 15

Over any model M of $PA^-+I\Sigma_1^0$. Suppose $A\in [T]$ where $T$ is a $\Delta_2^0$-tree and $A$ is one isolated path. Further, $A$ is regular, i.e. $\forall n A\upharpoonright n$ has a code in $M$. A is easily seen to be $\Delta_2^0$. My question is does there exist a nice recursive approximation $\langle A_s\rangle$ of A such that $\forall n \exists t \forall s>t A_s\upharpoonright n =A\upharpoonright n$? This property could be expected for any $\Delta_2^0$ set in any $PA^-+B\Sigma_2^0$ model. However, I'm wondering if being an isolated path is enough restriction to force this nice property in $PA^-+I\Sigma_1^0$.

Edit: There might be some further restriction on the tree that I left out. Otherwise as François pointed out the restriction is vacuous. Let's say $T=\{\tau\in 2^{<M}: \forall u< |\tau| K(\tau\upharpoonright u)<K(u)+b\}$ where $K$ is the prefix-free Kolmogorov Complexity (it could be defined in models of fragments of arithmetic) and b is a constant. Actually, it corresponds to the K-trivial set via constant $b$ as in the standard case.

Over any model M of $PA^-+I\Sigma_1^0$. Suppose $A\in [T]$ where $T$ is a $\Delta_2^0$-tree and $A$ is one isolated path. Further, $A$ is regular, i.e. $\forall n A\upharpoonright n$ has a code in $M$. A is easily seen to be $\Delta_2^0$. My question is does there exist a nice recursive approximation $\langle A_s\rangle$ of A such that $\forall n \exists t \forall s>t A_s\upharpoonright n =A\upharpoonright n$? This property could be expected for any $\Delta_2^0$ set in any $PA^-+B\Sigma_2^0$ model. However, I'm wondering if being an isolated path is enough restriction to force this nice property in $PA^-+I\Sigma_1^0$.

Over any model M of $PA^-+I\Sigma_1^0$. Suppose $A\in [T]$ where $T$ is a $\Delta_2^0$-tree and $A$ is one isolated path. Further, $A$ is regular, i.e. $\forall n A\upharpoonright n$ has a code in $M$. A is easily seen to be $\Delta_2^0$. My question is does there exist a nice recursive approximation $\langle A_s\rangle$ of A such that $\forall n \exists t \forall s>t A_s\upharpoonright n =A\upharpoonright n$? This property could be expected for any $\Delta_2^0$ set in any $PA^-+B\Sigma_2^0$ model. However, I'm wondering if being an isolated path is enough restriction to force this nice property in $PA^-+I\Sigma_1^0$.

Edit: There might be some further restriction on the tree that I left out. Otherwise as François pointed out the restriction is vacuous. Let's say $T=\{\tau\in 2^{<M}: \forall u< |\tau| K(\tau\upharpoonright u)<K(u)+b\}$ where $K$ is the prefix-free Kolmogorov Complexity (it could be defined in models of fragments of arithmetic) and b is a constant. Actually, it corresponds to the K-trivial set via constant $b$ as in the standard case.

Source Link
Jing Zhang
  • 3k
  • 1
  • 17
  • 15

Stabilization of recursive approximation in $PA^-+I\Sigma_1^0$

Over any model M of $PA^-+I\Sigma_1^0$. Suppose $A\in [T]$ where $T$ is a $\Delta_2^0$-tree and $A$ is one isolated path. Further, $A$ is regular, i.e. $\forall n A\upharpoonright n$ has a code in $M$. A is easily seen to be $\Delta_2^0$. My question is does there exist a nice recursive approximation $\langle A_s\rangle$ of A such that $\forall n \exists t \forall s>t A_s\upharpoonright n =A\upharpoonright n$? This property could be expected for any $\Delta_2^0$ set in any $PA^-+B\Sigma_2^0$ model. However, I'm wondering if being an isolated path is enough restriction to force this nice property in $PA^-+I\Sigma_1^0$.