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

frabala · Answer

$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}timesmathbb{N}$.
Now, the theorem states that every such function $h$ can be defined recursively as some function $f : mathbb{N}tomathbb{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}tomathbb{N}$, and a function $h:mathbb{N}timesmathbb{N}tomathbb{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}tomathbb{N}$ such that $h'(x) = h(m,x)$ and work with $h'$. Or better, you can define $h':mathbb{N}timesmathbb{N}tomathbb{N}$ such that $h'(n,y) = h(m,y)$. Then, $h'$ fits the formulas and requirements of the theorem.

xyz · Answer

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

let E be a set. if there exists $x_0in E$ and $h:Eto E,$ then there exists a unique $f: Bbb Nto E$ by $f(0)=x_0$ and $f(n^+)=h(f(n))$.

Notice that there exists $S:Bbb Nto Bbb N$ by $S(n)=n^+ forall nin Bbb N.$ (the succession)
For any $m in Bbb N$. Addition to $m$ is usually defined as $f_m:Bbb Nto 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 Ntimes Bbb Nto Bbb N$ by $h(n,f(n))=f(n)^+forall n$, which uses $Bbb Ntimes 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 Nto Bbb N$ by $M(n)=n+m$ (as $+$ is defined above)
Multiplication is defined as $g:Bbb Nto Bbb N$ by $g_m(0)=0$ and $g_m(n^+)=M(g_m(n))=g_m(n)+m$ $(mtimes 0=0, mtimes 1=(mtimes0)+m, mtimes 2=(mtimes1)+m...$)

Definition of addition and multiplication on $ℕ$ using recursion

2 Answers

Add your own answers!

Ask a Question