Relations problem

May 2010

What would be the solution to this exercise:

Consider the set S of 10^n different words of length n with the 10 letters A, B, C, D, E, F, G, H, I and J. Partition S in subsets X1, X2, X3,...., Xk so that the following binary relation R holds:
For all a, b in Xi, a can be reproduced by rewriting the letters of b, in different order. Which of the relations "reflexive", "symmetric", "transitive" holds for R? Is it an equivalence relation?
Thank you very much.
Last edited:


MHF Hall of Honor
Dec 2008
South Coast of England
Hello ktmr

I'm not sure about the meaning of the word 'different' in the phrase 'a can be reproduced by writing the letters of b in a different order'. If the order is strictly different, then the relation is not reflexive, since if we re-arrange the order of the letters making up the word a then we cannot reproduce the same word a again.

The relation is definitely symmetric (if b can be re-arranged to form a, then a can be re-arranged to form b).

But the same problem over the interpretation of 'different' will apply to transitivity, since aRb and bRa does not imply aRa, as it will need to if the relation is to be transitive.

However, if a 'different' order of the letters can actually mean leaving the letters in the same order, then the relation is reflexive, symmetric and transitive, and is therefore an equivalence.

  • Like
Reactions: ktmr