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

1.4k Views Asked by At

We have a map $f:P(X)\to P(X)$, where $P(X)$ means the part of $X$ and the function is monotone (by considering inclusion "$\subseteq$"). So $\forall \space A\subseteq B $ we have $f(A)\subseteq f(B)$. Show that this map has a fixed point.

This claim is used in some proofs of Cantor–Schröder–Bernstein theorem, for example, see proof 3 on ProofWiki (current revision).

2

There are 2 best solutions below

1
On BEST ANSWER

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.

0
On

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)$.)