0
$\begingroup$

Let $F:A\to A$ be a function and let $Y \subseteq A$. The recursion theorem implies the existence of the function $h:\omega \to \mathcal{P}(A)$ that satisfies:

(1) $h(0)=Y$

(2) $h(n^+)=h(n) \cup F[h(n)]$

Now address the following:

(a) Let $Y \subseteq B \subseteq A$ and $F[B] \subseteq B$. Prove by induction that $h(n) \subseteq B$ for all $n \in \omega$.

(b) Let $C'=\bigcup_{n\in \omega}h(n)$. Prove that $Y \subseteq C' \subseteq A$ and $F[C'] \subseteq C'$.

Attempt: For (a), I let $I=\{n\in \omega |h(n) \subseteq B\}$. $0\in I$ trivially. Then let $n\in I$, and we need $(n^+)\in I$, i.e. given $h(n) \subseteq B$, show that $h(n^+)\subseteq B$. I see the identity given in (2), but I'm not entirely sure how to proceed because the whole $F[B]\subseteq B$ thing is still confusing me. Any help is appreciated!

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.