Equivalence Class of Fixed Element

From ProofWiki
Jump to navigation Jump to search


Let $S_n$ denote the symmetric group on $n$ letters.

Let $\sigma \in S_n$.

Let $\RR_\sigma$ denote the equivalence defined in Permutation Induces Equivalence Relation.

Let $i \in \N^*_{\le n}$.


$i \in \Fix \sigma$ if and only if $\eqclass i {\RR_\sigma} = \set i$


$\eqclass i {\RR_\sigma}$ denotes the equivalence class of $i$ under $\RR_\sigma$
$\Fix \sigma$ denotes the set of fixed elements of $\sigma$.


$i \notin \Fix \sigma$ if and only if $\eqclass i {\RR_\sigma}$ contains more than one element


By the definition of an equivalence relation it is easily seen that $\set i \subseteq \eqclass i {\RR_\sigma}$.

Suppose that $i \in \Fix \sigma$.

Let $j \in \eqclass i {\RR_\sigma}$.

Then by Condition for Membership of Equivalence Class and Permutation Induces Equivalence Relation:

$j \in \eqclass i {\RR_\sigma} \iff i \mathrel {\RR_\sigma} j \implies \exists m \in \Z: \sigma^m \paren i = j$

And by Fixed Point of Permutation is Fixed Point of Power:

$\sigma^m \paren i = i \implies i = j$


$\eqclass i {\RR_\sigma} \subseteq \set i$

and so:

$\eqclass i {\RR_\sigma} = \set i$


For the converse, suppose that:

$\eqclass i {\RR_\sigma} = \set i$.

It is seen that:

$i \mathrel {\RR_\sigma} \map \sigma i \iff \map \sigma i \in \eqclass i {\RR_\sigma}$


$\map \sigma i = i \implies i \in \Fix \sigma$

Hence the result.