Question

Suppose that \({\bf{A}}\) and \({\bf{B}}\) are finite subsets of \({{\bf{V}}^{\bf{*}}}\), where \({\bf{V}}\) is an alphabet. Is it necessarily true that \(\left| {{\bf{A B}}} \right|{\bf{ = }}\left| {{\bf{B A}}} \right|\)?

Short answer

\(\left| {{\bf{A B}}} \right|{\bf{ = }}\left| {{\bf{B A}}} \right|\) is not true.

Step-by-step solution

Definition

In mathematics, set \({\bf{A}}\) is a subset of a set \({\bf{B}}\) if all elements of \({\bf{A}}\) are also elements of \({\bf{B}}\); \({\bf{B}}\) is then a superset of \({\bf{A}}\). It is possible for \({\bf{A}}\) and \({\bf{B}}\) to be equal; if they are unequal, then \({\bf{A}}\) is a proper subset of \({\bf{B}}\).

Verifying \(\left| {{\bf{A B}}} \right|{\bf{ = }}\left| {{\bf{B A}}} \right|\) is true or not

It is not true that \(\left| {A B} \right|\) is always equal to \(|A| \bullet |B|\), since a string in \({\bf{AB}}\) may be formed in more than one way. After a little experimentation, it might come up with the following example to show that \(\left| {{\bf{A B}}} \right|\) need not equal \(\left| {{\bf{B A}}} \right|\) and that \(\left| {{\bf{A B}}} \right|\) need not equal. Let \({\bf{A = }}\left\{ {{\bf{0,00}}} \right\}\), and let \({\bf{B = }}\left\{ {{\bf{01,1}}} \right\}\). Then \({\bf{A B = }}\left\{ {{\bf{01,001,0001}}} \right\}\) (there are only \(3\) elements, not \({\bf{2 \times 2 = 4}}\), since \(001\) can be formed in two ways), whereas \({\bf{B A = }}\left\{ {{\bf{010,0100,10,100}}} \right\}\) has \(4\) element.

Hence, \(\left| {{\bf{A B}}} \right|{\bf{ = }}\left| {{\bf{B A}}} \right|\) is not true.