הוכחות מתמטיות/תורת הקבוצות/למת נקודת השבת

אם $X\neq \phi$ והפונקצייה $\varphi \colon P(X)\to P(X)$ הינה שומרת הכלה (מונוטונית עולה), כלומר $\forall A,B\in P(X)\colon A\subseteq B\Rightarrow \varphi (A)\subseteq \varphi (B)$,
אזי $\exists Y\in P(X)\colon Y=\varphi (Y)$.

כלומר, לכל פונקצייה שומרת הכלה יש נקודת שבת.

הוכחה

נגדיר קבוצה $\mathbf {M} =\{A\in P(X)|A\subseteq \varphi (A)\}$. מתקיים $\phi \in \mathbf {M}$ ומכאן $\mathbf {M} \neq \phi$.
נסמן $Y=\bigcup \mathbf {M} =\bigcup _{A\in \mathbf {M} }A$. מובן כי $Y\in P(X)$ לפי ההגדרה.

מהגדרת $Y$, לכל $A\in \mathbf {M}$ מתקיים $A\subseteq Y$ ומכך ש-$\varphi$ שומרת הכלה נקבל $\varphi (A)\subseteq \varphi (Y)$. ומכאן גם מתקבל $\bigcup _{A\in \mathbf {M} }\varphi (A)\subseteq \varphi (Y)$.
מהגדרת $\mathbf {M}$, לכל $A\in \mathbf {M}$ מתקיים $A\subseteq \varphi (A)$, ולכן גם $Y=\bigcup _{A\in \mathbf {M} }A\subseteq \bigcup _{A\in \mathbf {M} }\varphi (A)$.
משילוב שתי התוצאות הללו נקבל $Y\subseteq \varphi (Y)$.

שוב, $\varphi$ שומרת הכלה ולכן $\varphi (Y)\subseteq \varphi (\varphi (Y))$, ולכן לפי הגדרת $\mathbf {M}$ נקבל כי $\varphi (Y)\in \mathbf {M}$.
מכאן נסיק כי $\varphi (Y)\subseteq \bigcup \mathbf {M} =Y$.

הראנו הכלה בשני הכיוונים, כלומר $Y=\varphi (Y)$, כנדרש.