Set theory, fixed points

87 Views Asked by At

Let $f : \mathcal{P}(B) \to \mathcal{P}(B)$ be a monotonic function and $I$ - its least fixed point. Prove that:

  • if $I \subseteq A \subseteq B$ and $f_A : \mathcal{P}(A) \to \mathcal{P}(A)$, $f_A(X) = A \cap f(X)$ for all $X \subseteq A$, then $I$ is least fixed point of $f_A$, as well;

  • if $B \subseteq C$ and $f^C : \mathcal{P}(C) \to \mathcal{P}(C)$, $f^C(X) = f(X \cap B)$ for all $X \subseteq C$, then $I$ is least fixed point of $f^C$, as well.

My attempt for the first part: I tried to use the idea of Tarski's Fixed-point Lemma that every function, defined as above, has least prefixed point and this least prefixed point is least fixed point.

So, I construct the set $C = \{x|x \in \mathcal{P}(A), f_A(x) \subseteq x\}$. Then, if I show that for an arbitrary element $x_0$ of the set $C$, $I \subseteq x_0$, then I will be least prefixed point and so least fixed point.

Any hints how this could be proven?

1

There are 1 best solutions below

1
On BEST ANSWER

For the first part, let $J$ be the least fixed point of $f_A$. Because $I$ is also a fixed point of $f_A$, we see that $J \subseteq I$. Therefore, we have $f(J) \subseteq f(I) = I \subseteq A$, and therefore $J = f_A(J) = A \cap f(J) = f(J)$; then $I \subseteq J$.

For the second part, let $J$ be the least fixed point of $f^C$. Then $J = f^C(J) = f(B \cap J) \subseteq B$. Therefore, $J = f^C(J) = f(J)$. Then $I \subseteq J$. Conversely, since $I \subseteq B$, we have $I = f(I) = f(B \cap I) = f^C(I)$, so $J \subseteq I$.