The recursion theorem - approach

213 Views Asked by At

I'm reading "Introduction to Set Theory" by Hrbacek and Jech(1999, 3rd ed). On page 47, the recursion theorem is stated as follows.


The recursion theorem: For any set $A$, any $a \in A$, and any function $g : A \times N \to A$, there exists a unique infinite sequence $f : N \to A$ such that
(a) $f_0 = a$;
(b) $f_{n+1} = g(f_n,n)$ for all $n \in N$


The author says that "the proof of the Recursion Theorem consists of devising an explicit definition of $f$. (p. 48)" In case of the function factorial, an explicit definition could be given like this:

$$f_0 = 1 \quad\text{ and }\quad f_m = 1 \times 2 \times \cdots\times (m-1) \times m \;\text{ if }\; m \neq 0 \;\text{ and }\; m \in N \; \cdots \; (1)$$

The problem with this kind of formulation, the author says, is that the ellipsis "$\cdots$" is not precise enough. The solution, according to the book, is to state $f_m$ as the result of a computation.

$$1$$ $$1\times1$$ $$[1\times1]\times2$$ $$[1\times1\times2]\times3$$ $$\vdots$$ $$[1\times1\times2\times\cdots\times(m-1)]\times m$$

Above is an m-step computation t which means that it is a "finite sequence that is of length $m + 1$ where $t_0 = 1$ and $t_{k+1} = t_k \times (k + 1) = g(t_k,k)$ for all $k < m, k \geq 0.$" The rigorous explicit definition of $f$ then is:

$$f_m = t_m$$ where $t$ is an m-step computation (based on $a = 1$ and $g$)


My question is, I don't understand why the ellipsis "$\cdots$" in (1) is not precise enough. What does "precise" mean? How does reformulating it in terms of a computation make it any more "precise"?

1

There are 1 best solutions below

0
On BEST ANSWER

the ellipsis "$\cdots$" is not precise enough

When there is a disagreement while playing any game, the participants must be able to get out the 'rule book' to decide how to proceed.

What if a famous mathematician writing out a proof that uses the ellipsis in a much more complex context. Are they following the rules?

Can you see this one "in your own mind":

$a + ar + ar^2 + \ldots + ar^{n-1} = \frac{ a( 1- r^n) } { (1-r) }$

Must we force another person looking at this to see it the way we do, as a
'telescoping cancel/out deal'.