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.

  • $\begingroup$ 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...). $\endgroup$ – Mauro ALLEGRANZA May 10 at 14:59
  • $\begingroup$ Your condition for "represented" doesn't make sense : what's the connection between $a$ and $x$, $b$ and $y$ ? $\endgroup$ – Max May 10 at 15:39
  • $\begingroup$ @Max I assume what was meant was $\text{PA}\vdash \psi(\overline{a},b)$. $\endgroup$ – Alex Kruckman May 10 at 15:52
  • $\begingroup$ @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 $\endgroup$ – 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.

  • $\begingroup$ 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). $\endgroup$ – Michael Weiss May 10 at 18:39
  • $\begingroup$ @MichaelWeiss Sure, that sounds like reasonable terminology. I agree that it doesn't seem like definable and represented are comparable notions, though I don't have counterexamples in mind). $\endgroup$ – Alex Kruckman May 10 at 18:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.