0
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Even if you use $(1 + a)^n = 1 + na + {n \choose 2} a^2 + {n \choose 3} a^3 \dots$, you have to define an auxiliary function to compute ${n \choose k}$. Although I can't prove it off the top of my head, it seems likely that ${n \choose k}$ can't be defined without recurring on $n$. At some point, even with auxiliary functions, you'll have to make a recursion call on $(n - 1)$. Not to mention the sum itself recurs on $n$. $\endgroup$ – DanielV Jun 23 '17 at 6:49
2
$\begingroup$

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.)

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Well, this makes it much clearer, I should've figured, simple as it was, but I think I was starring at what happened on rhs, i.e. I did not think of the recursion as happening on the arguments per se. so I got confused. Also, I will get used to recursive definitions again soon enough. Thank you for an elaborate and well written answer. $\endgroup$ – Christopher.L Jun 22 '17 at 15:26
  • $\begingroup$ @Christopher.L Thanks! Yeah, one of the things that gets left out a lot (for some reason) when presenting recursive arguments is the bit about recursion happening on a specific variable. Usually the examples that are done in class, in my experience, are commutative functions, which obscure the importance of the variable choice. $\endgroup$ – Noah Schweber Jun 22 '17 at 15:27
  • $\begingroup$ When you say "we could get around this by being a bit clever", are you suggesting that it is possible to define $a^n$ without recurring on $n$? I'd be interested in seeing that. I'll post it as a question if you prefer. (Edit: actually that might be a redundant question since that is what the poster is already asking). $\endgroup$ – DanielV Jun 23 '17 at 6:51
2
$\begingroup$

"one can choose to have the recursion in the first argument, if one wants to"

-> that means that you could also choose to define addition this way:

$0+a := a$

$s(n)+a := s(a+n)$

What exactly is meant by 'argument' here?

$a$ and $n$ are the arguments of the operator $+$ in the expression $a+n$

"In the definition of exponentiation, the recursion has to occur in the second argument"?

It would not work to try to define exponentiation with a formula using $a^n$ to define $(s(a))^n$ (just try if that doesn't seem obvious...)

| cite | improve this answer | |
$\endgroup$

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.