Skip to main content
added 413 characters in body
Source Link
Eric
  • 2.6k
  • 1
  • 23
  • 25

A total recursive function $f(x)$ is provably total in $PA$ if there's some formula $\phi(x,y)$ such that

  1. $f(x)=y \iff PA\vdash \phi(x,y)$ and
  2. $PA\vdash \forall x \exists y \phi(x,y)$

I know (not in much detail) that a total recursive function is not provably total if it grows as fast as/faster than $f_{\epsilon_0}$ in a fast growing hierarchy, where $\epsilon_0=\omega^{\omega^{\omega^....}}$ (the Goodstein sequence would be an example). My question is, is the converse also true, i.e., every total recursive function dominated by $f_{\epsilon_0}$ is provably total in $PA$?


Edit: By Gro-Tsen's comment and Henry's answer, I know the answer to my above question is (almost trivially) no ... But if I strength my requirement a bit, and consider a total recursive function $f_\alpha$ with $\alpha<\epsilon_0$. If the fundamental sequences here leading up to $\epsilon_0$ are computable, is $f_\alpha$ guarantee to be provably total then? And how do we prove (or disprove) it?

A total recursive function $f(x)$ is provably total in $PA$ if there's some formula $\phi(x,y)$ such that

  1. $f(x)=y \iff PA\vdash \phi(x,y)$ and
  2. $PA\vdash \forall x \exists y \phi(x,y)$

I know (not in much detail) that a total recursive function is not provably total if it grows as fast as/faster than $f_{\epsilon_0}$ in a fast growing hierarchy, where $\epsilon_0=\omega^{\omega^{\omega^....}}$ (the Goodstein sequence would be an example). My question is, is the converse also true, i.e., every total recursive function dominated by $f_{\epsilon_0}$ is provably total in $PA$?

A total recursive function $f(x)$ is provably total in $PA$ if there's some formula $\phi(x,y)$ such that

  1. $f(x)=y \iff PA\vdash \phi(x,y)$ and
  2. $PA\vdash \forall x \exists y \phi(x,y)$

I know (not in much detail) that a total recursive function is not provably total if it grows as fast as/faster than $f_{\epsilon_0}$ in a fast growing hierarchy, where $\epsilon_0=\omega^{\omega^{\omega^....}}$ (the Goodstein sequence would be an example). My question is, is the converse also true, i.e., every total recursive function dominated by $f_{\epsilon_0}$ is provably total in $PA$?


Edit: By Gro-Tsen's comment and Henry's answer, I know the answer to my above question is (almost trivially) no ... But if I strength my requirement a bit, and consider a total recursive function $f_\alpha$ with $\alpha<\epsilon_0$. If the fundamental sequences here leading up to $\epsilon_0$ are computable, is $f_\alpha$ guarantee to be provably total then? And how do we prove (or disprove) it?

added 45 characters in body
Source Link
Eric
  • 2.6k
  • 1
  • 23
  • 25

A total recursive function $f(x)$ is provably total in $PA$ if there's some formula $\phi(x,y)$ such that

  1. $f(x)=y \iff PA\vdash \phi(x,y)$ and
  2. $PA\vdash \forall x \exists y \phi(x,y)$

I know (not in much detail) that a total recursive function is not provably total if it grows as fast as/faster than $f_{\epsilon_0}$ in a fast growing hierarchy, where $\epsilon_0=\omega^{\omega^{\omega^....}}$ (the Goodstein sequence would be an example). My question is, is the converse also true, i.e., every total recursive function dominated by $f_{\epsilon_0}$ is provably total in $PA$?

A total recursive function $f(x)$ is provably total in $PA$ if there's some formula $\phi(x,y)$ such that

  1. $f(x)=y \iff PA\vdash \phi(x,y)$ and
  2. $PA\vdash \forall x \exists y \phi(x,y)$

I know (not in much detail) that a total recursive function is not provably total if it grows as fast as/faster than $f_{\epsilon_0}$ in a fast growing hierarchy, where $\epsilon_0=\omega^{\omega^{\omega^....}}$. My question is, is the converse also true, i.e., every total recursive function dominated by $f_{\epsilon_0}$ is provably total in $PA$?

A total recursive function $f(x)$ is provably total in $PA$ if there's some formula $\phi(x,y)$ such that

  1. $f(x)=y \iff PA\vdash \phi(x,y)$ and
  2. $PA\vdash \forall x \exists y \phi(x,y)$

I know (not in much detail) that a total recursive function is not provably total if it grows as fast as/faster than $f_{\epsilon_0}$ in a fast growing hierarchy, where $\epsilon_0=\omega^{\omega^{\omega^....}}$ (the Goodstein sequence would be an example). My question is, is the converse also true, i.e., every total recursive function dominated by $f_{\epsilon_0}$ is provably total in $PA$?

Source Link
Eric
  • 2.6k
  • 1
  • 23
  • 25

$f_{\epsilon_0}$ and provably total functions in $PA$

A total recursive function $f(x)$ is provably total in $PA$ if there's some formula $\phi(x,y)$ such that

  1. $f(x)=y \iff PA\vdash \phi(x,y)$ and
  2. $PA\vdash \forall x \exists y \phi(x,y)$

I know (not in much detail) that a total recursive function is not provably total if it grows as fast as/faster than $f_{\epsilon_0}$ in a fast growing hierarchy, where $\epsilon_0=\omega^{\omega^{\omega^....}}$. My question is, is the converse also true, i.e., every total recursive function dominated by $f_{\epsilon_0}$ is provably total in $PA$?