# Equivalence classes

Page 1 of 1

## 1 Replies - 1471 Views - Last Post: 30 September 2013 - 10:53 AM

### #1 deprosun

• D.I.C Regular

Reputation: 0
• Posts: 306
• Joined: 16-November 10

# Equivalence classes

Posted 30 September 2013 - 10:38 AM

Let Σ be the alphabet {a, b, c, d} and let R be the following relation on Σ*: R(x, y) is true if every letter in string x also occurs in y, and every letter in string y also occurs in x. (For, R(abba, babbb) is true and R(abcb, cbbcb) is false.) How many (non-empty) sets are in the partition of Σ* corresponding to R? (That is, how many equivalence classes does R have?)

I think it would be 16, because:
it doesn't matter if there are any repeated letters. A string x has a relation to all other strings y that contain same letters, and the collection of the y's with that x is a set called equivalence class of x. Correct?

If so, if x = abba (which is basically consisted of a and b's), equivalence class of x with contain all y containing ab's. ab is one of the possible subsets. other are abcd, ad, ac, dc, dcb....etc. And there are 2^4 possible strings. So there are 2^4 equivalence classes.

Correct?

Is This A Good Question/Topic? 0

## Replies To: Equivalence classes

### #2 deprosun

• D.I.C Regular

Reputation: 0
• Posts: 306
• Joined: 16-November 10

## Re: Equivalence classes

Posted 30 September 2013 - 10:53 AM

or actually 15 because we need a non empty set.