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!


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.