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
    Given that first and third are fixed, there are 9 ways to vary, assuming first and third letters are A and A, times that by 4 gives us 36 variations which means 36 equivalnce classes?2012-11-05
  • 0
    There are two seperate counts here, be careful not to confuse them. First we are counting the number of _equivalence classes_. This is the same as counting the ways we can vary the first and third letters. Second we are counting the number of _elements_ in each equivalence class (which upon reading your question carefully doesn't actually seem to be required). For this, we count the number of ways we can vary the second and fourth letters.2012-11-05
  • 0
    16 ways to vary, is that the number of equivalence class? Also, how can any of them be equal to Z, i thought the first and third have to be the same2012-11-05
  • 0
    You seem to be confused on the concept of equivalence classes a bit, let me elaborate a bit more in my answer.2012-11-05
  • 0
    @Aaron Please see the updated answer. Hopefully it will clarify a few things.2012-11-05
  • 0
    Ok,the answer given is that there are 16 equivalence classes that are distinguished by the letters in the first and third positions, and there would be 20 members for each equivalence class, correct?2012-11-05
  • 0
    @Aaron Perfect.2012-11-05
  • 0
    And therefore, Z belongs to the equivalence class that has B as the first letter and A for third?2012-11-05
  • 0
    @Aaron Yes, precisely.2012-11-05