Let $U$ denote the set of natural numbers and let $F: P(U) \rightarrow{P(U)}$ denote the function given by $F(X) = \{3\} \cup \{x + 3 | x \in X\}$
a) show that $F$ is continous and cocontinous
b) Compute the least fixed-point and the greatest fixed-point using Kleene Theorem. Compare the two fixed points
I am struggling with this problem for a while. I've tried to prove a) by using structural induction on the set $U$, but it doesn't seem to generate any meaningful result.
What's the best approach to tackle this kind of problem.
I answered the exact same question but it got deleted (a class mate Emi?), but a partial rerun nonetheless:
Now we'll specify $U = \mathbb{N}$ (which includes $0$ in my book) and $F(X) = \{3\} \cup \{3+x: x \in X\}$. Note that clearly from its definition $F$ is monotonous: $A \subseteq B$ implies $F(A) \subseteq F(B)$.
First check the continuity, so let $X_n, n=0,1,2,\ldots$ be an increasing family of subsets of $U$.
We must show that $$F(\bigcup_{n \ge 0} X_n) = \bigcup_{ n \ge 0} F(X_n)$$
The right to left inclusion holds for any $F$: for all $m$, $X_m \subseteq \bigcup_{n \ge 0} X_n$ and as $F$ is monotonous, for all $m$, $F(X_m) \subseteq F(\bigcup_{n \ge 0} X_n)$, and so $\bigcup_{ n \ge 0} F(X_n) \subseteq F(\bigcup_{n \ge 0} X_n)$.
On the other hand, let $y \in F(\bigcup_{n \ge 0} X_n)$, so that $y=3$ or $y = 3+x$ for some $x \in \bigcup_{n \ge 0} X_n$. If $y=3$, $y \in F(X_n)$ for any $n$ (by definition of $F$) and so certainly $y \in \bigcup_{ n \ge 0} F(X_n)$, and if $y=x+3$ for $x \in X_{n_0}$, say, then $y \in F(X_{n_0})$, again by definition and we have $y \in \bigcup_{ n \ge 0} F(X_n)$ as well. It's not much we use of $F$ (on also I don't seem to be using the increasingness of the $X_n$ in any way). But anyway, I showed continuity of $F$.
The proof that $F$ is cocontinuous is similarly simple: let $X_n, n\ge 0$ be decreasing and we want to show that $F(\bigcap_n X_n) = \bigcap_n F(X_n)$. $\bigcap_n X_n \subseteq X_n$ for all $n$, so F(\bigcap_n X_n) \subseteq F(X_n)$ for all 4n$ by monotonicity of $F$. So $F(\bigcap_n X_n) \subseteq \bigcap_n F(X_n)$. Now let $y \in \bigcap_n F(X_n)$. If $y = 3$ then clearly $y \in F(\bigcap_n X_n)$, as $3 \in F(A)$ for any $A$. So we can assume that $y \ge 3$ and $y-3 \in F(X_n)$ for every $n$ (this follows directly from $y \in F(X_n)$ for every $n$ and $ y \neq 3$ from the definition of $F$). So $y-3 \in \bigcap_n X_n$, which implies that $y \in F(\bigcap_n X_n)$ as required. This shows the remaining inclusion and hence cocontinuity.
To find the minimum fixed point we apply the first fact from Kleene, and know that it equals $\mu F=\bigcup_{n \ge 0} F^n(\emptyset)$.
The first stages are $F^1(\emptyset) = \{3\}$, $F^2(\emptyset) = \{3,6\}$ and a simple induction will establish that $$F^n(\emptyset) = \{3i: 1 \le i \le n\}$$ from which it follows that the minimum fixed point is indeed, as you claim, $\mu F = \{3i: i \in \mathbb{N}\setminus\{0\}\}$
For the maximum fixpoint we go the other way: $$F(U) = \{3\} \cup \{3+x: x \in \mathbb{N}\} = \{3,4,5,6,7,\ldots\}$$
and
$$F^2(U) = \{3\} \cup \{3+n : n \in F(U)\} = \{3,6,7,8,9,\ldots\}$$
and by induction again we can prove that
$$F^n(U)=\{3i: 1\le 1 \le n\} \cup \{3n+j: j=1,2,3,\ldots\}$$
and then $\nu F = \bigcap_{n \ge 0} F^n(U) = \{3i: i \in \mathbb{N}\setminus\{0\}\} = \mu F$. (So the fixed point is unique.)
Note that changing the domain $U$ to $\mathbb{Z}$ does not change $\mu F$ at all (as we go up from $\emptyset$ and keep sets in $\mathbb{N}$ all the time), while $F(U) = U$, as $n \in U$ implies $n-3 \in U$ and so $n = 3+(n-3) \in F(U)$ too, and so $\nu F = U$ in this case (you see why both are included now..)