Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
up vote 2 down vote accepted

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

share|cite|improve this answer
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? – Aaron Nov 5 '12 at 4:08
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. – EuYu Nov 5 '12 at 4:14
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 same – Aaron Nov 5 '12 at 4:20
You seem to be confused on the concept of equivalence classes a bit, let me elaborate a bit more in my answer. – EuYu Nov 5 '12 at 4:24
@Aaron Please see the updated answer. Hopefully it will clarify a few things. – EuYu Nov 5 '12 at 4:32

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.