How to prove that this relation R is transitive?

Question

Consider the following relation R on the set $W =\{0,1\}^{16}.$ For every two sequences $a = (a_1, \ldots,a_{16})$ and $b = (b_1,\ldots,b_{16})$ from $W$, we have $R(a,b)$ if and only if $b = (a_k,\ldots ,a_{16},a_1, \ldots,a_{k−1})$ for some $k \in \{1, \ldots,16\}$. (a) Prove that R is an equivalence relation.

This is what I have done so far:

Let $aRb$ such that there exists $a_k \in \{1,...,16\}, b =\{b_1,...,b_{16}\} = \{a_k,\ldots,a_{16},a_1,\ldots,a_{k-1}\}$

Let $bRc$ such that $k' \in \{1,...,16\}, c = \{c_1,\ldots,c_{16}\} = \{b_{k'},\ldots,b_{16},b_1,...b_{k'-1}\}$

Now i'm not sure how to write $c$ in terms of the sequence a to prove that $aRc$.

Welcome to MSE. For some basic information about writing mathematics at this site see, e.g., basic help on mathjax notation, mathjax tutorial and quick reference, main meta site math tutorial and equation editing how-to. — José Carlos Santos, Apr 18 '23 at 09:18
For reflexivity I showed that aRa when k = 1. For symmetry, I showed that aRb for some k then for some m ∈ {1,...,16} a = (bm,...,b16,b1,...,bm-1} hence bRa. @DougM — ark, Apr 18 '23 at 09:29
try a (smaller) example first (replace all $b_k$ in the relation $bRc$ with the respective $a_k$ in the relation $aRb$ — Sam Hoffman, Apr 18 '23 at 09:31
Hint: consider the map (circular permutation) $\sigma:(x_1,\dots,x_{16})\mapsto(x_2,x_3,\dots,x_{16},x_1)$ and its iterates $\sigma^k$ (which depend only on $k\bmod{16}$). This will simplify your notations. — Anne Bauval, Apr 18 '23 at 09:31
@AnneBauval im not sure how to express it as a function of k — ark, Apr 18 '23 at 09:49
@AnneBauval =(1,…,16) =(,…,16,1,…,−1) a = (bm,...,b16,b1,...,bm-1}. This shows that a1 = bm, a16 = bm-1 , ak-1 = b16 and ak = b1 — ark, Apr 18 '23 at 10:16
Ok thank you for your patience. Now, my hint above might help for transitivity. — Anne Bauval, Apr 18 '23 at 10:23

Muhammad rahmani · Answer 1 · 2023-04-19T13:07:33.670

By definition $$aR b\iff \exists k\in[\![1,16]\!]\text{ such that }b=(a_k,\ldots,a_{16},a_1,\ldots,a_{k-1})$$ which means that $b$ is obtained from $a$ by shifting the first $k-1$ elements to the right. Then we have \begin{align*} b_j&=a_{(j+k-1)\ mod\ 16},\qquad \forall j\in[\![1,16]\!]\setminus\{\ 17-k\} \\ b_{17-k}&=a_{16} \end{align*} So to prove transitivity, let $a,b,c\in W$ such that $aR b$ and $bR c$, then $\exists k,s\in[\![1,16]\!]$ such that $$b_j=a_{(j+k-1)\ mod\ 16}\quad \text{and}\quad c_j=b_{(j+s-1)\ mod\ 16},\quad\forall j\in[\![1,16]\!]\setminus\{\ 17-k,17-s\}.$$ To prove $aRc$ we must write each $c_j$ in terms of coordinates of $a$ as the definition. We just replace in the two previous relations we obtain: \begin{align*} c_j&=b_{\color{blue}{\textrm{(j+s-1) $mod$ 16}}}\\ &=a_{\big(\color{blue}{\textrm{(j+s-1) $mod$ 16}}+k-1\big)mod\ 16}\\ &=a_{(j+s-1+k-1)mod\ 16}\\ &=a_{(j+m-1)mod\ 16} \end{align*} where $m:=(k+s-1)\mod 16$. In this way we get $c=(c_1,\ldots,c_{16})=(a_m,\ldots,a_{16},a_1,\ldots,a_{m-1})$, i.e, $aRc$ as desired. $ \qquad \qquad \square $
For example, we have $$c_1=a_{(1+m-1)\ mod\ 16}=a_{m\ mod\ 16}=a_m$$ $$c_{16}=a_{(16+m-1)\ mod\ 16}=a_{(m+15)\ mod\ 16}=a_{(m-1)\ mod\ 16}=a_{m-1}$$ Note we do the reduction modulo $16$ in indexation to ensure indexing stays in the interval $[\![1,16]\!]$.

How to prove that this relation R is transitive?

1 Answers1