For a finite set $X$ let $X^\* $ be the set of all non-empty proper subsets of $X$. Let $f : X^\* \longrightarrow X^\* $ be an increasing function such that for some $A \in X^\* $, $|f(A)| \not = |A|$. It is true that $f$ must have a fixed point ? 


(By increasing I mean when $A\subseteq B$ then $f(A)\subseteq f(B)$ )



Increasing functions on the set of all non-empty proper subsets of a finite set
Take $A$ maximal among sets such that $|f(A)|>|A|$. For each one-element set $\{x\}$, $f(\{x\})\subseteq f(A)$, because otherwise $|f(A \cup \{x\})| > |A \cup \{x\}|$. Draw a directed graph with one arrow leaving each element $x\in X$ pointing to an element $y\in X$ with $y \in f(\{x\})$. Let $T$ be the set of points in a cycle of that graph, then $T$ is proper because no point in $f(A)^c$ is in the image of any arrow, and $T\subseteq f(T)$ . A set $S$ maximal among sets such that $S\subseteq f(S)$ is a fixed point.


