2
$\begingroup$

I am very confused about the "role of the hyperoperations" in the peano arithmetic.

For example addition's and multiplication's axioms are given.

$A_1$ $\forall x(x+0=x)$

$A_2$ $\forall xy(x+ S(y)=S(x+y))$

$M_1$ $\forall x(x\times0=0)$

$M_2$ $\forall xy(x\times S(y)=x+(x\times y))$

with multiplication we can define exponentiation

$E_1$ $\forall x(x^0=1)$

$E_2$ $\forall xy(x^{ S(y)}=x\times(x^ y))$

...

$\mathcal Q_1$ but exponentiation's axioms are not given in $\mathsf{PA}$... why?

My possible ideas are:

  • (1) because in $\mathsf{PA}$ we just don't need (are not interested in) exponentiation or

  • (2) we need it but but addition's and multiplication's axioms are enough to get it.

If the statement (2) is right then why we need multiplication's axioms?

$\mathcal Q_2$ Seems to mee so weird that now I'm starting to think that probably I am missing something about $\mathsf{PA}$ and how axioms and first order theories works...what am I missing?

But if my first interpretation (1) is right and we don't need/have exponentiation in $\mathsf{PA}$ then ...

$\mathcal Q_3$ what we obtain if we add infinite axioms for all the hyperoperations left (higher than multiplication) ?

The axioms are the following

$K_1$ $\forall xy(x \uparrow ^{0}y=x \times y)$

$K_2$ $\forall xz(x\uparrow^{S(z)}0=1)$

$K_3$ $\forall xyz(x\uparrow^{S(z)}S(y)=x\uparrow^{z}(x\uparrow^{S(z)}y))$

$\endgroup$
  • $\begingroup$ $A_*$, $M_*$ are not axioms of $\mathsf {PA}$. These are. $\endgroup$ – Karolis Juodelė Mar 5 '14 at 15:52
  • $\begingroup$ Sorry @KarolisJuodelė but if I go in the section "first order theory of arithmetic" i can see 7 axioms (6+induction schema) and axiom 3,4,5 and 6 are exatly the definition of addition and multiplication, those are not Peano Arithmetic's axioms? $\endgroup$ – MphLee Mar 5 '14 at 16:23
4
$\begingroup$

Every recursive function is representable in Peano Arithmetic. Roughly speaking this means that for every recursive function $f(x_1,x_2,\dots,x_n)$, there is a formula $F_f(y,x_1,x_2,\dots,x_n)$ such that $F_f(y,x_1,x_2,\dots,x_n)$ "says" that $y=f(x_1,x_2,\dots,x_n)$. Somewhat more precisely, for any natural numbers $b,a_1,a_2,\dots,a_n$, the sentence $F_f(\bar{b},\bar{a}_1,\bar{a}_2,\dots,\bar{a}_n)$ is provable if and only if $b=f(a_1,a_2,\dots,a_n)$. Here $\bar{b}$, $\bar{a}_i$ are the formal expressions corresponding to $b$, $a_i$. These are successor function applied the appropriate number of times to the constant symbol $\bar{0}$.

Additionally, in Peano Arithmetic it is a theorem that for every $x_1,x_2,\dots,x_n$ there is a unique $y$ such that $F_f(y,x_1,x_2,\dots,x_n)$. There are always infinitely many $F_f$ that "represent" the function $f$.

Exponentiation is a recursive function, you have essentially given a recursive description of it. Thus exponentiation is representable in PA. So are the other hyperoperations mentioned in the question.

The corresponding result is false if we start only with addition. Multiplication is not representable in the resulting theory, which is usually called Presburger Arithmetic.

$\endgroup$
  • $\begingroup$ Thanks! Now is all bit more clear for me but why multiplication is so special? Why without it we can't "represent" the other recursive functions? after all multiplication is recursively defined from addition. Maybe two initial operations is the smaller number of basic operations needed to "build" all the others r.functions? If yes then what happens if we replace multiplication's axioms with two axioms of another recursive function obtained by recursion from $S$ and $+$? it will be equivalent? $\endgroup$ – MphLee Mar 5 '14 at 20:47
  • $\begingroup$ There are other other basic operations and/or predicates one could start from. One can replace multiplication by the simpler operation of squaring. It seems likely to me that one can replace the combo addition, multiplication by a single operation. It would be fairly harmless if addition, multiplication were not enough (but they are) as long as we have an explicit single axiomatized theory. (We certainly don't want to modify our basic theory each time we decide to study a new number-theoretic function.) And representability is a basic tool in the proof of the Incompleteness Theorem. $\endgroup$ – André Nicolas Mar 5 '14 at 21:08

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.