Terminology: arithmetic vs. expressible vs. represented

A function $$f:\mathbb{N}^k\rightarrow\mathbb{N}$$ is arithmetic iff its graph is arithmetic, i.e., there is a formula $$\psi(\vec{x},y)$$ in the language of Peano arithmetic such that for all $$\vec{a}$$ in $$\mathbb{N}^k$$, $$f(\vec{a})=b$$ iff $$\mathbb{N}\models\psi(\vec{a},b)$$.

For $$f$$ to be represented in PA, we have the (much) stronger condition that for all $$\vec{a}$$ in $$\mathbb{N}^k$$, $$f(\vec{a})=b$$ iff $$\text{PA}\vdash\psi(\vec{a},b)$$.

I'm wondering about an intermediate condition: $$f$$ is arithmetic, and in addition, PA proves that the associated formula defines a function. That is, $$\text{PA}\vdash\forall\vec{x}\,\exists!y\,\psi(\vec{x},y)$$.

Would it be reasonable to call this condition expressible in PA? Or would that conflict with generally accepted terminology?

I'm also assuming that definable in PA is a synonym for arithmetic. But I'm interested in hearing from anyone who doesn't agree with this.

• IMO, the terminology is not very "stable". R.Smullyan (into his G's Incompl Th) uses expressible for the first one (true in...) and representable for the second one (provable in...). – Mauro ALLEGRANZA May 10 at 14:59
• Your condition for "represented" doesn't make sense : what's the connection between $a$ and $x$, $b$ and $y$ ? – Max May 10 at 15:39
• @Max I assume what was meant was $\text{PA}\vdash \psi(\overline{a},b)$. – Alex Kruckman May 10 at 15:52
• @AlexKruckman yes I thought so but at first I had a misconception in my head about what $\mathbb{N}\models \psi(a,b)$ implied about provability in PA, I was thinking in too low complexity of formulas – Max May 10 at 16:00

Your condition is called definable. This is standard usage in model theory: Given a theory $$T$$, a definable function is a formula $$\varphi(\overline{x},y)$$ such that $$T\vdash \forall \overline{x}\, \exists^! y\, \varphi(\overline{x},y)$$, up to provable equivalence in $$T$$. Then for any model $$M\models T$$, $$\{(\overline{a},b)\in M^{n+1}\mid M\models \varphi(\overline{a},b)\}$$ is the graph of a function $$M^n\to M$$ (which we abuse terminology by also calling a definable function).
It would be a big mistake to make "definable in PA" a synonym for "arithmetic". The point is that the definition of arithmetic has nothing to do with the theory PA, it's just about the standard model $$\mathbb{N}$$. On the other hand, the definition of definable has nothing to do with the standard model $$\mathbb{N}$$, it's just about the theory PA. These are totally different concepts.
• OK, thanks. And I guess we would use "definably represented" for the conjunction of those two conditions. (A priori, I can't see why one would imply the other, in general (i.e., for $\psi$ high enough in the hierarchy). – Michael Weiss May 10 at 18:39