Countability of complement of a set of fixed points Let $X$ be a set and $f$ a function from $X$ to itself such that $A\backslash f(A)$ is countable for each subset $A$ of $X$.
Can anyone prove that the set 
$\{x\in X:f(x)\neq x\}$
is countable?!
 A: First, note that for any $a\in X$, the set $A=f^{-1}(\{a\})$ must be countable, since $f(A)$ has only one element.  Now let $\sim$ be the equivalence relation on $X$ generated by $f$ (considered as a relation on $X$).  Concretely, $x\sim y$ if there is a finite sequence $x=a_0,a_1,\dots,a_n=y$ such that for each $i$, either $f(a_i)=a_{i+1}$ or $f(a_{i+1})=a_i$.  Since the preimage of each point under $f$ is countable, each equivalence class with respect to $\sim$ is countable.
Now suppose $\{x\in X:f(x)\neq x\}$ is uncountable.  Then it must intersect uncountably many equivalence classes with respect to $\sim$, so we can pick an uncountable subset $A\subseteq\{x\in X:f(x)\neq x\}$ such that no two distinct elements of $A$ are equivalent.  In particular, this means $f(a)\neq b$ for all distinct $a,b\in A$, and also $f(a)\neq a$ since $A\subseteq\{x\in X:f(x)\neq x\}$.  That is, $f(A)$ is disjoint from $A$, so $A\setminus f(A)=A$ is uncountable.  This is a contradiction, so $\{x\in X:f(x)\neq x\}$ must be countable.
