1
$\begingroup$

Working in $\sf ZFC$ we can define a function $F$ from naturals to naturals such that $F(0) = \, ^\circ\ulcorner r({\sf Z}) \urcorner$, where $r({\sf Z})$ is the Rosser sentence of Zermelo set theory $\sf Z$, and for each $n$ if $F(n)= \, ^\circ \ulcorner r(T) \urcorner$, then $F(n+1)= \, ^\circ \ulcorner r({\sf T}+r({\sf T})) \urcorner$. Where $\ulcorner S \urcorner$ is the Godel number of the sentence $S$, and $^\circ n = {\sf SSS \ldots S_n}(0)$

Is this function definable in $\sf PA$?

If so can $\sf PA$ prove: $\forall x \exists y: F(x)=y$

My point is that the $F$ function is not purely arithmetical one, it is speaking about numbers related to theories of higher consistency strength than $\sf PA$. But $\sf PA$ has the capacity to represent any computable function, and the above is one I suppose. So, can $\sf PA$ speak about functions whose rules are derived in terms of those higher theories?

If No, then this would mean that studying the infinite realm can enable us define functions on the finite world that we cannot otherwise define?

Improve this question
$\endgroup$
2
  • $\begingroup$ I wonder whether the notation $\, ^\circ\ulcorner r({\sf Z}) \urcorner$ rather than $\, ^o\ulcorner r({\sf Z}) \urcorner$ might make more sense? $\endgroup$
    – Michael Hardy
    Commented Jul 18 at 2:58
  • 1
    $\begingroup$ @MichaelHardy, Yes correct. I'll correct it. Thanks $\endgroup$
    – Zuhair Al-Johar
    Commented Jul 18 at 12:30

1 Answer 1

Reset to default
6
$\begingroup$

Yes, this function is obviously definable in PA and PA proves it is total. You are defining the tower of theories by recursion, which PA can do, and taking the Rosser sentence of each theory, which PA can do. The fact that the theories transcend PA in consistency strength poses no obstacle.

Improve this answer
$\endgroup$
2
  • 4
    $\begingroup$ +1. For the OP: remember that every computable function is definable in the language of arithmetic, by a low-quantifier-complexity formula even (this is a consequence of the $\Delta_0$-ness of Kleene's T-predicate, but see also Post's theorem). Provable totality is another matter, but you have to work extremely hard to whip up a function which can't be defined in the language of arithmetic. $\endgroup$
    – Noah Schweber
    Commented Jul 17 at 21:13
  • $\begingroup$ For functions in the "spirit" of the OP, provable totality is really only an issue if we define the function in question so that the behavior of the output sentence is assumed; e.g. letting $T_n$ be the $n$th theory in your hierarchy, "$G(x)$ = the smallest Godel number of a $T_x$-independent sentence" is a perfectly valid PA-definition of a function but PA can't prove that it's total. (Of course, PA can prove the totality of "$H(x) = F(x)$ if $T_x$ is consistent and 7 otherwise." No mystery here: these two definitions are externally, but not PA-provably, equivalent.) $\endgroup$
    – Noah Schweber
    Commented Jul 17 at 21:17

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .