Principle of recursive definition

Question

This problem is from Topology by Munkres. It is a version of Principle of recursive definition.

Let $A(\neq \varnothing)$ be a set. Let $\rho$ be a function assigning, to every function $f$ mapping a section $S_n=\{1,\dots, n-1\}$ of $\mathbb{N}$ into $A$ , an element $\rho(f)$ of $A$ . Then there is a unique function $h:\mathbb{N}\rightarrow A$ such that $h(n)=\rho(h|S_n)$ for each $n\in \mathbb{N}$.

How do I proceed?

Answer 1

What you’re given to work with is the following version of recursive definition:

Theorem $\mathbf{8.4.}$ Let $A$ be a set, and let $a_0\in A$. Suppose that $\rho$ is a function that assigns an element $\rho(f)\in A$ to each function $f$ mapping a non-empty section of the positive integers into $A$. Then there is a unique function $h:\Bbb Z_+\to A$ such that $h(1)=a_0$, and $h(k)=\rho(h\upharpoonright S_k)$ for $k>1$, where $S_k=\{1,\ldots,k-1\}$.

From this you’re supposed to prove the version given in the question, namely:

Let $A$ be a set, and let $\rho$ be a function that assigns an element $\rho(f)\in A$ to each function $f$ mapping a section $S_n$ of $\Bbb Z_+$ into $A$. Then there is a unique function $h:\Bbb Z_+\to A$ such that $h(n)=\rho(h\upharpoonright S_n))$ for each $n\in\Bbb Z^+$.

One difference is that this time we’re not given a specified element $a_0\in A$ to be $h(1)$; instead, we’re told that $h(1)$ should be $\rho(h\upharpoonright S_1)$. Now $S_1=\varnothing$, so even though we don’t yet know what $h$ is, we do know that $h\upharpoonright S_1=h\upharpoonright\varnothing=\varnothing$: the only function with empty domain is the empty function. Fortunately, the other difference is that this time $\rho$ is defined on functions from all sections of $\Bbb Z_+$ into $A$, not just the non-empty sections, and the only function from $S_1=\varnothing$ into $A$ is the empty function, so $\rho(\varnothing)$ is defined.

Now set $a_0=\rho(\varnothing)$ and apply Theorem $8.4$.

Answer 2

---Warning: this answer is written from my mobile. I'm travelling.---

The principle of induction for naturals is equivalent to the decomposition of naturals: every natural is either zero of the successor of some other natural; I.e. if n is a natural then it is of the form "0" or of the form "k+1" for some natural k.

It is a simple induction proof to show that the decomposition theorem is true. The converse is just as easily doable as well and follows the idea illustrated below.

With decomposition in hand, we can define your "h" as follows:

h(n) := HH(f,n, p(f))

Where we use a fancy helper function:

HH(g, n, e) := if n is 0 then e else if n is k+1, for some natural k, then g( HH(g, k, e) ).

Essentially this function takes the number n and function g and element e to the n-fold iterated function composition of g with itself applied to e: (g.g.g.g...g)(e), n-many times.

That this defn satisfied the required properties is easily shown by using the decomposition theorem and then the defn of HH. Enjoy ;-)