A finite set and the set of its fixed points under any involution have cardinalities of the same parity

Question

I am trying to write down a formal proof of the following fact:

Let $A$ be a non-empty finite set and $f$ an involution on $A$. If $A'$ is the set of fixed points of the involution $f$, then $|A| \equiv |A'| \pmod 2$, where $|A|$ is the cardinality of $A$ and $|A'|$ is the cardinality of $A'$.

We can define an equivalence relation on $A$ given by the rule \begin{equation*} \forall \, a, b \in A \quad a \sim b\ \text{if and only if}\ b = a\ \text{or}\ b = f(a). \end{equation*} It is easy to verify that this is in fact an equivalence relation on $A$. Call $C_a$ the equivalence class of an element $a \in A$. Therefore, $C_a = \{a, f(a) \}$ if $a \in A \setminus A'$ and $C_a = \{a\}$ if $a \in A'$. We have \begin{equation*} |A| = \sum_{a \in A} |C_a| = \sum_{a \in A \setminus A'} |C_a| + \sum_{a \in A'} |C_a| = \sum_{a \in A \setminus A'} |C_a| + |A'|. \end{equation*} Since $|C_a| \equiv 0 \pmod 2$ for all $a \in A \setminus A'$, we have $|A| \equiv |A'| \pmod 2$.

Is this proof correct? If it is, can it be improved? Are there other proofs of this fact?

Answer 1

Your proof is almost correct, and what you probably were thinking is correct. The only problem is that when you write $\sum_{a\in A\setminus A'}|C_a|$, you’re counting each of the doubleton classes twice. What you really want to do here is let $\mathscr{C}=\{C_a:a\in A\}$ and $\mathscr{C}'=\{C_a:a\in A'\}$, say, and look at

$$\sum_{C\in\mathscr{C}\setminus\mathscr{C}'}|C|+\sum_{C\in\mathscr{C}'}|C|\;.$$

Also note that you don’t need to split the description of $C_a$ into two cases: $C_a=\{a,f(a)\}$ for all $a\in A$. It’s just that this set is a singleton when $a\in A'$ and a doubleton otherwise.

Answer 2

There is only one issue here, which is that you count some equivalence classes twice. Namely, if $f(a)=b\neq a$, then $C_a=C_b=\{a,b\}$.

You can fix this by choosing a representative from each equivalence class. Namely $B\subseteq A$ is a choice of representative from each $C_a$. Note that it follows that $A'\subseteq B$. The rest of the proof is fine.