For $A = \{a, b\}$ and $B = A^* × A^*$ ($A^*$ is the set of all words (of all lengths))

In my opinion, because $B$ is reflexive, symmetric and transitive $(aa, bb)$. It is an equivalence relation, the equivalence classes should be one, because all elements are related to each other?

Am I correct?

  • $\begingroup$ What is $B$ a relation on? Seemingly, it's on the set of all words with letters in $A$. $\endgroup$ – астон вілла олоф мэллбэрг Aug 18 '17 at 5:55
  • $\begingroup$ That's right! A* could be any length. $\endgroup$ – user3741679 Aug 18 '17 at 6:12
  • $\begingroup$ Okay, so $B$ is a relation on the set $A^*$, given by $A^* \times A^*$ itself. Of course, this means any two elements are related, so that the number of equivalence classes is indeed only one. $\endgroup$ – астон вілла олоф мэллбэрг Aug 18 '17 at 6:16

Yes you're right. Two elements belong to the same equivalence class if and only if they are equivalent. If you take any two elements $w_1,w_2\in A^*$, we have $(w_1,w_2)\in A^*\times A^*=B$, which shows that they are both equivalent under the equivalence relation $B$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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