Question

Let Σ be a finite alphabet with n letters and let R be the relation on Σ* defined as follows: R = {(u, v): every letter in u occurs somewhere in v, and every letter in v occurs somewhere in u} Then R is an equivalence relation with exactly 2n equivalence classes.

T or F?

Answer 1

First we will prove that R is an equivalence relation. We prove the three properties required:

• Reflexive: If u is a string on the given alphabet, then each letter in u occurs somewhere in u which implies u is related to itself by R. In other words  . Thus R is reflexive.
• Symmetric: If u and v are strings on the given alphabet such that each letter in u occurs in v and each letter in v occurs in u, then R(u,v) and R(v,u). In other words . Thus R is symmetric.
• Transitive: If u, v and w are strings on the given alphabet such that each letter in u occurs in v and each letter in v occurs in u, and each letter in v occurs in w and each letter in w occurs in v then the words in u, v and w are made of the same letters and thus each letter in u occurs in w and each letter in w occurs in u. In other words . Thus R is transitive.

We have proved that R is an equivalence relation, now we will have to find the number of equivalence classes.

For each subset of Σ we have one equivalence class which consists of all the words made only from the alphabets in that particular subset. Since the number of subsets of Σ is , R is an equivalence relation with equivalence classes.