Definabilty of two functions on natural numbers

Question

Is there a first order logic arithmetic ($0,+,\cdot$) formula $f(n,m)$ such that $f(n,m)$ is true in $\mathbb{N}$ iff $m$ is the $n$th prime number? Similarly, is there $g(k,n,m)$ which is equivalent to $k^n=m$ ?

I have no clue, but I suppose this could potentially be difficult to answer.

Answer 1

I assume that you mean the signature $(0, +, \cdot, =)$, so that there is at least one relation symbol. The answer is that the things in the question are definable, and this is well known.

First, let's recover the language of Peano arithmetic. In the signature of the question, we can define:

• the order relations: $x < y$ if and only if $x \not = y$ and $(\exists z)[z+x=y]$
• the successor function: $x = S(y)$ if and only if $x < y$ and $\lnot (\exists z)[x < z \land z < y]$
• the number $1$, which is $S(0)$.

So we may as well assume we have the "full" signature of Peano arithmetic, $(0, 1, S, +, \cdot, <, =)$.

The collection of functions and relations definable on the natural numbers with this signature is described by the arithmetical hierarchy. In particular, it includes all computable functions on the natural numbers. Both of the functions/relations mentioned in the question are computable, so they are definable. But many non-computable functions and relations are also definable.

The main technical step in showing that all computable functions can be defined is showing that it is possible to quantify over finite sequences of natural numbers. One standard way of doing this goes through the β function developed by Gödel for this purpose.

Answer 2

Yes there is. For every recursive function $f(x_1,\dots,x_n)$, there is a formula $\varphi(y,x_1,\dots,x_n)$ of arithmetic such that for any non-negative integers $b,a_1,\dots,a_n$, we have

(i) If $f(a_1,\dots,a_n)=b$, then the formula $\varphi(b,a_1,\dots,a_n)$ is provable in (say) first-order Peano Arithmetic.

(ii) If $f(a_1,\dots,a_n)\ne b$, the negation of $\varphi(b,a_1,\dots,a_n)$ is provable in (say) first-order Peano Arithmetic.

First-order Peano Arithmetic can be replaced here by substantially weaker theories.

The formula $\varphi$ is called a representing formula for $f$,

I have been a little sloppy. We cannot put numbers into formulas. So in $\varphi(b,a_1,\dots,a_n)$, we should, if for example $b=3$, replace $b$ by the formal term $(1+1)+1$.

The representability result is crucial for the proof that first-order Peano arithmetic is undecidable.