Is $R$ reflexive, symmetric, and transitive?

431 Views Asked by At

Let A be the set of all strings of all consisting solely a's and b's of length 4. define the relation R on A by $\forall s,t\in A: sRt\iff$ s and t have the same first or last letter

Is $R$ reflexive, symmetric, and transitive

my attmept: the example of the string is :abba or abab it clear that the relation is reflection and symmetric but i am not sure about transitive

2

There are 2 best solutions below

0
On BEST ANSWER

For this, taking an example doesn't prove anything. You can use counterexamples when you want to disprove a given statement.

To show this one by one


Reflexive:

Let $s\in A$. Clearly, the first letter of any $s$ is equal to the first letter of $s$, and similarly for the last letter. Hence, $sRs$ and the relation is reflexive.


Symmetric:

Let $s,t\in A$ such that $sRt$. By definition, the first or last letter of $t$ is the same as $s$. So, the first or last letter of $s$ must be the same as $t$, hence $tRs$, and the relation is symmetric.


Transitive:

Let $r,s,t\in A$ such that $rRs$ and $sRt$. Then, at least one out of the first and last letters of $r$ and $s$ are the same, and one out of the first and last letters of $s$ and $t$ are the same. But it is not necessary that this hold for $r$ and $t$. Let $r_1$ be the first letter of $r$ and $r_4$ be the lat letter. Suppose $r_1=s_1$ and $r_1\ne t_1$, and $s_4=t_4$ and $r_4\ne t_4$. Clearly, $rRt$ is not true. For example, let $r=aaab$, $s=aaaa$, $t=baaa$. Hence the relation is not transitive.

0
On

I think you mean reflexive rather than relative.

To find reflexivity, check: If $s$ is any string does it have the same first letter as itself? Trivially yes, so the relation is reflexive, i.e. $sRs$.

To check symmetry suppose $sRt$ so that they either have the same first letter or the same last letter. Then $tRs$ because they either have the same first or last letter.

To check transitivity, take $abba$, and $abbb$ and $baaab$. We have $sRt$ and $tRu$ but not $sRu$.