Definition of function by finite recursion I am reading the book "Set Theory and the Continuum Problem" by Raymond Smillyan and Melvin Fitting.
On page 43 §8 he states the following:

Let $c$ be an element of a class $A$, and $g$ be a function from $A$
  into $A$. Does there necessarily exist a function $f$ from numbers
  to elements of $A$ such that
  $f(0)=c$ and for every $n, f(n^+)=g(f(n))$ (In othe words, f(0)=c,
  f(1)=g(c), f(2)=g(g(c)),...)? An obvious induction argument on $n$
  shows that there cannot be more than one such function $f$, but how do
  we know there is at least one? Unfortunately some articles and
  textbook have given the fallacious argument that $f$ is defined on $0$
  (since $f(0)=c$) and if $f$ is defined on $n$, then $f$ is also
  defined on $n^+$ (since $f(n^+)=g(f(n))$) hence by mathematical
  induction $f$ is defined on every natural number $n$. The counter to
  that fallacious argument is: What function $f$?

I do not understand why the above argument is false. What exactly is the problem? I dont understand the question "What function $f$"? Its already defined by  $f(0)=c$ and $f(n^+)=g(f(n))$ for every natural number.
Instead the author suggest to create the function $f_n$ defined on the set of integers from $0 \dots n$ by $f_n(0)=c$, and $f_n(i^+) = g(f_n(i))$ for any $i<n$. Then, the author suggest to show that $f_n(k) = f_{n^+}(k)$ for any $k\leq n$. He then defines the function $f$ to be the set of all ordered pairs $<n, f_n(n)>$ (from §9 - a function is a relation $R$ such that for any x there s at most one element y with $<x,y> \in R$).
Can someone explain to me, why the author does not accept the first proof? And what is substantially different from the second proof?
 A: Axiomatically in set theory it is tricky to go from finite to infinite, i.e. for example even if it is trivial to show that such a function exists on a finite set by just describing the function values with one logical sentence, it is not trivial to describe the limit case which is infinite, because you cannot have infinite logical sentence.
To go around this limitation, you can still use the induction principle (in different situations the axiom of choice helps as well).
Induction principle basically says that, for any logical sentence $P(n)$, if you can show $P(0) \wedge (\forall n \: P(n)\implies P(n+1))$, then $\forall n \: P(n)$ holds.
Induction principle can then be applied to build finite graphs, i.e. to show $$\forall n \:\exists !f\in\mathcal F([0,n], A) \: (f(0)=c \wedge \forall i\in[0,n-1] \: f(i+1)=g(f(i))).$$
Finally you may build a function on $\mathbb N$ buy taking the union of all the graphs of the functions uniquely defined above. You still have to verify that this union constitutes a graph - and here the uniqueness of these functions defined on finite domains is actually very helpful - and then that it is the graph of the function you want.
A: Let’s expand the argument in the paragraph in question: we want to show that the domain of the function $f$ is all of $\mathbb{N}$, by induction. We know the domain includes $0$, and if it includes $n$, then it includes $n^+$. Hence, the domain is all of $\mathbb{N}$.
Okay, what is the problem? You are trying to show that the function $f$ exists. If you don’t know it exists yet, which you do not because you are trying to show it exists, then how can you possibly define the domain of $f$, let alone apply induction to it? So the argument is fallacious because it implicitly assumes that you already know you have a function $f$, with domain contained in $\mathbb{N}$, so that you can apply induction to its domain.
Now, the conditions you have allow you to define a function $f_0$ with domain $\{0\}$, namely $f_0 = \{(0,c)\}$. Once you have this, you can use the conditions to define a function $f_1$ with domain $\{0,1\}$ by $f_1 = \{(0,c), (1,g(f_0(0)))\}$. Once you have this you can use the conditions to define a function $f_2$ with domain $\{0,1,2\}$ given by $f_2 = \{(0,c), (1,g(f_1(0))), (2,g(f_1(1)))\}$. Etc. 
So you can write down a function $f_k$ with domain $\{0,1,\ldots,k\}$ for any $k\in\mathbb{N}$ using the description, just one element of the domain at a time. But that only allows you to define functions on initial segments of $\mathbb{N}$, not on all $\mathbb{N}$: just because you can do this any finite number of times does not mean you can do it an infinite number of times. 
So, since you don’t actually know there is a function $f$ to apply the argument to, but you do know you have all these functions $f_k$, then you can try to leverage those functions $k$ into constructing a new function $f$ that is defined on all of $\mathbb{N}$ and has the property you want. That’s what he suggests you do.
The key is that if you were to try to write down the definition of the function in set theory, without these considerations, you would end up with a definition of $f$ in terms of $f$. You can’t do that. You cannot define a set in terms of itself. So until you show that you have a function $f$, you can’t argue about its domain.
