0
$\begingroup$

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

$\endgroup$
1
  • 1
    $\begingroup$ How do you show it is reflexive? You do not do it by taking examples, take general strings from $A$ and operate, otherwise you could stumble upon a false example. As it happens, reflexivity and symmetry are true, but transitivity is not: For example, $abba \sim abbb$ (same first letter) and $abbb \sim bbbb$ (same last letter) but $abba \sim bbbb$ (neither first nor last letter match). $\endgroup$ Nov 19 '16 at 8:02
2
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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

$\endgroup$

Your Answer

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