How can I simplify this number theory problem?

Question

Let X = {1, 2, 3, 4, 5, 6} and σ= \begin{bmatrix} 1 & 2 & 3 & 4 & 5 & 6 \\ 6 & 4 & 3 & 5 & 2 & 1 \\ \end{bmatrix} Define a relation ∼ on X as follows: for x, y ∈ X, x ∼ y if there is a natural number k such that $σ^k(x) = y$. Prove this is an equivalence relation and determine the equivalence classes. Here $σ^k$ is the composition of σ with itself k times: $σ^2 = σ ◦ σ, σ^3 =σ ◦σ^2$, ...

For the transitive relation, I don't want to run through every pair catching transitivities, so I am just wondering if there is a nice a way in which I can show that the relation is transitive.

I cannot understand your notation in the first line. Go to the Help page and click on "How do I format Mathematics here?" — DanielWainfleet, May 27 '16 at 05:21
Why, if $\sigma^k(x)=y$ and $\sigma^m(y)=z$, then what is $\sigma^{k+m}(x)$? — Ivan Neretin, May 27 '16 at 05:37

score 1 · Answer 1 · answered May 27 '16 at 16:32

Define $x \sim y$ if some power of $\sigma$ takes $x$ to $y$. Let's show the relation is symmetric. Suppose $x \sim y$. Then some power $\sigma^k$ of $\sigma$ takes $x$ to $y$, and so $\sigma^{-k} = \sigma^{-k+6}$ is a power of $\sigma$ takes $y$ to $x$. I've used the fact that $\sigma=(1,6)(2,4,5)(3)$ has order 6. To show $\sigma$ is transitive, suppose $x \sim y$ and $y \sim z$. Then some power $\sigma^k$ takes $x$ to $y$ and some power $\sigma^\ell$ takes $y$ to $z$, and so $\sigma^{k+\ell}$ takes $x$ to $z$. Thus, $x \sim z$. The zeroth power of $\sigma$ takes each point $x$ to itself, and so the relation is also reflexive. This proves that the relation is an equivalence relation.

Since every equivalence relation gives rise to a partition, the relation gives rise to a partition of $\{1,\ldots,6\}$. The parts in this partition are called the orbits of the permutation group $\langle \sigma \rangle$. In this example, there are three orbits, namely $\{1,6\}, \{2,4,5\}$ and $\{3\}$.

score 0 · Answer 2 · answered May 27 '16 at 05:37

0

So let's say $x \sim y$ and $y \sim z$.

Then, for some $k$ and $m$, $y=\sigma^k(x)$ and $z=\sigma^m(y)$.

Then, $$ z=\sigma^m(y)=\sigma^m(\sigma^k(x))=\sigma^{m+k}(x)$$. Thus $x \sim z$.

answered May 27 '16 at 05:37

ASKASK

9,000
4
28
49

why is $σ^{m+k}$ true – TheMathNoob May 27 '16 at 05:42
If I apply a function $k$ times, and then I apply it $m$ more times, how many times have I applied it? – ASKASK May 27 '16 at 05:43
ohhhh yes right m+k what about to show it's symmetric?. For that one I do need to run the pairs? – TheMathNoob May 27 '16 at 05:56

How can I simplify this number theory problem?

2 Answers2