Show that a function $f:P(X)\to P(X)$ preserving the subset relation has a fixed point

HINT: Consider the set $\bigcup\{A\subseteq X:A\subseteq f(A)\}$. (Be sure to show that there is at least one $A\subseteq X$ such that $A\subseteq f(A)$.)


I'll generalize the nice answer by @Brian and give a curiosity (that you don't need to show that there exists at least one $A \subset X$ such that $A \subset f(A)$!).

Definition: Given a partially ordered set $X$ and a subset $A$, $\sup(A)$ is defined as (if it exists) the element $s$ such that:

  1. $s\geq a ~\forall a \in A$.
  2. $b \geq a ~\forall a \in A \implies b \geq s$.

Uniqueness is clear. Note that $\emptyset$ has a $\sup$ if and only if $A$ has a minimum element.

Now, we have:

Theorem: Let $X$ be partially ordered s.t. every subset has a supremum and $f:X \to X$ monotone. Then $f$ has a fixed point.

Proof: Let $A=\{x \mid f(x) \geq x\}$. Take $s=\sup(A)$ (note that this is exactly the set given by Brian).

We prove that $f(s)=s$.

First, since $s$ is $\sup(A)$, it follows that $s \geq x $ for all $x \in A$. Since $f$ is monotone, we have $f(s) \geq f(x)$ for all $x \in A$. Since $f(x)\geq x$ for all $x \in A$, we have $f(s) \geq x$ for all $x \in A$. Since $s$ is $\sup(A)$, it follows that $f(s) \geq s$.

Now, note that monotonicity implies $f(f(s)) \geq f(s)$. Therefore, $f(s) \in A$. We then have $s \geq f(s)$, since $s$ is $\sup(A)$.

It follows that $s=f(s)$. $\blacksquare$

Note that in no point of the proof we needed $A$ to be non-empty, although it clearly is (since the set will have a minimum element by assumption).

Now your exercise is to adapt the proof to your case.