Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question

2 Answers 2

up vote 2 down vote accepted

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.

share|improve this answer

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.

share|improve this answer
    
Oh, alright. I have to read into that.. –  user35359 Feb 3 '13 at 12:49

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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