# Permutations & Functions

This is an assignment question I received a week ago.

A function $f:\{1, 2, \dots ,n\} \to \{1, 2, \dots, n\}$ which is a bijection is also called a permutation. Let $P_n$ be the set of all permutations on $\{1, 2, \dots , n\}$. Define the relation $\sim$ on $P_n$ by $f\sim g$ iff there exists a permutation $h$ such that $f = h \circ g \circ h^{-1}$.

a) Need to show that it is an equivalence relation.

My Approach:

For a relation to be an equivalence relation, it must be reflexive, symmetric, and transitive.

Reflexive:

Let $f \sim f \Longleftrightarrow$ there exists $h$ such that $f = h \circ f \circ h^{-1}$.

My question (this may be silly) but is $h \circ f \circ h^{-1} = f$? I claimed that it was, and thus if $h \circ f \circ h^{-1} = f$, then it is reflexive.

Symmetric:

Let $f \sim g \Longleftrightarrow$ there exists $h$ such that $f = h \circ g \circ h^{-1}$. Let $g \sim f \Longleftrightarrow$ there exists $h_2$ (may be a different $h$) such that $g = h \circ f \circ h^{-1}$.

If $f = h \circ g \circ h^{-1}$ then $f = g$.

And since $g = h \circ f \circ h^{-1}$ then $g = f$.

Clearly this is reflexive.

I would like to know if I am in the right direction.

Regards,

Julian.

-

You are generally going in the right direction. For reflexive, the permutations do not commute, so $h \circ f \circ h^{-1}$ does not necessarily equal $f$. But can find a specific $h$ that works. For symmetric, when you write $g$ you should write $g = h_2 \circ f \circ h_2^{-1}$. Again, because the permutations do not commute you cannot conclude (and it is not generally true) that $f=g$. But given $f = h \circ g \circ h^{-1}$ you should be able to find an $h_2$. For transitive, you assume $f = h \circ g \circ h^{-1}$ and $g= h_2 \circ k \circ h_2^{-1}$ Now can you find $h_3$ such that $f = h_3 \circ k \circ h_3^{-1}$?
@JulianPark: That is exactly what I was thinking. You have shown $f \sim f$ as you wanted. Another that works is $f$ itself, as does $f^{-1}$ (which need not be distinct from $f$) –  Ross Millikan Nov 2 '12 at 3:19