Function by recursion on a set $X$ satisfy Peano’s axioms

analysispeano-axiomsreal-analysisrecursionset-theory

I've been stuck on this theorem for like two days and I still don't really get it.
I'm reading the construction of natural numbers using "classic set theory for guided independent study", and it says:

"To construct arithmetic operations a key tool will be the definition of a function $f$ by recursion. In the context of a set $X$ satisfying Peano's axioms, this means giving $0$ some value and explaining how to define $f(S(x))$ assuming one knew the value of $f(x)$"

then it gives this example:

"define $f$ on $\{0, 1, 2, \cdots\}$ by $f(0)=1$ and $f(n+1)=(n+1)f(n)$ for $n>0$ then to workout $f(m)$ for some specific $m$, use the second part of the definition until you hit $f(0)$, for instance: $f(3)=f(2+1)=3f(2)=3f(1+1)=3·2f(1)=6f(0+1)=6·1f(0)=6·1=6$
infact this $f$ is just the factorial function $f(n)=n!$"

I understand all this but this is the part I don't really get:

"A general result about defining a function by recursion on a set $X$ satisfying Peano's axioms is as follows: Let $X$ satisfy Peano's axioms. Let $Y$ be any set, $y_0$ any element of $Y$ and $h:X×Y→Y$ a function on pairs $(x,y)∈X×Y$. Then there exists a unique function $f:X→Y$ such that $f(0)=y_0$ and $f(S(x))=h(x,f(x))$ for all $x$."

I don't really understand this part, I understand what it states but I don't understand what it's trying to convey. Peano's axioms that this book is talking about are:

"A Peano system is a set $X$ with a special element $0\in X$ and a funtion $S:X\to X$ such that the following also hold:

  1. The function $S$ is one-one
  2. For all $x\in X$, $0\neq S(x)$
  3. For all subset $A\subseteq X$, if $A$ contains $0$ and contains $S(x)$ whenever $x\in A$, then $A$ is all of $X$."

After that theorem it also says:

"for the example above we could take both $X$ and $Y$ to be the set of natural numbers, $y_0=1$ and $h$ the function $h(x,y)=(x+1)\cdot y$

What is the function $S$ in that example? What is $h$? Why is $h$ defined like $h(x,y)=(x+1)·y$? I don't really understand, could you guys help me out please?

Best Answer

Definitions by recursion are typical of natural numbers (in set theory, they can be generalized); see Recursion Theorem).

This kind of definition exploits the key facts about $\mathbb N$ as defined by Peano axioms:

$0, S(x)$ and Induction axiom.

Consider the following example regarding the function $a^n$.

For every real number $a$ we define $a^n$ recursively as follows:

$a^0=1$ and $a^{n+1}=a^n \cdot a$, for every $n \in \mathbb N$.

How can formalize the above definition with recursion formalism?

Let assume $a \in \mathbb R$ and let $f: \mathbb N \times \mathbb R \to \mathbb R$.

We have: $f(0,a)=1$, and we have:

$f(S(n), a)= f(n,a) \cdot a$.

Here the "auxiliary" function $h(x,y)$ is simply the product, i.e.

$\cdot: \mathbb R \to \mathbb R$.

The definition provides a simple procedure (an algorithm) to compute $a^n$ for every $n$; this facts is based on the Induction axiom that guarantees that we can reach every natural number $n$ after a finite number of steps.

We start with $n=0$ and we compute $a^0=1$, using the first part of the definition.

Having $a^0$, i.e. $f(0,a)$, we use it in the second part of the defintioin to compute:

$a^1=f(1,a)=f(S(0),a)=h(f(0),a)=h(1,a)=1 \cdot a=a$.

And so on... (this is Induction).

Related Question