Meaning of Provable recursiveness

47 Views Asked by At

Is there any difference between provably total function and provable recursiveness of a function in first order PA ?

From provably total I mean that the totality of the function itself is provable in the theory... I know this is true of every total recursive function in PA , it can prove the totality of a given total recursive function..

But I get confuse with the term provable recursiveness when reading about it in Stanford Plato website...

1

There are 1 best solutions below

2
On

There is some variance of usage, but usually "provably total" and "provably recursive" are indeed synonymous. That said, this old answer of mine for a case where they aren't! Always check the precise definition in your source. Basically, the key point is that we usually restrict attention to "low-complexity" defining formulas, which prevent a silly trick from making all total recursive functions provably total via "pathological" definitions.

That said, there's a fundamental error in your question:

"I know this is true of every total recursive function in PA"

This is false, at least when we restrict attention to low-complexity definitions (which is usually done per the above): any total recursive function $f$ is (strongly) representable in PA, but that does not mean that PA can prove that $f$ is total. All PA can do is prove, for each specific $n$, that $f(n)$ is defined; PA cannot in general prove "For all $n$, $f(n)$ is defined." (This is exactly analogous to how PA can prove, for each specific $n$, that there is no contradiction in PA involving at most $n$ symbols, but PA cannot prove "For all $n$ there is no contradiction in PA involving at most $n$ symbols.")