Proof that recursion defines a function (from: Recursive definition - Wikipedia, the free encyclopedia)

Suppose one has a pair of functions f and g on the natural numbers such that f(0)=0 and f(n+1)=g(f(n)) for all n. We want to construct, for any natural number n, a subset F(n) of N x N such that:

(1) for all natural numbers a between 0 and n: there exists a unique natural number b such that (a, b) is in F(n);

(2) (0, f(0)) is in F(n);

(3) for all natural numbers a, where a is between 0 and n-1: if (a, f(a)) is in F then (a+1, g(f(a))) is in F(n).

Clearly {(0, f(0))} satisfies (2) and (3).

Suppose these properties hold for n. Consider F(n+1)=F(n)U{(n,g(n))}. Then this set satisfies all 3 properties (1), (2), (3). By induction we have such a set for any natural number n. Let F be the set theoretic union of all the F(n), where the union is taken over all natural numbers n.

---

After pondering a good while here is my interpretation of the proof. I state my case positively not because I am certain that I am right but because I want to clear about what I think.

So what we want is to define a function f that delivers a particular subset F(n) of N x N. It would be nice to have a “regular function” like f(n) = 2n but instead we are being given a recursive function defined by f(0)=0 and f(n+1)=g(f(n)).

Unfortunately it took me a long time to comprehend the meaning of that last statement. I now believe that what it says is … what it says … that f(n) is defined recursively by a base value f(0)=0, and a function g which delivers a next value of “f”, f(n+1), as a function of a previous value of “f “, f(n), that is f(n+1) = g(f(n)). Where does the value of f(n) come from? … from a recursive iteration of values starting from a base case, in this instance, f(0+1) = g(f(0)).

It took me a while to realize that a regular function f(n) can be replaced by a recursive function f(n) but to do so you must come up with a base value and a suitable unique function g(n) that does the job of correctly delivering f(n+1) as a function of f(n). Comprehending g(f(n)) was a real revelation.

I don’t believe there is any set way of finding g(n) for a given regular function f(n), or for a set F(n) subset of N x N, but once you have a candidate a proof by induction allows you to see if it works.

Now, I believe that not all subsets of N x N can be defined recursively (probably not “regularly” either – is there another name for a “regular” function?) so F(n) must have certain properties .

(1) for all natural numbers a between 0 and n: there exists a unique natural number b such that (a, b) is in F(n);

This says that every element “a” of f’s domain set must have auniquecorrespondent “b” in f’s codomain. Note that while all values of f’s domain set must have a corresponding value in the codomain, not all values in the codomain need be the correspondent of a value in the domain set, i.e. the range set will often be a proper subset of the codomain but can equal to the codomain.

(2) (0, f(0)) is in F(n);

This is just the given base case.

(3) for all natural numbers a, where a is between 0 and n-1: if (a, f(a)) is in F then (a+1, g(f(a))) is in F(n).

This is just f(0)=0 and f(n+1)=g(f(n)), used to generate the ordered pairs of F(n). The domain is restricted on the lower end as greater than 0 because there is no defined precursor of 0 to apply to g. The domain is restricted at the higher end because (n-1) is the argument that must be applied to g if it is to return a value for f(n).

Clearly {(0, f(0))} satisfies (2) and (3).

(2) is clearly satisfied, (3) is apparently satisfied not to be bothered since 0 is not between 0 and n.

Suppose these properties hold for n. Consider F(n+1)=F(n)U{(n,g(n))}. Then this set satisfies all 3 properties (1), (2), (3). By induction we have such a set for any natural number n. Let F be the set theoretic union of all the F(n), where the union is taken over all natural numbers n.

Assuming the three properties hold, i.e.

(1) that for any natural number greater than 0 and less than n there exists a unique f(n),

(2) that for n = 0 specifically, f(0) exists

(3) that a function g(n) exists such that f(n+1)=g(f(n)), so that when (a, f(a)) is in F then (a+1, g(f(a))) is in F(n),

.... granting those properties .... by induction F(n) is a set defined by recursion.

Induction itself is justified foundationally by a recursive union of sets expressed by F(n+1)=F(n)U{(n,g(n))}.

F(n+1) is the set of ordered pairs comprising F(n) in union with the next/successive ordered pairs defined by (n, g(n)) and reduced to a set theoretic union (a set comprised of all of the elements found within the recursively generated sets comprising F(n)U{(n,g(n))} ).

Hopefully I have this explanation correct because this understanding the role of g(n) with respect to f(n) in particular seems to make many things much more clear.