1
$\begingroup$

Let $S_6 = \{1, 2, 3, 4, 5, 6\}$ and define 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?

1 Answers 1

1

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$.