Definition by Recursion: why is the existence part not (almost) obvious?

Question

I saw the following statement.

Let $H$ be a set, let $e\in H$ and let $k:H\rightarrow H$ be a function. Then there is a unique function $f:\mathbb{N}\rightarrow H$ such that $f(1)=e$, and that $f\circ s=k\circ f$. (where $s:\mathbb{N}\rightarrow\mathbb{N}$ is the successor function)

On the 'existence' part alone, my problem is that I can't see what the flaw is in my argument.

We know $f(1)$, and if ,for some $n\in\mathbb{N}$, we are given $f(n)$ then we define $f(s(n)):=k(f(n))$; so we know $ f(s(n))$ .By induction $f$ is defined on $\mathbb{N}$.

Maybe the "proof" is too informal. Some examples to illustrate may be helpful.

Thanks

Answer 1

In fact your proof is a circular argument. To prove something by induction you first have to have the something. To define something "inductively" (loose terminology) is definition by recursion.

You can define a recursive function $f$ for a finite range of $n\in\mathbb N$, say $n \le N$ by saying $f(1) = e, f(2) = k(e), ...... f(n) = k^{n-1}(e)$ but why would this function exist for all values of $n\in\mathbb N$ ? - you can't write an infinite specification for the function.

So, you have actually relied on the Theorem of Recursion (i.e. in one form, the statement you are trying to prove) when you assume the existence of $f$ for all $n\in\mathbb N$ (and you are then using induction to prove $f$ has the property you have assumed it to have).

The longer proofs that you may have seen might in outline go as follows:

(1) if $f$ exists it would be represnted as a subset of N x H, i.e. a set of ordered pairs where each $n\in\mathbb N$ is represented in exactly one ordered pair.

(2) whatever values $f$ might take N x H contains them

(3) the powerset of N x H, $\mathscr P(N \mathrm x H)$ contains all possible subsets of N x H

(3) using specification, one can obtain a subset $\mathscr D$ of $\mathscr P(N \mathrm x H)$ with the property that all the elements of $\mathscr D$ (which are subsets of N x H) include $(1, e)$ , and if $(n, h)$ is in such an element of $\mathscr D$ then so is $(n + 1, k(h))$

(4) The intersetion of all elements of $\mathscr D$ is formed and shown to be a function and (by definition) to be recursive.

(5) the function $f$ is then shown to be unique.

Answer 2

The validity of a proof must be verified according to the logical system and the axioms used by the theory. In ZFC, functions are sets and the existence of a set must be justified by the set axioms. Since you haven't mentioned any axioms of ZFC, your proof are unlikely to be accepted as a proof in ZFC.

However, if we build another theory in which functions are determined by finite instructions governing how to compute the output from the input in finite steps, your proof turns out to be a very good one. Suppose $H$ is a decidable set and $k$ is a computable function, your proof actually provides an algorithm(with finite instructions:$f(1)=e,fs=kf$) which gives a result for any natural number $n$ in finite steps. Proofs of this kind agree with constructivists' reasoning.