# Increasing functions on the set of all non-empty proper subsets of a finite set

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

-
If "increasing" means that whenever $A$ is a proper subset of $B$, $f(A)$ must be a proper subset of $f(B)$, then it's easy to prove that $|f(A)|=|A|$ for all $A$ (assuming $||$ means cardinality). So your hypothesis is vacuous. –  Steven Landsburg Jun 21 '13 at 18:38
@Steven: By increasing I mean when $A\subseteq B$ then $f(A) \subseteq f(B)$. –  user30293 Jun 21 '13 at 19:30

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.
$f$ can not take $X$ since $f$ is from $X^*$ into $X^*$ –  user30293 Jul 8 '13 at 17:38