Equivalence Class of Fixed Element

From ProofWiki
Jump to: navigation, search

Theorem

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

Let $\sigma \in S_n$.

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

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


Then:

$i \in \Fix \sigma$ if and only if $\eqclass i {\mathcal R \paren \sigma} = \set i$

where:

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


Corollary

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


Proof

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


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

Let $j \in \eqclass i {\mathcal R \paren \sigma}$.


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

$j \in \eqclass i {\mathcal R \paren \sigma} \iff i \mathrel {\mathcal R_\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$


Therefore:

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

and so:

$\eqclass i {\mathcal R \paren \sigma} = \set i$

$\Box$


For the converse, suppose that:

$\eqclass i {\mathcal R \paren \sigma} = \set i$.


It is seen that:

$i \mathrel {\mathcal R_\sigma} \sigma \paren i \iff \sigma \paren i \in \eqclass i {\mathcal R \paren \sigma}$

Therefore:

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


Hence the result.

$\blacksquare$