Exercise 8.8

Question

\def{ho}
\defest{estriction}

Verify the following version of the principle of recursive definition: Let $A$ be a set.
Let $$ be a function assigning, to every function $f$ mapping a section $S_n$ of ${{\mathbb{Z}}_+}$ into $A$, an element $(f)$ of $A$.
Then there is a unique function $h: {{\mathbb{Z}}_+} 	o A$ such that $h(n) = (h est S_n)$ for each $n \in {{\mathbb{Z}}_+}$.

Dan Whitman · Accepted Answer

\def{ho}
\defest{estriction}

Denote the above property of $h$ by $(*)$.
We show that there is a unique $h: {{\mathbb{Z}}_+} 	o A$ satisfying this using the standard principle of a recursive definition, Theorem~8.4.
\begin{proof}
First, note that $S_1 = \left\{n \in {{\mathbb{Z}}_+} \mid n < 1ight\} = \varnothing$ by definition.
Note also that $\varnothing$ itself is vacuously a function from $S_1 = \varnothing$ to $A$, and is the only such function.
It then follows that $f est S_1 = f est \varnothing = \varnothing$ for any $f : S_n 	o A$ for some $n \in {{\mathbb{Z}}_+}$.
So then, define $a_0 = (\varnothing)$ so that there is a unique function $h$ such that
\begin{align*}
h(1) &= a_0 \,, \
h(i) &= (h est \left\{1, \ldots, i-1ight\}) \hspace{1cm} 	ext{for $i > 1$.}
\end{align*}
by Theorem~8.4.
Denote this property by $(+)$.

We first claim that this $h$ satisfies $(*)$.
To see this, consider any $n \in {{\mathbb{Z}}_+}$.
If $n=1$ then we have
\begin{gather*}
h(n) =  h(1) = a_0 = (\varnothing) = (h est \varnothing) = (h est S_1) = (h est S_n) \,.
\end{gather*}
If $n > 1$ then by $(+)$ we have
\begin{gather*}
h(n) = (h est \left\{1, \ldots, n-1ight\}) = (h est S_n)
\end{gather*}
again.
Since $n$ was arbitrary, this shows that $(*)$ is satisfied.

To show that this $h$ satisfying $(*)$ is unique, suppose that another function $f: {{\mathbb{Z}}_+} 	o A$ satisfies $(*)$.
Then we have
\begin{gather*}
h(1) = (h est S_1) = (h est \varnothing) = (\varnothing) = a_0
\end{gather*}
and
\begin{gather*}
h(i) = (h est S_i) = (h est \left\{1, \ldots, i-1ight\})
\end{gather*}
for $i > 1$.
This shows that $f$ also satisfies $(+)$, and, since we know that the function satisfying $(+)$ is unique, it must be that $f = h$ as desired.
\end{proof}

Exercise 8.8

Answers

Comments

Exercise 8.8

Answers

Comments

Add answer