0
$\begingroup$

Let A be the set of all possible strings of 3 or 4 letters in alphabet ${A,B,C,D}$, let z = $BCAD$, and let $(x,y)\in R$ if and only if $x$ and $y$ have the same first letter and the same third letter

I have already confirmed that this is an equivalence relation and now I have to find the equivalence classes, the number of equivalence classes and determine which equivalence class belongs to Z when Z= $BCAD$

I have no idea where to start. (Textbook question, not for homework)

Please do not tell me the answer, but tell me how to begin or give a portion of the answer.

1 Answers 1

2

Well, each choice of a starting letter and a third place letter will represent an equivalence class. Can you see why? So how many equivalence classes are there (this is equivalent to counting how many ways we can choose the first and third letters in the string).

To see the size of an equivalence class, note that given any equivalence class, the first and third letters are fixed. So how many ways can we vary the second and fourth letters?

To give a concrete example of an equivalence class, suppose we have the string $ACBD$. What are all the members of it's equivalence class? Well to be in the same equivalence class as $ACBD$, we need the string to have the same first letter as $ACBD$, namely $A$, and the same third letter, namely $B$. Then the strings are of the form $A?B?$. Now we have to fill in the question marks. Each choice of letters will be fine. $AABA,\ AABB,\ AABC,\ AABD,\ AAB$ $ABBA,\ ABBB,\ ABBC,\ ABBD,\ ABB$ $ACBA,\ ACBB,\ ACBC,\ ACBD,\ ACB$ $ADBA,\ ADBB,\ ADBC,\ ADBD,\ ADB$ And those are all the members in the equivalence class of $ACBD$. You would do something similar to find out the members of the equivalence class for $BCAD$.

  • 0
    @Aaron Yes, precisely.2012-11-05