# Write down all of the elements of $S_6 \times S_6$ which are related to $u = (6, 5)$ under $R'$

Let $S_6 = \{1, 2, 3, 4, 5, 6\}$ and deﬁne a relation $R \subseteq S_6 \times S_6$ by

$$R = \{(n, m) \text{ | } n < m\text{ or }n = m + 1\}.$$

Question: Write down all of the elements of $S_6 \times S_6$ which are related to $u = (6, 5)$ under $R′$, that is all the elements $v$ such that $(v, u) \in R'$.

I have written down the elements of $R$: $$R=\{(1,2),(1,3),(1,4),(1,5),(1,6),(2,1),(2,3),(2,4),(2,5),(2,6),(3,2),(3,4),(3,5),(3,6),(4,3),(4,5),(4,6),(5,4),(5,6),(6,5)\}$$

It is my understanding that $R'$ means the lexicographic extension of R.

So, $(a,b)R'(c,d)$ if $aRc$ or $a=c$ and $bRd$.

Would someone oversee my logic please.

$(1,1) \in S_6 \times S_6$. Since $1R6$, $(1,1) \in R'$

$(1,2) \in S_6 \times S_6$. Since $2R6$, $(1,2) \in R'$

...

$(6,1) \in S_6 \times S_6$. Since $6=6$ and $1R5$, $(6,1) \in R'$

...

$(6,5) \in S_6 \times S_6$. Since $6=6$ and $5=5$, $(6,5) \notin R'$

$(6,6) \in S_6 \times S_6$. Since $6=6$ and $6R5$, $(6,5) \in R'$

So it is my understanding that the only ordered pair in $S_6 \times S_6 \notin R'$ is $(6,5)$. Am I correct?

-

Assuming that $R\,'$ is the lexicographic extension of $R$ to $S_6\times S_6$, it looks fine, apart from the wording of your conclusion. $R\,'$ is a subset of $(S_6\times S_6)\times (S_6\times S_6)$, so $\langle 6,5\rangle$ can't be a member of it. What you mean is that $\langle 6,5\rangle$ is the only member of $S_6\times S_6$ not related to $\langle 6,5\rangle$ by $R\,'$: $$\Big\langle\langle 6,5\rangle,\langle 6,5\rangle\Big\rangle\notin R\,'\;,$$ and in fact $$R\,'=\Big((S_6\times S_6)\times(S_6\times S_6)\Big)\setminus\left\{\Big\langle\langle 6,5\rangle,\langle 6,5\rangle\Big\rangle\right\}\;.$$
You can do it more easily, though. Suppose that $\langle a,b\rangle$ is not related to $\langle 6,5\rangle$. Then either $a\,\not R\,6$, or $a=6$ and $b\,\not R\,5$. If $a\,\not R\,6$, then $a=6$, so $b\,\not R\,5$, and therefore $b=5$.