Definition of addition and multiplication on $ℕ$ using recursion

Question

My book, Classic Set Theory: For Guided Independent Study, gives me this theorem:
"let $y_0$ be any element of $ℕ$ and $h"ℕ×ℕ×→ℕ$ a function on pairs $(x,y)∈ℕ×ℕ$. Then there exists a unique function $f:ℕ→ℕ$ such that $f(0)=y_0$ and $f(n^+)=h(n,f(n))$ for all $n∈ℕ$"

($n^+$ is the successor of the number $n$, which in this case, since the natural numbers are defined as sets, is $n^+=n∪\{n\}$)

then it says:

"for defining addition, the trick is to use recursion to define $m+n$ for a fixed $m$ and all $n$. The $f$ in the theorem will be defined so that $f(n)$ is to be regarded as $m+n$. To emphasize this, we shall refer to this $f$ as $f_m$."

then it defines addition in this way:

"$f(0)=m$ and $f_m(n^+)=(f_m(n))^+$

I understand this last part, since $m+n^+=m+n+1=(m+n)+1=(m+n)^+$, but i don't understand what $h(n,f(n))$ is.

It gives also this exercise (you don't need to read this part, but maybe it can help you answering the question), which i actually dont understand..

"Define $h(x,y)$ so that $f_m(n^+)=h(m,f_m(n))$"
the solution is:
"$h(x,y)=y^+$"
(which comes from the definition above: $f(n^+)=h(n,f(n))$ but since $f_m(n^+)=(f_m(n))^+$ we have $h(n,f(n))=(f_m(n))^+$)

what i dont get about this excercise is the first "$m$" in $h(m,f_m(n))$, i don't know if this is a typo or not, what i thought is that since $m$ is fixed and in the theorem it says "for all $n$" you can write it like that, but it doesn't really makes sense since in $h$, $n$ appears multiple times you have to replace it throughout the equation.

If it can be useful, multiplication is defined using the definition of addition and that theorem as $f_m(0)=0$ and $f_m(n^+)=f_m(n)+m$ where $f_m(n)$ means $m·n$

Could you guys help me out please? Could you tell me what $h(n,f(n))$ means in the definition of addition (and if you want also multiplication)?

Answer 1

First, the Theorem you gave is a particular case of the Recursion theorem

let E be a set. if there exists $x_0\in E$ and $h:E\to E,$ then there exists a unique $f: \Bbb N\to E$ by $f(0)=x_0$ and $f(n^+)=h(f(n))$.

Notice that there exists $S:\Bbb N\to \Bbb N$ by $S(n)=n^+ \forall n\in \Bbb N.$ (the succession)

For any $m \in \Bbb N$. Addition to $m$ is usually defined as $f_m:\Bbb N\to \Bbb N$ by $f_m(0)=m$ and $f_m(n^+)=S(f_m(n))=f_m(n)^+$ (i.e $m+0=m, m+1=m+1, m+2=(m+1)+1.... )$

In your book, the author defined $h:\Bbb N\times \Bbb N\to \Bbb N$ by $h(n,f(n))=f(n)^+\forall n$, which uses $\Bbb N\times \Bbb N$ as the domain to keep track of $n$, instead of just $\Bbb N$. I think it is not necessary, and $S$ defined above is good enugh.

For multiplication to $m$:

there exists $M_m:\Bbb N\to \Bbb N$ by $M(n)=n+m$ (as $+$ is defined above)

Multiplication is defined as $g:\Bbb N\to \Bbb N$ by $g_m(0)=0$ and $g_m(n^+)=M(g_m(n))=g_m(n)+m$ $(m\times 0=0, m\times 1=(m\times0)+m, m\times 2=(m\times1)+m...$)

Answer 2

$h$ is just some function. It poses no conditions on the arguments that you can pass to it (other than their domain). This function is defined on $\mathbb{N}\times\mathbb{N}$.

Now, the theorem states that every such function $h$ can be defined recursively as some function $f : \mathbb{N}\to\mathbb{N}$, where the recursive call $f(n^+)$ is handled by $h(n, f(n))$. In other words, $h$ contains the recipe of how to calculate $f(n^+)$ from $n$ and $f(n)$.

Regarding the exercise, it could be a typo, but it doesn't really matter. The assignment gives you a function $f_m$ and asks you to find the recipe ($h$) for the recursive case in terms of $m$ and $f_m(n)$. Because the recipe drops the first argument $m$ and only uses the second argument $f_m(n)$, it doesn't matter whether the first argument is $m$ or $n$ or some other number.

Suppose it's not a typo. We have a fixed number $m$ (it is not a variable, because it's fixed), a function $f_m:\mathbb{N}\to\mathbb{N}$, and a function $h:\mathbb{N}\times\mathbb{N}\to\mathbb{N}$. $h$ needs two arguments and the exercise requires that the first argument is always the fixed $m$. Then, in the context of this fixed $m$, you can consider some $h':\mathbb{N}\to\mathbb{N}$ such that $h'(x) = h(m,x)$ and work with $h'$. Or better, you can define $h':\mathbb{N}\times\mathbb{N}\to\mathbb{N}$ such that $h'(n,y) = h(m,y)$. Then, $h'$ fits the formulas and requirements of the theorem.