Mathematical logic:

$\_\_\_\_\_\_$

Idea $2\mathrm{.}23[$Inductive function definition$]$

Let S be defined inductively from basis B and some construction rule. to difine a function f on elements of S do the following:

Basis : : Specify the value f$($x$)$ for each x in B

Ind : : For each way an x in S can be obtained from some y$,...$ yn in S$,$ specify how to obtain f$($x$)$ from the values f$($y$1)...$ f$($yn$).$

Clsr : : The closure of S ensures that f is defined for all x in S

$\_\_\_\_\_\_\_\_\_\_\_$

Example $2\mathrm{.}26$

Define the set of strings N over $\backslash$Sigma $=\{0,$s$\}$:

Basis :: $0$ in N

Induction :: If n in N then sn in N

This language is the basis of the formal definition of natural numbers. The constructors are $0$ and the operation of appending the symbol $$s$$ to the left. $($The $$s$$ signifies the $$successor$$ function corresponding to n$+1.)$ Notice that we do not obtain the set $\{0,1,2,3...\}$ but $\{0,$ s$0,$ ss$0,$ sss$0...\},$ which is a kind of unary representation of natural numbers. Notice that, for instance, the strings $00$s$,$ s$0$s$0$ not in N$,$ i$.$e$.,$ N $\backslash$Sigma $*$

using the definistion of N$,$ we can define the plus operation for all n$,$ m in N:

BASIS :: $0+n=n$

IND. :: $s(m)+n=s(m+n)$

It is not obvious that this is the usual addition. For instance, does it hold

that $n+m=m+n?$ We shall verify this in an exercise.

We can use this definition to calculate the sum of two arbitrary natural numbers represented as elements of $N.$ For instance, $2+3$ would be processed as follows:

$ss0+sss0|s(s0+sss0)|ss(0+sss0)|ss(sss0)=ssss0.$

Note that Idea $2\mathrm{.}23$ of inductive function definition is guaranteed to work only when the set is given by a $1-1$ definition. Imagine that we tried to

define a version of the length function in Example $2\mathrm{.}24$ by induction on

the definition in Example $2\mathrm{.}22$ as follows: len$(x)=1$ for xin$,$ while

len$(ps)=$len$(p)+1.$ This would give different $($and hence mutually con$-$

tradictive$)$ values for len$(abc),$ depending on which way we choose to derive

abc. Idea $2\mathrm{.}23$ can be applied also when the definition of the set is not $1-1,$

but then one has to ensure that the function value for every element is inde$-$

pendent from the way it is derived. In the present case, the two equations

len$(x)=1$ and len$(ps)=$len$(p)+$len$(s)$ provide a working definition, but

it takes some reasoning to check that this is indeed the case.

$\_\_\_\_\_\_\_\_\_$

Exercise $1$

$($a$)$ Example $2\mathrm{.}26$ of Michal's book defines the $(+)$ function as a function in two arguments.

Modify Idea $2\mathrm{.}23[$Inductive function definition$]$ to cater for inductive functions in any number of

arguments.

$($b$)$ Using the inductive definition of natural numbers, show that the operation $(+)$ defined in Example

$2\mathrm{.}26$ is commutative, i$.$e$.n+m=m+n$ holds for all $n,$minN.

This requires a nested induction, as:

for all minN,$0+m=m+0$

for all minN,$s(n)+m=m+s(n)$ given that for all minN,$n+m=m+n$

can only be proven using induction.

$($c$)$ Show that $(+)$ on the natural numbers is associative, i$.$e$.,n+(m+p)=(n+m)+p.$