Proving that the cardinality of a set is even

Question

Let $E$ be a set and $f:E\to E$ be a function such that $f\circ f=Id$.

Let $A=\{x\in E, f(x)\neq x\}$.

Suppose that $A$ is finite.

Prove that the cardinality of $A$ is even.

My idea is to rewrite $A$ as a disjoint union of sets with even cardinality, but I've been unsuccessful so far.

I noticed that $f$ acts as a permutation over the elements of $A$.

What should I do next ?

Answer 1

For each $a\in A$ let $S_a=\{a,f(a)\}$.

1) Show that $|S_a|=2$ for all $a\in A$.

2) Show that $S_a\cap S_b\ne \emptyset$ implies $S_a=S_b$, for all $a,b\in A$.

3) Count the number of elements in $A=\bigcup_{a\in A}S_a$.

In a bit more sophisticated language, there is an action of $\mathbb Z_2$ on $A$ given by applying $f$. The orbits are the $S_a$. By definition, all stablizers are trivial, and thus all orbits have size $|\mathbb Z_2|=2$. The entire set $A$ is the disjoint union of orbits, and thus even.

Answer 2

$f|_A:A \longrightarrow A$ permutes all elements of $A$ and has no fixed points and $f^2 = id_A$.

I want to prove that if $S\subseteq A$ and $f$ permutes the elements of $S$, then the cardinality of $S$ is even. Taking $S=A$ we get the thesis.

I work by contradiction. Suppose there exists $S \subseteq A$ such that $f$ permutes the points of $S$ and $S$ has odd cardinality. Then you can consider such a set with minimal (odd) cardinality. Clearly, since the cardinality of $S$ is odd, we have $S \neq \emptyset$.

But now, pick $x \in S$. Then $S'=S \setminus \{ x, f(x)\}$ has odd cardinality and $f$ permutes all elements of $S'$, contradicting the minimality of $S$.