What does elementary function arithmetic without the induction axiom tell us about the exponential function?

291 Views Asked by At

We can extend Robinson arithmetic (Q) to include exponentiation, using the axioms

1) $x^0=1$ and 2) $x^{S(n)} = x^n*x$. Wiki page

How much can this extension actually say about exponentiation? Because Robinson arithmetic is not associative or commutative, it doesn't seem like proving $x^{a+b} = x^ax^b$ or $(x^a)^b = x^{ab}$ are possible, both of which seem pretty fundamental when it comes to the exponential function.

In fact, I don't even think that proving $x^1 = x$ is possible:

$x^1 = x^{S(0)}*x = 1*x$, but Robinson arithmetic only proves that $x*1 = x$, not that $1*x = x$. I suppose this could be fixed by altering axiom 2), but that still wouldn't solve the other problems.

I know that Q is weak, but these extra two axioms seem so weak and so bad at capturing exponentiation that it just doesn't even seem worth discussing. Am I missing something?

1

There are 1 best solutions below

2
On BEST ANSWER

Your definition of EFA is missing a crucial component. EFA consists of $Q$, the axioms for exponentiation, and induction for formulas with bounded quantifiers. By contrast, $Q$ contains no induction at all, and $PA$ consists of $Q$ together with full induction.

As soon as we add induction to $Q$ - even a small amount of induction, like induction for bounded-quantifier formulas - we get a much more powerful system. In particular, the basic arithmetic facts which $Q$ curiously can't prove tend to be provable from bounded-quantifier induction. It's also worth noting that bounded-quantifier induction in the language including exponentiation is stronger than bounded-quantifier induction in the language of $Q$ alone; that is, EFA is not conservative over the theory $Q$ + induction for bounded-quantifier formulas in the language of $Q$.


For example, here's how to show that $1*x=x$ using bounded-quantifier induction:

There's a slight language-mismatch here. EFA as described has a symbol "$1$" not present in the language of $Q$, and does not contain the symbol "$S$" which is present in the language of $Q$. So the description in the wiki page is a little bit inexact. But we can always replace "$1$" with "$S(0)$" and replace "$S(x)$" with "$1+x$," so we might as well assume we have both $1$ and $S$ to work with.

  • We have $x*0=0$ as an axiom in $Q$, so in particular we have $1*0=0$.

  • Now suppose $1*x=x$. Then $1*(S(x))=(1*x)+1=x+1=S(x).$ Note that "$x+1=S(x)$" really is the right thing to say here: treating "$1$" as an abbreviation for "$S(0)$," the statement "$x+S(0)=S(x)$" is provable in $Q$.

  • The formula $\varphi(x)\equiv$ "$1*x=x$" is a bounded-quantifier formula, so applying bounded-quantifier induction to the above two bullets we get $\forall x\varphi(x)$, and we're done.