MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
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
up vote 6 down vote accepted

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.

share|cite|improve this answer

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 The second paragraph after this theorem refers to the situation of the present question.

share|cite|improve this answer
$f$ can not take $X$ since $f$ is from $X^*$ into $X^*$ – user30293 Jul 8 '13 at 17:38

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.