I am self-studying a course on logic during the summer, and I have a question relating to formulations in my textbook. The section is about recursive definitions, and the construction of $\mathbb{N}$, using the successor function $s$, has just been explained. The examples define addition, multiplication and exponentiation, recursively on $\mathbb{N}$. The following are quotes from the book:
Addition is defined in a similar manner, in two cases:
$\begin{gather}a+0:=a\\ a+s(n):=s(a+n)\end{gather}$
Addition occurs on the right side of [the second case above]. One therefore says that the definition is "recursive".
Note: $s:\mathbb{N}\to\mathbb{N}$, is the successor function.
Further down, one can read:
The definition of [multiplication] brings nothing new, except that one can choose to have the recursion in the first argument, if one wants to:
$\begin{gather}0\cdot a:=0\\ s(n)\cdot a:=(n\cdot a)+a\end{gather}$
In the definition of exponentiation, the recursion has to occur in the second argument:
$\begin{gather}a^0:=1\\ a^{s(n)}:=a^n\cdot a\end{gather}$
Question(s): What is meant by the statements "one can choose to have the recursion in the first argument, if one wants to" and "In the definition of exponentiation, the recursion has to occur in the second argument"? Also, how could we define it differently, so that the def. of $\cdot$ has the recursion in the first/second argument? What exactly is meant by 'argument' here?
Thoughts: If they are referring to the arguments of the binary operations of $+$ and $\cdot$, both definitions have the recursion in the first argument, no? I do not see what makes the two definitions different (in the way they are suggesting). As I've understood it, the recursion takes place at "$(n\cdot a)$" and at "$a^n$", does it not?
The question is which argument (= variable input) is being "broken down" in the recursive definition.
For instance, here's another way to define multiplication recursively:
$a\cdot 0=0$,
$a\cdot s(x)=a\cdot x+a$.
To compute $3\cdot 2$, we'd break down the second argument (in this case, "$2$"): $$3\cdot 2=3\cdot s(s(0))=3\cdot s(0)+3=3\cdot 0+3+3=0+3+3=6.$$
This is the issue with recursive definitions: the variables have to line up appropriately, so that we can in fact evaluate expressions by breaking them down into simpler ones, and eventually arriving at a "base case" (like $a\cdot 0$) which we understand.
By the way, note that in the last equality, we use $a\cdot 0=0$ - but $0\cdot a=0$ wouldn't obviously (in fact, provably wouldn't) get the job done! The $0$ in the base case has to be in the same place as the "breaking down" (= recursing) variable.
Both multiplication and addition "split nicely on both sides" - e.g. $s(a)+b=a+s(b)=s(a+b)$, and similarly with $\cdot$. So we can use either the first or the second variable as our recursing variable.
Now what about exponentiation?
Well, we want to give a recursive definition of $exp(a,b)$. Such a definition has a base case and a successor case (recursion is to constructions what induction is to proofs). We have two basic options:
Recursion on the first variable: $exp(0, b)=?$,$\quad exp(s(a), b)=?$.
Recursion on the second variable: $exp(b,0)=?$,$\quad exp(b, s(a))=?$.
Three of these expressions are easy to evaluate, and we get:
Recursion on the first variable: $exp(0, b)=0$,$\quad exp(s(a), b)={\color{red}?}$.
Recursion on the second variable: $exp(b,0)=1$,$\quad exp(b, s(a))=exp(b, a)\cdot b$.
But there's no good way to simplifty $(a+1)^b$! So while recursion on the second variable has a perfectly nice form, recursion on the first variable in this case runs into serious problems. (I'm not saying these problems are insurmountable - we could get around this by being a bit clever with binomial coefficients and division - but this shows that recursion on the second variable is clearly the best way to define exponentiation recursively.)