Give a recursive definition


m,n subset of N(natural numbers) A contains N (0,m) subset of A

If n = 0, 0*m = 0

(m + 1) * x = mx + x

Recursive Steps:

  • 1
    $\begingroup$ see in Peano axioms : Arithmetic for the standard recursive definition of $+$ and $\times$. You can find also them in any textbook of math log. $\endgroup$ – Mauro ALLEGRANZA Feb 7 '15 at 20:03
  • $\begingroup$ It looks like you did it already. Maybe replace $(m+1)$ with $sm$. $\endgroup$ – GEdgar Feb 7 '15 at 20:48
  • $\begingroup$ I have to give an answer using successor. Could you please elaborate what you were trying to say, Please! Thank you $\endgroup$ – user2884707 Feb 7 '15 at 20:52

We assume that you are searching for the (elementary) set-theoretic definition of multiplication, having available the sum ($+$).

If so, we need the successor function, defined as :

$s(x) = x \cup \{ x \}$.

Thus, the recursive definition of multiplication needs a function $f_m : \omega \to \omega$, for each $m \in \omega$, such that :



Then we can apply the Recursion theorem :

Given a set $A$ and a function $g : \omega \times A \to A$, there exists a unique function $f : \omega \to A$ that satisfies the following recursive definition:

$f(0) = a$, for $a \in A$

$f(s(n)) = g(n,f(n))$, forn any $n$

with $\omega$ as $A$, $0$ as $a$ and $+$ as $g$.

We have that $\{ \langle \langle m,n \rangle, f_m(n) \rangle \mid \langle m,n \rangle \in \omega^2 \}$ is single-valued in the second projection, for $\langle m,n \rangle = \langle m',n' \rangle$ implies $m = m'$, and hence also $f_m = f_{m'}$; but $\langle m,n \rangle = \langle m',n' \rangle$ implies also $n = n'$ and thus $f_m(n) = f_{m'}(n')$, showing that the $f_m$ are "well-defined" functions.

Thus, we can call the set $\{ \langle \langle m,n \rangle, f_m(n) \rangle \mid m,n \in \omega^2 \}$ with “$\cdot$” and we have - as expected - that $\cdot : \omega \times \omega \to \omega$ satisfies the conditions :

$$m \cdot 0 = 0$$

$$m \cdot s(n) = (m \cdot n) + m.$$

You can see also this post.


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.