How to show factorial is recursive?

239 Views Asked by At

In my textbook

Fact : Given recursive $G:\omega^{n}\rightarrow\omega$ and $H:\omega^{2}\times\omega^{n}\rightarrow\omega$ , a function $F:\omega\times\omega^{n}\rightarrow\omega$ defined by $F(a,\bar{b})=\begin{cases} H(F(a-1,\bar{b}),a-1,\bar{b}) & a>0 \\ G(\bar{b}) & otherwise \end{cases}$ is recursive.

And it suggest a function $ fac(n)=\begin{cases} fac(n-1)\cdot n & n>0\\ 1 & n=0 \end{cases}$

is an example of the fact.

But,then G must be a function $\omega ^0\rightarrow \omega$. This seems to be strange.

1

There are 1 best solutions below

0
On BEST ANSWER

That's OK. A $0$-ary function is essentially a constant. It's not only a useful convention, it's a natural correspondence.

Its domain has one element, and it assigns to that an element of the range. For any thing $*$, the functions $\{*\}\to X$ are in many cases interchangeable with the elements of $X$ — each function selects an element from the range, and every element can be so selected, uniquely.

$X=\omega^0 =$ is the singleton $\{\emptyset\}$: it's the all zero-length sequences of elements of $\omega$. As nombre points out in a comment, the standard convention in set theory is that every ordinal, including integers $\subseteq \omega$, is the set of its predecessors, so that $0=\emptyset$. So $\omega^0 = \omega^{\emptyset}$, whose only member is $\emptyset$, the unique function on $\emptyset$, "into"... $\omega$, but really, into anything. This function is itself $\emptyset$. If $()$ denotes the empty sequence, then $() = \emptyset$.

So $G\colon \{\emptyset\}\to \omega$ just selects an integer: "it's a constant". If we wanted to be very fussy and formal, we'd write $G(())$, "but nobody ever does" (Halmos, I think). In the case of the $fac$ function, we'd much rather read and write $0$ than something like $(()\mapsto 0)()$. Thus, "$fac(n) = H(fac(n-1),n-1)$ for $n>0$, $0$ otherwise, where $H(x,y)=x*(y+1)$."