Equivalence Class of Fixed Element/Corollary

From ProofWiki
Jump to navigation Jump to search

Theorem

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

Let $\sigma \in S_n$.

Let $\map {\mathcal R} \sigma$ denote the equivalence defined in Permutation Induces Equivalence Relation.

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


Then:

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

where:

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


Proof

From Equivalence Class of Fixed Element and Biconditional Equivalent to Biconditional of Negations:

$i \notin \Fix \sigma \iff \set i \ne \eqclass i {\map {\mathcal R} \sigma}$


Because the Biconditional is Transitive, it suffices to show that:

$\set i \ne \eqclass i {\map {\mathcal R} \sigma}$

if and only if:

$\eqclass i {\map {\mathcal R} \sigma}$ contains more than one element.


Suppose that $\set i \ne \eqclass i {\map {\mathcal R} \sigma}$.

From the definition of an equivalence relation it is seen that:

$\set i \subseteq \eqclass i {\map {\mathcal R} \sigma}$


And from the hypothesis:

$\set i \subset \eqclass i {\map {\mathcal R} \sigma}$


Therefore $\eqclass i {\map {\mathcal R} \sigma}$ contains more than one element.

$\Box$


Conversely, if $\eqclass i {\map {\mathcal R} \sigma}$ contains more than one element, then it is seen that:

$\set i \ne \eqclass i {\map {\mathcal R} \sigma}$

$\blacksquare$