Proof of equality of least fixed point of two continuous function

131 Views Asked by At

The question is simple: given a set U, a continuous function (Scott continuity) $f \colon \mathcal{P}(U) \to \mathcal{P}(U)$ and function $g(X) := f(f(X))$, prove that $g$ is continuous and its least fixed point is equal to least fixed point of $f$.

I've already managed to prove the continuity of $g$. However, I'm stuck with the second part. My teacher suggested to prove the double inclusion $\text{fix}(f) \subseteq \text{fix}(g)$ and $\text{fix}(g) \subseteq \text{fix}(f)$.

Using the Kleene theorem, we know that $$ \text{fix}(f) = \bigcup_{i \in \mathbb{N}} f^i(\emptyset) $$

Can you please tell me whether the following steps are correct?

$$ \text{fix}(g) = \bigcup_{i \in \mathbb{N}} g^i(\emptyset) = \bigcup_{i \in \mathbb{N}} f^i(f(\emptyset)) = \bigcup_{i \in \mathbb{N}} f^{i+1} (\emptyset) $$ $$ \bigcup_{i \in \mathbb{N}} f^{i+1}(\emptyset) = \bigcup_{i \in \mathbb{N}} f^{i+1}(\emptyset) \cup \emptyset = \bigcup_{i \in \mathbb{N}} f^{i+1}(\emptyset) \cup f^0(\emptyset) = \bigcup_{i \in \mathbb{N}} f^{i}(\emptyset) = \text{fix}(f) $$ Is it correct, even if I followed a different path?