0
$\begingroup$

Good day. Just a couple of questions on Equivalence Relations/Classes and proofs.

Let X denote the number of ways to arrange 4 distinct elements (this was 24 as obtained via 4!)

Consider the relation R between arrangements such that a new arrangement can be obtained by shifting all elements one space to the right. (1234 => 4123)

If A on X is the transitive closure of relation R

  1. Would it be correct to say that A denotes "The number of possible arrangements obtained by shifting all distinct elements to the right"?

I'm not sure if the idea of "24 different arrangements" is necessary as A is a transitive closure.

  1. Suppose A is an equivalence relation. How many distinct equivalence classes exist for A? Which classes are they?

This is something I don't really understand. Are the permutations of the 4 elements the same as the "equivalence classes"? Since shifting all elements to the right doesn't affect the permutations prima facie.

  1. Prove A is an equivalence relation.

Reflexive - ???

Symmetric - "There are 24 ways to arrange the distinct elements after shifting them to the right" and "There are 24 ways to arrange the elements after shifting them to the left" Hence, they are symmetrical.

Transitive - "There are 24 ways to arrange the distinct elements" and "All elements can be shifted to the right to create a new arrangement". This is transitive as A is the transitive closure of these two statements.

Any help/comments would be greatly appreciated.

$\endgroup$
0
$\begingroup$

Let $p$ and $q$ be permutations of $\{1,2,3,4\}$. The statement that $A$ is the transitive closure of $R$ means that $\langle p,q\rangle\in A$ if and only if there are permutations $p=p_0,p_1,\ldots,p_n=q$ for some $n\in\Bbb Z^+$ such that $\langle p_k,p_{k+1}\rangle\in R$ for $k=0,\ldots,n-1$. In less formal notation, $p\mathrel{A}q$ if and only if there are permutations $p=p_0,p_1,\ldots,p_n=q$ for some $n\in\Bbb Z^+$ such that

$$p=p_0\mathrel{R}p_1\mathrel{R}\ldots\mathrel{R}p_n=q\;.$$

To answer your first question, $A$ is not a number; it’s a relation on the set of permutations of $\{1,2,3,4\}$. If $P$ is that set of permutations, $A$ is a subset of $P\times P$.

Now suppose that $p=a_1a_2a_3a_4$; then

$$p=a_1a_2a_3a_4\mathrel{R}a_4a_1a_2a_3\mathrel{R}a_3a_4a_1a_2\mathrel{R}a_2a_3a_4a_1\mathrel{R}a_1a_2a_3a_4=p\;,$$

so $p\mathrel{A}a_4a_1a_2a_3$, $p\mathrel{A}a_3a_4a_1a_2$, $p\mathrel{A}a_2a_3a_4a_1$, and $p\mathrel{A}p$, and it’s pretty clear that these are the only four permutations $q$ such that $p\mathrel{A}q$. This already shows that the relation is reflexive, since $p\mathrel{A}p$ for all $p\in P$. You can also verify quite easily that $A$ is symmetric and transitive.

Notice first that we’ve shown that for any $p,q\in P$, $p\mathrel{A}q$ if and only if $q$ can be obtained from $p$ be a circular right shift of $0,1,2$, or $3$ places. Then observe that if $q$ is obtained from $p$ by a circular right shift of $k$ places, where $0\le k\le 3$, then $p$ is obtained from $q$ by a circular right shift of $4-k$ places: $k+(4-k)=4$, and a $4$-place shift is equivalent to doing nothing. You should try to prove in similar fashion that $A$ is transitive. Assume that $p,q,r\in P$ are such that $p\mathrel{A}q$ and $q\mathrel{A}r$, and show that $p\mathrel{A}r$.

We saw above that each $p\in P$ is $A$-related to $4$ members of $P$ including itself; this set of $4$ permutations is the equivalence class of $p$ with respect to $A$. The equivalence classes of an equivalence relation partition the underlying set, which in this case is $P$. $P$ has $24$ elements, and each equivalence class has $4$ elements. If you partition $P$ into $4$-element sets, there must be $\frac{24}4=6$ such sets, so $A$ has $6$ equivalence classes. One of them is

$$\{1234,4123,3412,2341\}\;:$$

the four members of this set are $A$-related to one another and to no other partition of $\{1,2,3,4\}$. We know now that there are $5$ other $A$-equivalence classes; I’ll leave it to you to find them and write them out.

$\endgroup$
  • $\begingroup$ Thanks for the detailed reply, Brian! $\endgroup$ – Unholy Wish Oct 29 '15 at 4:20
  • $\begingroup$ @UnholyWish: You’re welcome! $\endgroup$ – Brian M. Scott Oct 29 '15 at 4:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.