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)$ )
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.
If $f(A)=X$ for some $A$ then $f(X)=X$. Similarly if $f(A)=\emptyset$ then $f(\emptyset)=\emptyset$. Thus we may assume that the restriction $g$ of $f$ to $\overline{X^\ast}:= X^\ast-\lbrace \emptyset,X\rbrace$ is a map $\overline{X^\ast} \to \overline{X^\ast}$. If $g$ is a bijection then $|g(A)| = |A|$ for all $A\in\overline{X^\ast}$, so $g$ is not a bijection. Thus for some $B\in\overline{X^\ast}$ the restriction $h$ of $g$ to $\Gamma:=\overline{X^\ast}-\lbrace B\rbrace$ is an increasing map on $\Gamma$. It follows from a result of Baclawski and Björner that $h$ (and therefore $f$) must have a fixed point. See Theorem 3.1 of http://ftp.cs.wisc.edu/pub/users/prem/for-prem/Comp.%20topology/bjorner-topological-methods-1995.pdf. The second paragraph after this theorem refers to the situation of the present question.
