Suppose that $f:\mathcal{P}(A) \to \mathcal{P}(A)$ is increasing. If $G\in\mathcal{P}(A)$ and $f(G)=G$ then $H\subseteq G\subseteq J$

45 Views Asked by At

Suppose that $A$ is nonempty and that $f:\mathcal{P}(A) \to \mathcal{P}(A)$ is an increasing mapping with respect to $\subseteq$.


  1. By recursion theorem, there exist sequences $(H_n \mid n \in \Bbb N)$ and $(J_n \mid n \in \Bbb N)$ in $\mathcal{P}(A)$ such that $H_0=\emptyset$ and $H_{n+1}=f(H_n)$ and that $J_0=A$ and $J_{n+1}=f(J_n)$.

  2. Next I show that $(H_n \mid n \in \Bbb N)$ is an increasing sequence and that $(J_n \mid n \in \Bbb N)$ is an decreasing sequence.

We will prove $H_n \subseteq H_{n+1}$ by induction on $n$. We have $H_0=\emptyset \subseteq H_1$. It follows that $H_0\subseteq H_1$. Assume that $H_k \subseteq H_{k+1}$, then $f(H_k) \subseteq f(H_{k+1})$ by the fact that $f$ is increasing. Thus $H_{k+1} \subseteq H_{k+2}$. Hence $(H_n \mid n \in \Bbb N)$ is an increasing sequence.

We will prove $J_n \supseteq J_{n+1}$ by induction on $n$ again. We have $J_0=A \supseteq J_1=f(J_0)$. It follows that $J_0 \supseteq J_1$. Assume that $J_k \supseteq J_{k+1}$, then $f(J_k) \supseteq f(J_{k+1})$ by the fact that $f$ is increasing. Thus $J_{k+1} \supseteq J_{k+2}$. Hence $(J_n \mid n \in \Bbb N)$ is a decreasing sequence.

  1. Let $H=\bigcup\limits_{n\in \Bbb N}H_n$ and $J=\bigcap\limits_{n\in \Bbb N}J_n$. I will show that if $G\in\mathcal{P}(A)$ and $f(G)=G$ then $H\subseteq G\subseteq J$.

a. $H_n\subseteq G$ for all $n\in \Bbb N$

We will again use induction on $n$. Since $H_0=\emptyset$, $H_0\subseteq G$. Assume $H_k\subseteq G$, then $f(H_k)\subseteq f(G)=G$ by the fact that $f$ is increasing. Thus $H_{k+1}\subseteq G$ and hence $H_n\subseteq G$ for all $n\in \Bbb N$. It follows that $\bigcup\limits_{n\in \Bbb N}H_n\subseteq G$ and consequently $H\subseteq G$.

b. $G\subseteq J_n$ for all $n\in \Bbb N$

We will again use induction on $n$. Since $J_0=A$, $G\subseteq J_0$. Assume $G\subseteq J_k$, then $G=f(G)\subseteq f(J_k)$ by the fact that $f$ is increasing. Thus $G\subseteq J_{k+1}$ and hence $G\subseteq J_n$ for all $n\in \Bbb N$. It follows that $G \subseteq \bigcap\limits_{n\in \Bbb N}J_n$ and consequently $G\subseteq J$.


Does this proof look fine or contain gaps? Do you have suggestions? Many thanks for your dedicated help!